Порядок обхода: в глубину или лучший-первый

Коротко

У ветвей и границ есть второе решение помимо оценки - в каком порядке брать открытые узлы. Обход в глубину хранит только путь (O(n) памяти) и быстро находит первый рекорд. Лучший-первый всегда берёт узел с самой высокой оценкой и раскрывает меньше узлов - но держит в памяти целый фронт, а в задачах, где недостроенное решение ответом не является, до самого конца может не иметь ни одного решения. Замер на рюкзаке: в глубину 23-61 узел и 598-1677 шагов, лучший-первый 15-45 узлов, но 1095-3315 шагов и до 17 узлов в памяти. Это тот же приём, что A* из раздела 11, и требование к оценке там и здесь одно и то же.

Если ты знаешь разницу между обходом в глубину и лучшим-первым по памяти и по числу раскрытых узлов и помнишь, что это A\* другими словами, - листай до «Теперь сам».

Как думаешь, что выгоднее - идти вглубь или идти в лучшее

Оценка у нас есть, рекорд есть. Теперь представь, что в какой-то момент перебора известны три нераскрытых узла с оценками 780, 640 и 500. Какой раскрывать следующим?

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

На что это похоже

Поиск пропавшей вещи в квартире. Обход в глубину - это «начал с одного ящика комода и выпотрошил его до дна, потом следующий». Лучший-первый - это «обошёл все комнаты, оценил, где вероятнее всего, и копаю там; если стало менее вероятно - перехожу в другое место».

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

Механизм: фронт открытых узлов

ОБХОД В ГЛУБИНУ (стек, он же стек вызовов рекурсии)
память:    O(глубины) = O(n) - только текущий путь
рекорд:    появляется СРАЗУ, на первом же дошедшем до дна пути
отсечение: сравнивает с рекордом, который уже есть
узлов:     больше минимума - часть веток раскрывается до того,
           как рекорд стал хорошим

ЛУЧШИЙ-ПЕРВЫЙ (очередь с приоритетом по оценке)
память:    O(размера фронта) - в худшем случае экспоненциальная
рекорд:    там, где недостроенное решение - не ответ, может не появиться
           почти до конца: раскрываются узлы с лучшей ОЦЕНКОЙ,
           а не те, что ближе к листу
отсечение: сильнее - узел с оценкой хуже рекорда вообще не доживает
           до раскрытия
узлов:     минимум возможного при данной оценке

Ключевое свойство лучшего-первого стоит проговорить отдельно. Если оценка допустима, то первый ДОШЕДШИЙ ДО КОНЦА узел сразу оптимален: у всех остальных открытых узлов оценка не выше, а получить больше собственной оценки не может ни один из них - в этом и состоит допустимость. То есть лучший-первый не нуждается в доказательстве «а дальше лучше не станет» - он получает его бесплатно из порядка обхода. Это буквально A* из раздела 11, где оценка остатка называлась эвристикой h, а требование к ней - допустимостью.

Правило

Обход в глубину тратит O(n) памяти, немедленно даёт первый рекорд и потому годится всегда; лучший-первый раскрывает минимально возможное число узлов, но хранит целый фронт и может долго не иметь ни одного решения. Выбор между ними - это выбор между памятью и числом узлов, и на практике чаще берут гибрид: обход в глубину, в котором КАНДИДАТЫ на каждом уровне отсортированы по оценке - «лучший первым». Это даёт хороший рекорд рано, сохраняя память O(n). У лучшего-первого есть и скрытая цена реализации: выбрать максимум из фронта надо дёшево, иначе каждый шаг стоит O(размера фронта) - на замере это дало двукратный проигрыш по шагам при меньшем числе узлов.

Разбор: лучший-первый на рюкзаке, замер по трём величинам

Фронт - список узлов [оценка, номер предмета, вес, цена]. На каждом круге выбираем узел с наибольшей оценкой, раскрываем, двух детей кладём во фронт - но только если их оценка выше рекорда:

