Re: Задача коммивояжёра

From

Sergey Radkevich ()

To

Dmitri Shankov

Date

2002-09-06T09:52:58Z

Area

RU.ALGORITHMS

From: "Sergey Radkevich" <sergeyr@moscow.vestedev.com>


>  AC> Кто-нибудь знает, сабж какой максимальной размерности берут сейчас
>  AC> компьютеры. И сколько на это времени уходит.
>  А в чём состоит собственно эта задача?

нахождение минимального по длине гамильтонова контура на графе

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

При количестве городов менее 6-8 можно решать полным перебором. Для этого
генерируются все перестановки из N чисел, вычисляется длина пути и
выбирается путь с минимальной длиной.

При количестве городов менее 30-50 (в зависимости от реализации) можно
применить метод ветвей и границ. Применить можно по-разному, например
алгоритм Литтла

Я знаю единственную реальную задачу, которая подходит именно под этот
случай. В ней требуется определить, в каком порядке следует объединять
аппаратуру в кольца в системах связи на базе синхронной цифровой иерархии.
По соображениям синхронизации в кольце не м.б. более 20 мультиплексоров
(~городов), а при одном из способов защиты - не более 16.

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



--- ifmail v.2.15dev5
 * Origin: Golden Telecom (2:5020/400)