|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Kazak 2:5020/400 16 Oct 2001 20:00:57
To : Andrey Tarasevich
Subject : Re: Коммивояжёры...
--------------------------------------------------------------------------------
Да, каждый из них должен описать цикл, таким образом, чтобы эти циклы
покрыли все вершины графа, и при этом сумма их длин была бы минимальной
(либо длина максимального цикла должна быть минимальной). Иметь общие
вершины и рёбра они могут. Hо двигаться одновременно по одной и той же
дороге (находиться в одной и той же точке) - им нельзя. Это связано с тем,
что задача решается для железнодорожного транспорта. Требуется также
определить необходимое (оптимальное) количество коммивояжёров. Для задачи
небольшой размерности, понятно, лучше использовать точные алгоритмы, а если
вершин много - эвристические (не гарантирующие нахождение точного минимума).
Спасибо, Андрей, что заинтересовался.
--- ifmail v.2.15dev5
* Origin: Rostov State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
