Люди, пожалуйста помогите!
Вот пищу алгоритм реализующий задачу коммивояжере методом ветвей и границ. Во первых может кто знает где нить уже написанный есть, где можно его взять, может кто сам уже писал.... У меня проблема в месте где надо реализовать поиск контуров (циклов) которые надо исключить подставляя бесконечность в матрицу весов. Как определять эти переходы которые надо исключить.
Плиз, кто хоть чего то знает про это помогите.

Макс.

Здравствуйте, vmaxx, Вы писали:

V>Люди, пожалуйста помогите!
V>Вот пищу алгоритм реализующий задачу коммивояжере методом ветвей и границ. Во первых может кто знает где нить уже написанный есть, где можно его взять, может кто сам уже писал.... У меня проблема в месте где надо реализовать поиск контуров (циклов) которые надо исключить подставляя бесконечность в матрицу весов. Как определять эти переходы которые надо исключить.
V>Плиз, кто хоть чего то знает про это помогите.

V>Макс.

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

Здравствуйте, Sergey A. Sablin, Вы писали:

SA>Здравствуйте, vmaxx, Вы писали:

V>>Люди, пожалуйста помогите!
V>>Вот пищу алгоритм реализующий задачу коммивояжере методом ветвей и границ. Во первых может кто знает где нить уже написанный есть, где можно его взять, может кто сам уже писал.... У меня проблема в месте где надо реализовать поиск контуров (циклов) которые надо исключить подставляя бесконечность в матрицу весов. Как определять эти переходы которые надо исключить.
V>>Плиз, кто хоть чего то знает про это помогите.

V>>Макс.

SA>года 4 назад, в универе писал нечто подобное, разбираться что я там наделал времен нет, но работала точно.
SA>давай емайл, я тебе замылю.

Спасибо, что отозвался.
email: emaxim@hotbox.ru

Здравствуйте, vmaxx, Вы писали:

V>Люди, пожалуйста помогите!
V>Вот пищу алгоритм реализующий задачу коммивояжере методом ветвей и границ. Во первых может кто знает где нить уже написанный есть, где можно его взять, может кто сам уже писал.... У меня проблема в месте где надо реализовать поиск контуров (циклов) которые надо исключить подставляя бесконечность в матрицу весов. Как определять эти переходы которые надо исключить.
V>Плиз, кто хоть чего то знает про это помогите.

V>Макс.

как я понял, это делается следующим образом:
например, мы взяли дугу (x,y), тогда естественно надо исключить (y,x).
расширяя идею, если берем еще дугу (y,z), исключаем (z,y), потом соединяем с первым — (x,y,z) — естественно исключить (z,x). все.

Здравствуйте, ilnar, Вы писали:

I>Здравствуйте, vmaxx, Вы писали:

V>>Люди, пожалуйста помогите!
V>>Вот пищу алгоритм реализующий задачу коммивояжере методом ветвей и границ. Во первых может кто знает где нить уже написанный есть, где можно его взять, может кто сам уже писал.... У меня проблема в месте где надо реализовать поиск контуров (циклов) которые надо исключить подставляя бесконечность в матрицу весов. Как определять эти переходы которые надо исключить.
V>>Плиз, кто хоть чего то знает про это помогите.

V>>Макс.

I>как я понял, это делается следующим образом:
I>например, мы взяли дугу (x,y), тогда естественно надо исключить (y,x).
I>расширяя идею, если берем еще дугу (y,z), исключаем (z,y), потом соединяем с первым — (x,y,z) — естественно исключить (z,x). все.

Проблема в том, что на каждой итерации получающиеся дуги не последовательны и их порядок может быть произвольным. Например имеется 5 вершин, и получаются следующие вершины: (1,2) (2,3) (4,5) или может вот так: (1,2) (2,3) (4,1) или: (1,2) (4,5) (5,1) — это после трех итераций.
Ну ладно может и для 5 вершин можно написать алгоритм, но как написать общий алгоритм для произвольного числа вершин?