Алгоритм поиска B*

Эта статья — об алгоритме поиска по графу. О варианте B-дерево см. B*-дерево.

В информатике B* (произносится как "Би стар") — это алгоритм поиска по графу, использующий поиск по первому наилучшему совпадению, который находит наименее затратный путь от заданного начального узла до любого целевого узла (из одной или нескольких возможных целей). Впервые опубликованный Хансом Берлинером в 1979 году, он связан с алгоритм поиска A*.

Резюме

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

Подробности

Интервалы скорее, чем оценки

Конечным узлам B*-дерева даются оценки, которые являются интервалами, а не отдельными числами. Предполагается, что интервал содержит истинное значение этого узла. Если все интервалы, прикреплённые к листовым узлам, удовлетворяют этому свойству, то B* определит оптимальный путь к состоянию цели.

Процесс резервного копирования

Для резервного копирования интервалов в дереве верхняя граница предка устанавливается равной максимуму верхних границ потомков. Нижняя граница предка устанавливается равной максимуму нижней границы потомков. Обратите внимание, что эти границы могут быть предоставлены разными потомками.

Прекращение поиска

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

На практике сложные поиски могут не завершиться в рамках практических ограничений ресурсов. Таким образом, алгоритм обычно дополняется критериями искусственного завершения, такими как ограничения по времени или памяти. Когда достигнут искусственный предел, надо сделать эвристическое суждение о том, какой ход выбрать. Обычно дерево предоставляет обширные доказательства, такие как интервалы корневых узлов.

Расширение

B* — это процесс поиска по первому наилучшему совпадению, что означает, что он очень эффективен при обходе дерева, многократно опускаясь вниз, чтобы найти лист, который нужно раскрыть. В этом разделе описывается, как выбрать узел для раскрытия. (Примечание: Является ли дерево резидентным в памяти, зависит от общей эффективности реализации, включая то, как оно может отображаться и/или управляться через реальную или виртуальную память.)

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

Стратегия опровергнуть остальное выбирает потомка корня, который имеет вторую по высоте верхнюю границу. Есть надежда, что, расширив этот узел, можно уменьшить верхнюю границу до значения, которое меньше, чем нижняя граница лучшего потомка.

Выбор стратегии

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

В исходном описании алгоритма не было никаких дополнительных указаний относительно того, какую стратегию выбрать. Есть несколько разумных альтернатив, например, расширение выбора с меньшим деревом.

Выбор стратегии на некорневых узлах

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

Когда достигается листовой узел, алгоритм генерирует все последующие узлы и назначает им интервалы, используя функцию оценки. Затем необходимо выполнить резервное копирование интервалов всех узлов с помощью операции резервного копирования.

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

Надёжность

Если интервалы неверны (в том смысле, что теоретико-игровое значение узла не содержится в интервале), то B* может быть не в состоянии определить правильный путь. Однако на практике алгоритм довольно устойчив к ошибкам.

В программе Maven есть нововведение, которое повышает надежность B*, когда возможны ошибки оценки. Если поиск прекращается из-за разделения, Maven перезапускает поиск после небольшого расширения всех интервалов оценки. Эта политика постепенно расширяет дерево, в конечном итоге стирая все ошибки.

Расширение для игр с двумя игроками

Алгоритм B* применяется к детерминированным играм с нулевой суммой для двух игроков. Фактически, единственное изменение — это интерпретация наилучшего по отношению к стороне, движущейся в этом узле. Таким образом, вы должны взять максимум, если ваша сторона движется, и минимум, если движется противник. Точно так же вы можете представить все интервалы с точки зрения стороны, которую нужно переместить, а затем инвертировать значения во время операции резервного копирования.

Приложения

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

Программа Maven применила поиск B* к эндшпилю. Оценки конечных точек были назначены с использованием системы эвристического планирования.

Алгоритм поиска B* использовался для вычисления оптимальной стратегии в игре с суммой набора комбинаторных игр.

См. также

• Метод ветвей и границ

Ссылки

• Berliner, Hans. The B∗ tree search algorithm: A best-first proof procedure (англ.) // Artificial Intelligence : journal. — Elsevier, 1979. — May (vol. 12, iss. 1). — P. 23–40. — ISSN 0004-3702. — doi:10.1016/0004-3702(79)90003-1.
• Stuart J. Russell, Peter Norvig. Artificial Intelligence: A Modern Approach (англ.). — 2nd ed. — Upper Saddle River, N.J.: Prentice Hall, 2003. — P. 188. — ISBN 0-13-790395-2.
• Брайан Шеппард (2002). "Мировой чемпионат по игре в скрэббл". Artificial Intelligence. 134 (1–2): 241—275. doi:10.1016/S0004-3702(01)00166-7.