Конспект: ветви и границы

Понятия

Рекорд - лучшее найденное решение. Для максимума наибольшее, для минимума наименьшее.

Оценка (граница) - потолок достижимого в ветке: сверху для максимума, снизу для минимума.

Допустимая оценка - никогда не ошибается в опасную сторону: для максимума не меньше реально достижимого, для минимума не больше.

Релаксация (ослабление) - убрать требование задачи, решить что осталось, получить оценку.

Фронт открытых узлов - узлы, которые ещё предстоит раскрыть. У обхода в глубину это стек вызовов, у лучшего-первого - очередь с приоритетом по оценке.

Что унести

ВЕТВИ И ГРАНИЦЫ = поиск с возвратом + рекорд + оценка
    в каждом узле:  обновить рекорд, если решение допустимо
                    посчитать оценку ветки
                    отсечь, если оценка не лучше рекорда

максимум:  отсекаем при  оценка <= рекорд     (оценка сверху)
минимум:   отсекаем при  оценка >= рекорд     (оценка снизу)

Число узлов у сильной оценки почти не растёт с размером задачи - вот как выглядит хорошая граница. Ответы сверены с динамикой по вместимости: 420, 532, 675, 783.

ОТКУДА БЕРЁТСЯ ОЦЕНКА (ослабить = расширить множество решений)
целый рюкзак        → разрешить резать предметы      → жадность по цена/вес
коммивояжёр         → рёбра могут не быть путём      → сумма минимальных рёбер
коммивояжёр точнее  → убрать «степень каждого = 2»   → остовное дерево (МОД)
целые переменные    → разрешить дробные              → симплекс («релаксация»)
3 машины            → делить задачу между машинами   → max(объём/3, максимум)

несколько нижних оценок объединяются взятием НАИБОЛЬШЕЙ

ТОЧНОСТЬ ПРОТИВ ЦЕНЫ - ось, на которой выбирают оценку
оценка 0 ──────── ослабленная задача ──────── точный ответ
отсекает ничего      отсекает почти всё        отсекает всё
цена 0               O(1)...O(n) на узел       как вся задача
= полный перебор     рабочий метод             бессмысленно

Оценку надо пересчитывать инкрементно, а не заново: на шести городах версия «в лоб» оказалась дороже полного перебора.

ПОРЯДОК ОБХОДА
в глубину        память O(n), рекорд сразу, узлов чуть больше минимума
лучший-первый    узлов минимум, память под весь фронт; где частичное решение не ответ - ответа долго нет
                 (при допустимой оценке первый дошедший узел сразу оптимален = A*)
гибрид           спуск в глубину, кандидаты в порядке оценки ← обычный выбор
при ветвлении 2  гибрид = «пробуем сначала ветку с лучшей оценкой»

Ловушки джокера

Недопустимая оценка. Занижает потолок - отсекает ветку с оптимумом. Ответ есть, он просто хуже настоящего: 670 вместо 675 на одном наборе из четырёх. Проверять сравнением с полным перебором или с динамикой на малых данных.

Забыл сортировку в дробной оценке. Для рюкзака это условие ПРАВИЛЬНОСТИ, а не скорости: без сортировки по удельной цене ответы ломаются на всех размерах - 355 вместо 420, 700 вместо 783.

Перепутал направление. Для минимума нужна оценка снизу и сравнение >=, для максимума - сверху и <=. Ошибка в знаке отсекает оптимум.

Оценка дороже, чем экономит. Цена оценки умножается на число узлов. Замер: оценка «в лоб» на шести городах - 15 264 шага против 5387 у полного перебора.

Рекорд обновляется только на дне. В рюкзаке частичный набор - уже допустимое решение; обновляя рекорд в каждом узле, отсечения включаются раньше.

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

Фронт лучшего-первого как список с линейным поиском максимума. На десятках тысяч узлов выбор максимума становится главной статьёй расходов. Нужна очередь с приоритетом.

Не проверил оценку узла при извлечении из фронта. Пока узел лежал, рекорд вырос - узел уже бесперспективен.

Ждёшь гарантии от жадного старта. На одном наборе он свёл дерево к одному узлу, на трёх других не сэкономил ничего. При обходе в глубину с ветвью «берём» первой первый спуск и ЕСТЬ жадное решение, поэтому старт экономит ровно его.

Куда это ведёт

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