|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anton Kuznetsov 2:5030/566.13 04 Apr 2002 23:13:00
To : Alexander Shmidt
Subject : Комивояжор...
--------------------------------------------------------------------------------
AK>> Дана известная задача про комивояжора только конечная вершина любая.
AK>> Так вопрос: какие отсечения можно использовать чтоб оно уложилось в
AK>> отведенное ей время?
AS>
AK>> 1) если мы еще не нашли путь, но его суммарная длина уже больше,
AK>> чем длина найденного пути, то вылетаем.
AS>
AS> Тут вся фишка в том, какой путь мы найдем при первой итерации. Поэтому
AS> можно немного ускорить, если найти первый маршрут жадно, а уж потом
AS> пускать перебор. Попробуй и напиши, как изменилось время работы. (Тада
AS> будем еще думать.)
Дык я его жадным и написал :)
AK>> 2) Если сейчас длина Х и мы не побывали еще в Р вершинах и Х+Р
AK>> больше уже найденной длины, то вылетаем (это потому, что каждое ребро
AK>> весит хотя бы 1).
AS>
AS> В общем случае - не 1, а длина минимального ребра. Попробуй, мож еще чего
AS> выиграешь...
Спасибо. Выиграл в 1,5 раза.
Время теперь примерно 15-20 минут для 100 вершин.
До свидания, Alexander!
* Origin: Ya! (2:5030/566.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Комивояжор... 