Решение задачи коммивояжера (TSP Traveling Salesman Problem)
Вполне возможно вам известна задача коммивояжера,
Подробнее на русском тут или на английском тут
На данный момент, из известных мне реализаций алгоритмов для решения этой NP трудной задачи, является конкорд, не смотря на то, что последняя модификация от 2003 года, он отлично решает эти задачи, и вероятно по прежнему лучше всех. Задача на нескольких тысячах точек, может решаться часами, именно поэтому требуется быстрое и эффективное решение вроде конкорда.
Возможно, вы захотите установить его под Mac Os, и вероятно не получится с первого раза откомпилировать код, в таком случае по совету Cartera рекомендую скачать небольшой скрипт который автоматически скачает версию конкорда и необходимые библиотеки qsort и откомпилировав установит. Скачать его можно тут http://code.google.com/p/eggbotcode/downloads/detail?name=build-concorde-osx-0_2.sh
Подробнее на русском тут или на английском тут
На данный момент, из известных мне реализаций алгоритмов для решения этой NP трудной задачи, является конкорд, не смотря на то, что последняя модификация от 2003 года, он отлично решает эти задачи, и вероятно по прежнему лучше всех. Задача на нескольких тысячах точек, может решаться часами, именно поэтому требуется быстрое и эффективное решение вроде конкорда.
Возможно, вы захотите установить его под Mac Os, и вероятно не получится с первого раза откомпилировать код, в таком случае по совету Cartera рекомендую скачать небольшой скрипт который автоматически скачает версию конкорда и необходимые библиотеки qsort и откомпилировав установит. Скачать его можно тут http://code.google.com/p/eggbotcode/downloads/detail?name=build-concorde-osx-0_2.sh
Комментарии