otkrytye = [[ocenka(0, 0, 0), 0, 0, 0]]
rekord = 0
while len(otkrytye) > 0:
    luchshij = 0
    k = 1
    while k < len(otkrytye):                 # выбор максимума: O(фронта)
        if otkrytye[k][0] > otkrytye[luchshij][0]:
            luchshij = k
        k = k + 1
    uzel = otkrytye[luchshij]
    otkrytye[luchshij] = otkrytye[len(otkrytye) - 1]
    otkrytye.pop()
    if uzel[0] <= rekord:
        continue                             # оценка устарела: рекорд вырос
    i = uzel[1]
    v = uzel[2]
    c = uzel[3]
    if i == len(ves):
        continue                             # предметы кончились, раскрывать нечего
    if v + ves[i] <= C:                      # ребёнок «взять предмет»
        if c + cena[i] > rekord:
            rekord = c + cena[i]             # набор допустим - пробуем в рекорд
        o = ocenka(i + 1, v + ves[i], c + cena[i])
        if o > rekord:
            otkrytye.append([o, i + 1, v + ves[i], c + cena[i]])
    o = ocenka(i + 1, v, c)                  # ребёнок «не брать»
    if o > rekord:
        otkrytye.append([o, i + 1, v, c])
print(rekord)

Две строки после выбора максимума - обычный приём удаления из середины списка, когда порядок не важен: на место выбранного узла переставляют последний и снимают хвост через pop(). Это одна операция вместо сдвига всех следующих элементов, и работает она и тогда, когда выбранный узел сам последний: он записывается на своё же место и снимается.

Цикл идёт до пустого фронта, а не до первого дошедшего узла, но лишней работы в этом нет: как только рекорд сравнялся с оптимумом, все оставшиеся узлы отбрасываются проверкой при извлечении, не раскрываясь.

Замер на тех же данных, что в прошлом уроке. «Узлов» - сколько узлов РАСКРЫТО, «во фронте» - сколько максимум лежало в памяти одновременно:

предметов   в глубину                лучший-первый
15          23 узла,    598 шагов    15 узлов, 1 095 шагов, во фронте 7
20          61 узел,  1 346 шагов    45 узлов, 3 315 шагов, во фронте 12
25          52 узла,  1 573 шага     23 узла,  2 828 шагов, во фронте 15
30          35 узлов, 1 677 шагов    20 узлов, 3 114 шагов, во фронте 17

Ответы совпадают: 420, 532, 675, 783. А вот выводы из таблицы расходятся в разные стороны.

По узлам лучший-первый выигрывает всегда и заметно - от 1,4 раза на двадцати предметах до 2,3 на двадцати пяти. По шагам он проигрывает тоже всегда: в 1,8-2,5 раза. Причина видна в коде: выбор максимума - это цикл по всему фронту, и он выполняется на каждом круге. Если заменить список на очередь с приоритетом из раздела про кучи, цена выбора станет O(log k) вместо O(k), и часть проигрыша исчезнет - но не весь: узлы во фронте надо хранить целиком, со всем состоянием, а в обходе в глубину состояние лежит в стеке вызовов и ничего не копируется.

Разбор: когда лучший-первый долго не имеет ответа

Сначала - когда этой беды НЕТ, и это как раз наш рюкзак. В рюкзаке недостроенный набор уже допустимое решение, поэтому рекорд у лучшего-первого растёт с первого же раскрытия. На двадцати пяти предметах оценка корня равна 676, оптимум 675, и рекорд по ходу раскрытий шёл так: 68, 117, 204, 231 и дальше до 668 после тринадцатого узла, а 675 появилось на последнем, двадцать третьем. Первые тринадцать шагов - тот же жадный спуск, что у обхода в глубину: у ребёнка «взять» оценка совпадает с родительской, она остаётся лучшей во фронте, и лучший-первый сам идёт вниз.

Беда начинается в задачах, где недостроенное решение ответом НЕ является. Маршрут коммивояжёра, пока он не замкнут, - не маршрут; расписание, в котором расставлена половина занятий, - не расписание. Там рекорд появляется, только когда какой-то узел дойдёт до дна, а лучший-первый на дно не торопится: у коротких недостроенных маршрутов оценка снизу меньше, они выглядят самыми перспективными, и он прыгает между неглубокими узлами. Пока он это делает, НИ ОДНОГО готового решения у него нет.

