Pull to refresh

Comments 20

И всё это не факт что будет лучше для другого такого графа.
Или граф константа, и цель — найти оптимальный только в нём и только один раз?
задача стояла конкретно для одного графа.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.
для одного графа можно генетику запустить, и ждать до получения идеального варианта…
можно, да, но дэдлайн был близок и время было ограничено. лично мне еще понравился муравьиный алгоритм, но кодить его тоже времени не было
Все хорошо! Но надо бы вначале напоминать, что есть Гамильтонов цикл. А то создается впечатление…
Думал аналогично, пока не увидел, что граф полный.
Возможно, было бы лучше переименовать в «Задача коммивояжёра».
учел вашу критику =)
во время учебы как то занимался анализом алгоритмов для решения задач комбинаторной оптимизации, как раз на примере задачи коммивояжера. лет 5 назад у метя в топ-3 были: 1 — муравьиный алгоритм, 2 — генетический алгоритм, 3 — нейросеть Хопфилда. сейчас на сколько я помню лидирует генетический алгоритм.
я недавно находил, что все-таки муравьиная колония выигрывает сейчас
возможно ситуация опять поменялась, я сейчас не слежу за этой задачей
А литературу вы читали? Наиболее эффективный алгоритм решения TSP — через линейное программирование. Есть готовые программы, которые подобные алгоритмы реализуют: concorde. Современный рекорд порядка 100 000 вершин. Думаю с 500 вершинами проблем не будет.
задача была не получить ответ, а накодить алгоритм. я думаю, за три дня я бы не накодил то, что установило рекорд
А чем чужой код для вас хуже? Как минимум его можно использовать, чтобы получить точное решение, с которым можно сравнивать ваши результаты.
говорю же-задача стояла накодить.
для оценки результатов использовался результат жадины.
идея использовать оптимальное решение, данное линейным алгоритмом хороша, но имеет, на мой взгляд один минус-
мои алгоритмы сильно зависят от графа, и поэтому на разных графах будут показывать разные результаты относительно оптимального решения, но вот жадина-то тоже зависит от графа, поэтому относительно жадины мне показалось рассматривать как-то логичнее, проще анализировать
Я когда то решал похожую задачу генетическим алгоритмом.

Было бы неплохо также его упомянуть. Показывает достойный результат на больших графах.
Единственный его минус — это то, что может быть получено не оптимальное решение, а близкое к оптимальному.

Вот пример моего дипломника по этой теме.
Векторный редактор с картой города и поиск в транспортной сети. Тема очень близкая к данной.
Распакуйте архив в векторном редакторе, выберите уже готовую схему города с точками поиска и нажмите на кнопку «Поиск».
круто, посмотрю утром, когда будет время
А подскажите каким образом Вы кодировали/декодировали в хромосому путь обхода городов? Как из ноликов и единичек получить путь?
> Жадина хорошо работает на случайном графе, однако тут мы ничего про граф не знаем
Нематематик от такого впадет в ступор :-D
Задача коммивояжера, она же поиск гамильтонова цикла минимальной суммарной стоимости — NP-полная

Вот интересно, понимаете ли вы вообще, что такое NP-полная задача, когда употребляете этот термин? Вы, возможно, думаете, что это просто задача, решение которой недостижимо за полиномиальное время от некоторого параметра задачи? Спешу вас уверить, вы ошибаетесь. И задача коммивояжера вовсе не NP-полная, а NP-трудная. Ознакомьтесь, например:
www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/
да, согласен, в первоначальном варианте ошибка, верно — NP-тяжелая или NP-трудная. спасибо за указание
Only those users with full accounts are able to leave comments. Log in, please.