|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anton Kuznetsov 2:5030/566.13 03 Apr 2002 22:56:00
To : All
Subject : Комивояжор...
--------------------------------------------------------------------------------
Дана известная задача про комивояжора только конечная вершина любая. Веса на
ребрах натуральные...
Все бы хорошо, но ограничение по времени 10 секунд, а число вершин = 200.
Если писать вообще без отсечений то это примерно 2 в сотой...
Так вопрос: какие отсечения можно использовать чтоб оно уложилось в отведенное
ей время?
Стандартные отсечения про то, что
1) если мы еще не нашли путь, но его суммарная длина уже больше, чем длина
найденного пути, то вылетаем.
2) Если сейчас длина Х и мы не побывали еще в Р вершинах и Х+Р больше уже
найденной длины, то вылетаем (это потому, что каждое ребро весит хотя
бы 1).
не помогаю :-(
До свидания, All!
* Origin: ФТШ - лучше всех (2:5030/566.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
