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

← →
XeN (2002-05-10 19:23) [0]

Кто нибуть занимался решением задач о коммивояжере? Обьясните что это такое и если можно, то дайте пример такой задачи с решением на TP or Delphi.

← →
pasha_golub (2002-05-11 14:36) [1]

дан набор городов с дорогами. Коммивояжеру нужно обойти все города по одному разу за наименьшее расстояние. Задача из области графов. Классного алгоритма нет, решается перебором.

← →
Desdechado (2002-05-11 15:47) [2]

уточнения:
1. в каждом городе только по одному разу
2. вернуться в исходную точку (не обязательно)
3. алгоритмы есть точные (метод ветвей и границ и пр.), есть приближенные (Greedy-эвристики). А перебор - не алгоритм.

← →
XeN (2002-05-11 20:18) [3]

Можно поподробнее?
Вот к примеру есть 5 городов (вершини графов), есть дороги (ребра графов). Только не очень понятно по какому принципу строятся дороги, от кахдого города к каждому (если 5 городов, то дорог - 8?)?
Если можно, то поподробнее о методе ветвей и границ...

!!! горю

← →
[NIKEL] (2002-05-11 20:59) [4]

поищи инфу о создании игр - алгоритмы движения, обхода препятствий, и прохождение от точки до точки выбирая лучший путь - там такие задачи как орешки щелкуют :) Это тебе поможет

← →
MacLeod (2002-05-12 11:52) [5]

Уважаемый XeN.
Я решал задачу о коммивояжоре. Для этого я использовал алгоритм с возвратом. Очень эффиктивный алгоритм. Для сравнения: при использовании полного перебора (рекурсивный) для решения этой задачи с 11-12 городами уходило 6-7 часов на 133-ем. Для 13 городов дождаться решения у меня не хватило терпения. Используя перебор с возвратом решение находилось за несколько секунд. Причем, по времени не было заметно сколько городов в задаче 5, или 15, или 25. И первая и вторая программы были написаны на Turbo Pascal 7.0.
Желаю успехов.

← →
MacLeod (2002-05-12 11:54) [6]

Прошу прощение за неграмотность. Конечно же эффективный, а не "эффиктивный"

← →
Desdechado (2002-05-12 14:55) [7]

1. дороги не строятся, они заданы априорно. А также стоимость проезда по ним (или длина, или время, или ...). Так по этому критерию и определяется лучший маршрут.
2. для некоторых исходных данных решения может не быть (см. задачу Эйлера о Кенигсбергских мостах)
3. поищи в сети описание алгоритма ветвей и границ.

и вообще: как ты собираешься решать задачу, не зная ее постановки, исходных данных, ограничений?

← →
Jedi (2002-05-12 23:24) [8]

Есть документ по методу ветвей и границ. Если нужен - обращайся.

← →
Gregory (2002-05-14 10:21) [9]

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

Постановка транспортной задачи.

Имеется m складов и n пунктов потребления: С(i),
i=1..m; П(j), j=1..n
На каждом складе имеется количество товара в запасе
a(i). Пункты потребления подали заявки на b(j) единиц
товара. Заявки выполнимы. Всякий склад связан с пунктами
потребления сетью дорог с определенным тарифом перевозок
C(i,j).
Требуется составить план перевозок, т.е. указать с
какого склада и в какие пункты какое количество товара нужно
направить, чтобы заявки были выполнены, а общие расходы на
все перевозки были бы минимальны.

← →
XeN (2002-05-15 20:11) [10]

2Gregory: мне товар не нужен :) в смысле это усложняет задачу... мне надо просто нахождение кратчайшего пути между городами с прилежащими дорогами. В принципе я нашел много интересного по методу ветвей и границ, но пока реализовывать не начинал... Эх, мож у кого уже есть :)))

← →
Mystic (2002-05-16 10:20) [11]

> Gregory (14.05.02 10:21)
> В исследовании операций это еще называется "Транспортной
> задачей" (по сути это один из частных случаев общей задачи
> линейного программирования).

Вообще-то задача коммивояжера и транспортная задача ЛП суть разные вещи.

← →
dron1 (2002-05-28 15:59) [12]

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

Задача о коммивояжере Найти похожие ветки