Michael_K писал(а):
Нашел я эту задачку...
Там, как мне кажется, (хотя гарантировать, конечно, нельзя)
сильно прореженная матрица (или граф) задается.
Мы делали не так.
Michael_K писал(а):
Да, нужно в ответе указать какие конкретно машины купить.
И вряд ли условия допускают два одинаковых решения.
Мы в соревнованиях ставили задачи, в которых допускается несколько решений, просто мы проверяли решение на корректность (в данном случае сильную связность и общую сумму) - это чуть сложнее, чем просто сверить 2 ответа на идентичность.
blindman писал(а):
Создатели задачи конечно понимают, что в общем виде задача нерешаема. Поэтому наверняка исходный граф удовлетворяет неким условиям, которые позволяют найти решение. Поэтому фактически решение состоит из 2 частей : сделать верное предположение о структуре исходного графа, и решить основываясь на этом предположении.
Не факт, может быть задачу можно решить за N^2*2^N операций, тогда при n=20 это всего 420млн операций.
blindman писал(а):
В первую очередь, напрашивается предположение что граф разрежен. Это подтверждается словами одного из решивших задачу: "there are more compounds than you think, but fewer machines"
Если бы я ставил задачу на решение которой надо реально заморочиться - я бы брал пачку тестов - с сильно разреженным графом, с полным графом, почти решение (всего 2-3 ребра выкинуть надо из огромного графа, скажем n=400, кол-во ребер 403) - в общем потребовал бы до кучи выбор алгоритма решения в зависимости от входящего набора данных
blindman писал(а):
Вполне возможно, тестовые данные генерятся примерно так: соединяем все n вершин n дугами в кольцо, в каждую вершину входит ровно 1 дуга и выходит ровно 1. Потом случайным образом добавляем некоторое количество дуг, подбирая их вес так, чтобы решение в виде кольца было не оптимальным, и проверяя, чтобы оптимальное решение было единственным.
Мы всегда ставя задачу имели уже какое-то решение и просто под него генерили случайные тесты, добавляя ребра, пока граф не станет сильно связным. Ну и делали 2-3 сгенерированных вручную тестов, типа как я указал n=400, ребер 403.
_________________
Проект
[[Open Robotics]] - Универсальные модули для построения роботов
Вход
Регистрация
FAQ
Поиск
