|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Radkevich 2:5020/400 06 Sep 2002 09:52:58
To : Dmitri Shankov
Subject : Re: Задача коммивояжёра
--------------------------------------------------------------------------------
> AC> Кто-нибудь знает, сабж какой максимальной размерности берут сейчас
> AC> компьютеры. И сколько на это времени уходит.
> А в чём состоит собственно эта задача?
нахождение минимального по длине гамильтонова контура на графе
гамильтонов контур - замкнутый путь, проходящий через каждую вершину
в точности один раз.
При количестве городов менее 6-8 можно решать полным перебором. Для этого
генерируются все перестановки из N чисел, вычисляется длина пути и
выбирается путь с минимальной длиной.
При количестве городов менее 30-50 (в зависимости от реализации) можно
применить метод ветвей и границ. Применить можно по-разному, например
алгоритм Литтла
Я знаю единственную реальную задачу, которая подходит именно под этот
случай. В ней требуется определить, в каком порядке следует объединять
аппаратуру в кольца в системах связи на базе синхронной цифровой иерархии.
По соображениям синхронизации в кольце не м.б. более 20 мультиплексоров
(~городов), а при одном из способов защиты - не более 16.
При большем количестве городов можно воспользоваться эвристическими
алгоритмами, но уже без гарантии оптимальности результата.
--- ifmail v.2.15dev5
* Origin: Golden Telecom (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