Чем это плохо практически: если программу прервать по тайм-ауту, обход в глубину отдаст хоть какой-то ответ (у него рекорд есть с первого пути до дна), а лучший-первый в такой задаче - ничего. Поэтому в реальных решателях почти всегда работает гибрид: порядок обхода определяется оценкой, но вниз спускаются сразу, чтобы быстро получить допустимое решение и начать отсекать.

anytime-поведение (что отдадим, если прервут)
в глубину        есть ответ почти сразу, он улучшается со временем
лучший-первый    если недостроенное решение не ответ - до первого
                 дошедшего узла ответа нет вовсе
гибрид           ответ сразу + порядок по оценке

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

Что ломается без этого

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

Второе: забыть проверить оценку узла при извлечении. Узел лёг во фронт с оценкой 780, пока рекорд был 700; к моменту извлечения рекорд стал 783. Если не проверить оценку ещё раз, узел будет раскрыт напрасно. Именно для этого в коде стоит if uzel[0] <= rekord: continue.

Третье: хранить во фронте ссылку на общее изменяемое состояние. В обходе в глубину можно было держать один массив занятости и откатывать его. В лучшем-первом так нельзя: узлы раскрываются не в порядке спуска, и состояние каждого надо хранить ЦЕЛИКОМ. Это ещё одна причина, по которой фронт дорог по памяти.

Четвёртое: ждать, что лучший-первый всегда дешевле. По узлам - да, по шагам и памяти - нет. Замер выше: узлов меньше в полтора-два раза, шагов больше примерно вдвое.

Пятое: сортировать кандидатов по оценке и не проверять, что это окупилось. В гибридном варианте сортировка b кандидатов на каждом уровне стоит b·log b на узел. Если ветвление маленькое (как в рюкзаке - всего две ветки), сортировать нечего: достаточно выбрать, какую ветку пробовать первой.

Зачем это в работе

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

Второй - планировщики и маршрутизаторы. A* в навигаторе - это лучший-первый из этого урока; он хранит фронт и потому требует памяти, пропорциональной площади обследованной области. Отсюда и приёмы вида «поиск с ограничением памяти», где фронт подрезают.

Третий - разговор про «а что, если прервать». Требование «дай лучшее, что успел» - это требование anytime-поведения, и оно прямо диктует порядок обхода: в глубину или гибрид, но не чистый лучший-первый.

Теперь сам

У задачи ветвление два (взять предмет или нет) и сильная оценка. Какой порядок обхода выбрать и почему гибрид в этом случае вырождается в одно простое правило?

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

ветвление 2 → сортировать нечего, выбор из двух
ветка «взять»    оценка обычно выше: самый выгодный предмет
ветка «не брать» оценка ниже - её и откладываем
⇒ в глубину, сначала «взять», память O(n), рекорд появляется сразу

Именно так и написан перебор из прошлого урока - там строка rec(i + 1, v + ves[i], c + cena[i]) стоит ПЕРВОЙ, и это не случайность: рекорд от жадного спуска появляется на первом же пути до дна, и дальше отсечения работают уже с ним. Поменяй эти две строки местами - и первым найдётся пустой рюкзак с ценой нуль, а рекорд будет расти медленно.

Главное

Порядок обхода - второе решение ветвей и границ после оценки, и выбирается он не по красоте, а по трём величинам: память, число раскрытых узлов и наличие ответа при досрочной остановке. Обход в глубину: память O(n), рекорд сразу, узлов чуть больше минимума. Лучший-первый: узлов минимум возможного (и первый дошедший до конца узел сразу оптимален - это A* из раздела 11), но память под весь фронт, а там, где недостроенное решение ответом не является, до самого конца может не быть ни одного решения. Замер на рюкзаке: у лучшего-первого узлов меньше в полтора-два раза, шагов больше примерно вдвое, во фронте до 17 узлов. На практике берут гибрид - спуск в глубину, но кандидаты в порядке оценки; при ветвлении два это сводится к одному правилу «сначала пробуем ветку с лучшей оценкой», и именно поэтому в рюкзаке строка «взять предмет» стоит первой.