Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 20
И всё это не факт что будет лучше для другого такого графа.
Или граф константа, и цель — найти оптимальный только в нём и только один раз?
Или граф константа, и цель — найти оптимальный только в нём и только один раз?
задача стояла конкретно для одного графа.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.
понятно, что на разных графах будут разные результаты, разный подбор эвристик, констант в алгоритмах и т.д.
в любом случае ни один из этих алгоритмов не дает верное решение. только близкое к нему. и на другом графе будут, возможно, другие результаты. однако жадина+метод ветвей и границ наиболее оптимален, т.к. никогда не будет худшим.а у простой жадины он точно всегда выиграет. единственное — когда-то может повезти, и чистый МВиГ посчитается быстро и выиграет.
во время учебы как то занимался анализом алгоритмов для решения задач комбинаторной оптимизации, как раз на примере задачи коммивояжера. лет 5 назад у метя в топ-3 были: 1 — муравьиный алгоритм, 2 — генетический алгоритм, 3 — нейросеть Хопфилда. сейчас на сколько я помню лидирует генетический алгоритм.
А литературу вы читали? Наиболее эффективный алгоритм решения TSP — через линейное программирование. Есть готовые программы, которые подобные алгоритмы реализуют: concorde. Современный рекорд порядка 100 000 вершин. Думаю с 500 вершинами проблем не будет.
задача была не получить ответ, а накодить алгоритм. я думаю, за три дня я бы не накодил то, что установило рекорд
А чем чужой код для вас хуже? Как минимум его можно использовать, чтобы получить точное решение, с которым можно сравнивать ваши результаты.
говорю же-задача стояла накодить.
для оценки результатов использовался результат жадины.
идея использовать оптимальное решение, данное линейным алгоритмом хороша, но имеет, на мой взгляд один минус-
мои алгоритмы сильно зависят от графа, и поэтому на разных графах будут показывать разные результаты относительно оптимального решения, но вот жадина-то тоже зависит от графа, поэтому относительно жадины мне показалось рассматривать как-то логичнее, проще анализировать
для оценки результатов использовался результат жадины.
идея использовать оптимальное решение, данное линейным алгоритмом хороша, но имеет, на мой взгляд один минус-
мои алгоритмы сильно зависят от графа, и поэтому на разных графах будут показывать разные результаты относительно оптимального решения, но вот жадина-то тоже зависит от графа, поэтому относительно жадины мне показалось рассматривать как-то логичнее, проще анализировать
Я когда то решал похожую задачу генетическим алгоритмом.
Было бы неплохо также его упомянуть. Показывает достойный результат на больших графах.
Единственный его минус — это то, что может быть получено не оптимальное решение, а близкое к оптимальному.
Вот пример моего дипломника по этой теме.
Векторный редактор с картой города и поиск в транспортной сети. Тема очень близкая к данной.
Распакуйте архив в векторном редакторе, выберите уже готовую схему города с точками поиска и нажмите на кнопку «Поиск».
Было бы неплохо также его упомянуть. Показывает достойный результат на больших графах.
Единственный его минус — это то, что может быть получено не оптимальное решение, а близкое к оптимальному.
Вот пример моего дипломника по этой теме.
Векторный редактор с картой города и поиск в транспортной сети. Тема очень близкая к данной.
Распакуйте архив в векторном редакторе, выберите уже готовую схему города с точками поиска и нажмите на кнопку «Поиск».
> Жадина хорошо работает на случайном графе, однако тут мы ничего про граф не знаем
Нематематик от такого впадет в ступор :-D
Нематематик от такого впадет в ступор :-D
Задача коммивояжера, она же поиск гамильтонова цикла минимальной суммарной стоимости — NP-полная
Вот интересно, понимаете ли вы вообще, что такое NP-полная задача, когда употребляете этот термин? Вы, возможно, думаете, что это просто задача, решение которой недостижимо за полиномиальное время от некоторого параметра задачи? Спешу вас уверить, вы ошибаетесь. И задача коммивояжера вовсе не NP-полная, а NP-трудная. Ознакомьтесь, например:
www.nomachetejuggling.com/2012/09/14/traveling-salesman-the-most-misunderstood-problem/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск гамильтонова цикла в большом графе (задача коммивояжера).Часть 1