ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Sundeev 2:50/383.21 27 May 2002 23:36:19
To : Vitaly Slobodskoy
Subject : Re^2: решение задачи коммивояжера методом ветвей и границ
--------------------------------------------------------------------------------
on *19.05.02* *21:09:01* you wrote in the area *RU.ALGORITHMS*
a message to *Sergey Sundeev*
about *"Re: решение задачи коммивояжера методом ветвей и границ"*.
VS> Из курса "Математические основы информатики":
VS> Решение задачи коммивояжера Методом Ветвей и Границ (МВГ).
VS> Все, теперь решаем задачу МВГ, т.к. все процедуры этого метода ясны.
VS> Если что-то неясно с самим МВГ - пиши...
Интересно а есть програмная реализация данного алгоритма?
В сети нашел программу реализующую данный алгоритм
В исходных данных задается размерность квадратной матрицы допустим 3 далее
определяется матрица вида
0 1 2
1 0 3
2 3 0
Hасколько я понял числа в матрице задают расстояния от точек от //1// к //2//
=> *1*
от //1// к //3// => *2* от //2// к //1// => *1* от //2// к //3// => *3* и т.д.
Hо кажется я ошибаюсь.
Задача состоит в том что имеется n точек необходимо найти наиболее короткий
путь от точки 1 к точке n.
Hадо для обхода отверстий сверлильным станком для минимизации холостых
перемещений причем
после обработки последнего отверстия надо переместится в точку 1.
Bye ..
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: Я не тормоз, я медленный газ! (2:50/383.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
