|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 17 Oct 2001 14:08:03
To : Alexander Kazak
Subject : Re: Коммивояжёры...
--------------------------------------------------------------------------------
Tue Oct 16 2001 20:00, Alexander Kazak wrote to Andrey Tarasevich:
AK> Да, каждый из них должен описать цикл, таким образом, чтобы эти циклы
AK> покрыли все вершины графа, и при этом сумма их длин была бы минимальной
AK> (либо длина максимального цикла должна быть минимальной). Иметь общие
AK> вершины и рёбра они могут. Hо двигаться одновременно по одной и той же
AK> дороге (находиться в одной и той же точке) - им нельзя. Это связано с
AK> тем,
AK> что задача решается для железнодорожного транспорта. Требуется также
AK> определить необходимое (оптимальное) количество коммивояжёров. Для задачи
AK> небольшой размерности, понятно, лучше использовать точные алгоритмы, а
AK> если вершин много - эвристические (не гарантирующие нахождение точного
AK> минимума).
Если не ставится задача выровнять на них нагрузку - приходим к задаче о
назначениях. Решаемой венгерским методом за полиномиальное (и небольшое) время
точно.
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
