|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Shmidt 2:464/34.74 04 Apr 2002 07:06:37
To : Anton Kuznetsov
Subject : Комивояжор...
--------------------------------------------------------------------------------
>< Е >< Е >< Хау, бледнолицый Anton! >< Е >< Е ><
(будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
Эй, уважаемые Anton Kuznetsov и All! Что за "Комивояжор...", а где же яйца?!
AK> Дана известная задача про комивояжора только конечная вершина любая.
AK> Так вопрос: какие отсечения можно использовать чтоб оно уложилось в
AK> отведенное ей время?
AK> 1) если мы еще не нашли путь, но его суммарная длина уже больше,
AK> чем длина найденного пути, то вылетаем.
Тут вся фишка в том, какой путь мы найдем при первой итерации. Поэтому можно
немного ускорить, если найти первый маршрут жадно, а уж потом пускать перебор.
Попробуй и напиши, как изменилось время работы. (Тада будем еще думать.)
AK> 2) Если сейчас длина Х и мы не побывали еще в Р вершинах и Х+Р
AK> больше уже найденной длины, то вылетаем (это потому, что каждое ребро
AK> весит хотя бы 1).
В общем случае - не 1, а длина минимального ребра. Попробуй, мож еще чего
выиграешь...
Good bye, mister Kuznetsov _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Я люблю только двух мужчин - себя и Даню Шеповалова!!!
--- А у твоего ГолДеда стоит... фильтрация мессаг???
* Origin: Что наша жизнь? Графический эффект... (с)
(2:464/34.74)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Комивояжор... 
