[kita]

Здравствуйте, помогите разобраться.
Стандартная задача про коммивояжера, правда решить необходимо полным перебором.
Коммивояжер хочет объехать N городов и затем вернуться в начальный город,расстояния между которыми заданы. При этом желательно сделать это по наиболее короткому пути (т.к. коммивояжер не располагает лишними средствами на излишние перемещения между городами).
Данные ввела в стрингрид, правда, теперь запарялась с прямым перебором, не могу понять, как организовать перебор, чтоб города не повторялись?

[lmikle]

http://www.cyberforum.ru/delphi-begi...ead702300.html не подойдет?

[Alegun]

Сообщение от kita

...задача про коммивояжера, правда решить необходимо полным перебором...

А вот ещё один вариант с матрицами, работает на "жадном" алгоритме (полным перебором).

[M.A.D.M.A.N.]

Дак это ж дикость. Почему именно полным перебором?

[Alegun]

Я ошибся, поторопившись уровнять различные способы вычислений. Вот их определения

Жадный алгоритм

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность т.к. последним выпадает не всегда самый короткий путь. Но он работает и находит нужные комбинации, причём довольно быстро (самый быстрый алгоритм)

и

Полный перебор

Метод полного перебора заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной.

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

[M.A.D.M.A.N.]

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

Первоначально задача коммивояжера рассматривалась как математическая головоломка, но в последние десятилетия обнаружили, что к ней сводится ряд важных практических проблем. Например, если на одном оборудовании каждый месяц нужно производить фиксированную номенклатуру изделий, а затраты на переналадку зависят от предшествующего и последующего видов изделий, то определение последовательности запуска изделий в производство, обеспечивающей минимальные затраты на переналадку в течение месяца, представляет собой типичную задачу коммивояжера. Другой пример: составляется программа для станка с ЧПУ на сверление нескольких десятков отверстий в плате и требуется определить порядок, в котором будет производиться сверление, так, чтобы общее время операции было минимальным. Совершенно очевидно, что это тоже задача коммивояжера. В чем трудности решения таких задач, если число возможных вариантов всегда конечно? При трех городах имеется два варианта решения, при четырех - уже шесть, а при 11- более 3,6 млн. В общем случае задача коммивояжера с n городами (пунктами) имеет (-1)! замкнутых маршрутов, проходящих через все пункты. Таким образом, в реальных задачах число возможных вариантов исчисляется астрономическими величинами и в этом заключается основная проблема решения задачи.

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

Мы чето как-то быстро их решали.

[Pyro]

должен быть быстрый способ, раз им такие картинки создают http://www.flickr.com/photos/sbprzd/...57623709209312 http://www.flickr.com/photos/sbprzd/...7623709209312/
хотя если жадный алгоритм, то и не должен быть долгим