Решение задачи коммивояжёра рекурсивным полным перебором

[safright]

Насчет того, что полный перебор — «единственный» можно спорить очень долго и обоснованно. Чем вам «метод ветвей и границ» не угодил в таком контексте?

[Osmin]

Вот-вот, тем более метод ветвей и границ допускает в принципе нахождение оптимального решения, а предложенный алгоритм — не всегда.

[Prosolver]

Я исследовал применимость тривиального полного перебора как основного метода решения, в симбиозе с рекурсией. Любые другие методы, конечно, имеют право на существование.

[greefon]

Как то странно. Вы постулируете полный перебор, затем делаете его «не совсем полным» и опять же постулируете его «полность». Или я чего-то не понял.

[Prosolver]

Связи между узлами устанавливаются только полным перебором на данном уровне рекурсии. Конечно, перебор получается не полностью полный. Просто другого метода для соединения узлов здесь не используется.

[greefon]

Просто получается какая-то игра в слова. Т.е. предложенный метод по «полноте» не отличается от ветвей и границ (полный перебор с отсечениями), «отсечения» у вас происходят перед самим перебором, в момент формирования групп. И от «эвристики», как правильно внизу отметили, вы так и не избавились.

Интересно было бы посмотреть на оценку сложности (времени выполнения, эффективности) по сравнению с другими общепринятыми алгоритмами, может быть тут сильная сторона и не стоит так уж педалировать слово «полный»?

[Prosolver]

Согласен. Проработаю этот момент. Благодарю.

[nickme]

В результате вы все равно получили эвристический алгоритм… Чуда не произошло! :)

[Prosolver]

Да, конечно ) Но эвристики тут минимум. Если Вы видите способ, как полностью уйти от эвристики и основываться исключительно на каких-то соображениях, имманентно присущих данной задаче — было бы интересно узнать.

[nickme]

Про минимум эвристики улыбнуло :) Есть мнение, что уйти от экспоненциальности (а ведь это ваша цель?) и при этом сохранить оптимальность нельзя…

[Prosolver]

Да. Но! Можно попытаться эту экспоненциальность замедлить, если использовать априорную информацию о конкретной задаче.

[Prosolver]

В качестве меры близости используется евклидово расстояние, поэтому в принципе ничто не мешает его перевести в N-мерное пространство с метрикой евклида. В программе приведён вариант для 2-х измерений.

[ystein]

Алгоритм приближенного решения задачи коммивояжера большой размерности на плоскости
И. Х. Сигал
1987г.

Аннотация: Предлагается подход, основанный на декомпозиции и агрегировании. Множество точек разбивается на подмножества, для подмножеств выполняется агрегирование, решение задачи сводится к решению подзадач для подмножеств и к сшиванию этих решений в той последовательности, которая определяется решением задачи для точек – агрегатов этих подмножеств. Приводятся результаты вычислительного эксперимента.

[Prosolver]

Благодарю за ссылку. Сходство между алгоритмами, судя по статье, только в том, что используется рекурсия. В остальном отличия:
— в статье задача коммивояжёра на нижнем рекурсивном уровне решается подоптимальными методы / у меня полным перебором;
— в статье использован другой (нерекурсивный) алгоритм для разбиения на группы. А способ разбиения на группы — это самый принципиальный момент в рекурсивном подходе к решению задачи;
— у меня группы соединяются через один узел просто по ближайшему расстоянию между группами. У Сигала применена специальная процедура.

[sebres]

Самым больщим и IMO критичным отличием от Сигала у вас я вижу сложность сохранять веса маршрутов на будующее. У Сигала можно использовать уже раз просчитаные подмножества многократно — т.е. на одной композиции при расчете T(10 * K) много меньше чем 10 * T(K), где T время расчета, а K — коммивояжёр. Может я чего-то не допонял, но ваш алгоритм мне видится идеальным в случае один коммивояжёр ездит один раз в год — т.е. один раз просчитали и надолго забыли. Как то так.