Задача коммивояжера

[botanik]

Поставлена задача - реализовать алгоритм решения задачи коммивояжера, используя реккурентные соотношения Беллмана.
Встал вопрос о эффективном использовании памяти. При решении задачи хранится очень большое количество информации, необходимое для отката(построения непосредственно оптимального пути).
Может быть кто-нибудь сталкивался с такой проблемой. Буду рад любой помощи - исходники, ссылки на литературу, просто какие-то соображения.

Заранее благодарен.

[juna]

А Вам принципиально из Беллмана или нет? Если нет, то чем плох метод ветвей и границ - Судоплатов, Овчинникова "Основы дискретной математики" (за точность названия и авторов не ручаюсь). В интернете и готовые проги есть, например, Grin Печенкина http://www.uni-dubna.ru/~mazny/kurses/odm/lekcii/index.html

[botanik]

Артамонов Ю.Н. писал(а):

А Вам принципиально из Беллмана или нет? Если нет, то чем плох метод ветвей и границ - Судоплатов, Овчинникова "Основы дискретной математики" (за точность названия и авторов не ручаюсь). В интернете и готовые проги есть, например, Grin Печенкина http://www.uni-dubna.ru/~mazny/kurses/odm/lekcii/index.html

Принципиально из Беллмана! Просто все мои поиски в глобальной сети ни к чему не привели.(кроме методва ветвей и границ). Создается впечатление, что таким способом её решения(динамическое программирование) вообще никто не занимался (или я плохо искал).
Спасибо за указание на книгу: она возможно мне понадобится для решения видоизменённой задачи - т.н. задачи инкассации.Её как раз необходимо решить методом ветвей и границ.

[Vassil]

Задача о коммивояжере рассматривается еще и в книге И. В.Романовского "Алгоритмы решения экстремальных задач", Изд. "Наука", Москва 1977. В ней на стр. 210 форулируется задача. Непосредствено после этого рассматривается метод ветвей и границ для решения этой и других задач, вкл. и приводятся некоторые процедуры на Алголе.
Далее в главе 6 "Рекуррентные методы (модели денамического программирования)" обсуждаются особености реализации этих методов. К сожалению нет непосредственного упоминания насчет Задачи о коммивояжере, но может быть вам и написанное поможет самому вывести какие то подсказки ...

[botanik]

Ура!Справился!
Если кого-то заинтересует мой способ решения задачи коммивояжера методом реккурентных соотношений Беллмана, то где-то через 5 дней я выложу ссылку на исходники сюда.
Всем большое спасибо за помощь!

[botanik]

http://user.rol.ru/~skav86/AlgRec.zip
Если у кого-то будут замечания или предложения, буду только рад!

[V.V.]

botanik писал(а):

Ура!Справился!
Если кого-то заинтересует мой способ решения задачи коммивояжера методом реккурентных соотношений Беллмана, то где-то через 5 дней я выложу ссылку на исходники сюда.

А можно описание алгоритма с оценкой сложности?

[b3rs3rk]

выложите, пожалуйста, исходник задачи коммивояжера МВиГ

[bz21]

А кто-нибудь пробовал найти решение, когда матрица расстояний не симметричная по диагонали? Когда крокодил от носа до хвоста 8 метров, а от хвоста до носа - 7?
Особенно актуально для построения маршрутов внутри города, когда расстояние между точками меняется в зависимости от направления движения в связи с необходимостью соблюдения правил дорожного движения ...
Вот это зубодробительный вариант. Даже при составлении алгоритма полного перебора крыша съезжает.
Может кто чего посоветует?

[ГАЗ-67]

Попробуйте дополнить матрицу до квадратной.Длина несуществующих маршрутов задается очень большим числом .

[bz21]

Какие не существующие маршруты?
Все расстояния известны. Просто растояние от А до В не равно расстоянию от В до А. Соответственно, матрица расстояний по диагонали не симметрична ...

[ГАЗ-67]

Виноват,не сразу въехал

[botanik]

Для bz21:
А Вы начало темы читали или исходники смотрели?
Вообще говоря,при использовании рекуррентных соотношений для решения задачи коммивояжера не требуется симметричность матрицы расстояний.
Для ГАЗ-67:
Вашу идею я понял, Вы хотите использовать алгоритм Флойда или несколько раз запустить алгоритм Дейкстры, для нахождения кратчайших расстояний между городами в том случае, когда граф, соответствующий задаче коммивояжера, не полный.

[НеZнайка]

Проблема та же, нужен Help по Решению задачи о коммивояжере методом ветвей и границ. Это курсовой проект...необходимо реализовать в Delphi, перерыл много инфы, теория есть...проблема в написании кода.
буду рад любой помощи!

[Vassil]

Попробуйте посмотреть то, что по линку:

http://www.cs.sunysb.edu/~algorith/file ... sman.shtml

Быть может наведет куда хотите.