Главная

Случайный

Главная
Комми
Алгоритм
Быстрый
Средний
Случайный
Точный
Новый
Эксперимент

Карта

Случайный поиск




Назад...   Далее...

При поиске точного решения крайне желательно, чтобы оно уже лежало в текущем туре, чтобы не столько искать его, сколько доказывать оптимальность существующего. Да, у нас после отработки второго алгоритма погрешность составляет всего лишь единицы процентов, но для поиска оптимального тура это очень большая величина, многократно увеличивающая трудоёмкость расчётов. Да, экпериментальные прогоны на небольших графах показали, что уже первый каскад рекурсивного алгоритма обычно укладывает бета-границу в доли процента, но трудоёмкость даже первого каскада во много раз превышает затраты на все предыдущие расчёты.

Что же делать? Подумаем... обычно погрешность составляет 3-5%, понижать её нужно при жёстких временных (не более 30-40% ожидаемой трудоёмкости первого каскада) и, соответственно, технологических ограничениях (не более облегчённого "моста", и никакой рекурсии). И всё же основания для оптимизма есть: за редчайшим исключением, при ошибке в несколько процентов локальные минимумы ещё неустойчивые - достаточно хоть немного "спихнуть" с него тур, и бета-граница тут же падает на процент-другой. Как именно спихнуть? Видимо, есть только один реальный способ: "взлохматить" разворотом несколько случайных рёбер, объявить их "новыми", и произвести "добор" (запомнив, на всякий случай, текущий тур). Сколько? Немного, только чтобы "спихнуть" - иначе возможный выигрыш в одном месте с большой вероятностью "компенсируется" проигрышем в другом. Пожалуй, от одного до четырёх "разворотов", да и то с понижением вероятности. Сколько раз "бросать монету"? Тоже немного: это всё-таки авантюра, поиск решения "на авось". Скажем, 1000 раз - "добор" работает быстро, и даже в случае полной неудачи потери времени будут относительно небольшими. Когда? Однозначно, только перед точным алгоритмом: и скоростной, и средний и так неплохо справляются с погрешностью, а на точном "халява" уже не пройдёт.

Неожиданно этот подход показал невероятно высокую эффективность: best-known решения посыпались, как из рога изобилия, да и в остальных случаях бета-граница резко упала. Похоже, неустойчивость локальных минимумов распространяется на ошибки в десятые или даже сотые доли процента. Что же, случайный поиск явно заслужил право быть включённым в общую технологию.

Итак, скорость - великолепная, точность - прекрасная, т.е. наш алгоритм явно становится конкурентоспособным с самыми лучшими эвристическими алгоритмами. Словно в насмешку над приблизительно такими мыслями авторов, алгоритм начинает "тормозить". Впервые не удалось найти точное решение (krob150), ошибка превысила 0.1% (qa194), 1% (rat575), 2% (rl1889), 3% (pcb3038), наконец, решения вообще исчезли (rl5915). "Задним умом" понимаем - с увеличением числа узлов длинные рёбра (скажем, через весь граф) вызывают лавину новых рёбер при "доборе", и эти искажения тура "топят" любую возможную находку. Ставим ограничение: чем длиннее ребро, тем ниже вероятность, что оно будет использовано для искажения тура. Ура! Заработало! И на маленьких графах по-прежнему решения появляются, и на больших всё хорошо. Всё, большего от случайного поиска и требовать нельзя: бета-граница падает ещё на несколько процентов за вполне терпимое время вычислений.

К сожалению, эффективность случайного поиска резко падает с ростом числа узлов. Причины этого понятны: поверхность отклика становится всё более сложной, и мы, сохраняя способность сшибать на ней мелкие "кочки", практически утрачиваем возможность выбраться из более крупных "ям", требующих одновременной замены сколько-нибудь значительного числа рёбер. Заметно растут накладные расходы: при удаче мы изменяем, как правило, очень небольшой участок тура, но сохранять (и восстанавливать) приходится весь тур. Наконец, на небольших графах "добежать" до best-known можно буквально за несколько модификаций, а для более тяжёлых количество (удачных!) изменений тура составляет многие сотни и тысячи. Таким образом, рекомендовать этот алгоритм можно лишь с оговорками: до тысячи узлов он более, чем эффективен, до десяти тысяч тоже окажется полезен, да и до ста тысяч наверняка что-то найдёт (хотя время вычислений начинает уже серьёзно раздражать), до миллиона его могут использовать разве что мазохисты, а после миллиона это уже просто издевательство над компьютером!

Ну вот и всё: программное обеспечение для решения задачи коммивояжёра фактически написано: для практического получения качественных туров за приемлемое время больше вряд ли что можно придумать - разве что всё ту же "геометрию", которую мы принципиально не используем. А мы займёмся, наконец, поисками точного решения.
Назад...   Далее...

28.04.2016 21:54
 
`