Задача Коммивояжера С Фиксированным Стартом И Финишем

[nuke4303]

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

 

[rrrFer]

2 раза по одной дуге ходить можно?

Зачем искать алгоритм, когда можно составить самому?

 

[nuke4303]

Ходить то можно, но будет ли это оптимальный путь....
Придумать тоже можно, но это будет перебор...который для 20-30 вершин будет пол дня наверно все комбинации проверять..

 

[ixoyz]

Ходить то можно, но будет ли это оптимальный путь....

А оптимальный путь обязателен? Если нет и можно по одной дуге несколько раз ходить, можно просто сделать обход графа в глубину (или взять готовый алгоритм задачи коммивояжера с фиксированым стартом) и в конец маршрута добавить путь до заданной конечной точки (взять из того же обхода графа). Решение конечно не оптимальное, но зато просто реализуется и задачу решает.

 

[asSerega]

Зачем искать алгоритм, когда можно составить самому?

Ну-ну. Судя по твоему вопросу у тебя это получится

nuke4303, если длины ребер заданы однозначно попробуй поискать метод Кларка-Райта (это математический точный метод, прогу составить просто). Если длина ребер может изменятся, попробуй метод муравьиных колоний (он приближенный). Если сам не справишься, готов сделать за вознаграждение. Пиши algoritmer@yandex.ru