Б*

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

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

Краткое содержание

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

Подробности

Интервальные оценки, а не оценки

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

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

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

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

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

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

Расширение

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

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

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

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

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

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

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

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

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

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

Надежность

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

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

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

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

Приложения

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

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

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

См. также

• Ветвь и граница

Ссылки

• Берлинер, Ганс (1979). «Алгоритм поиска в B*-дереве. Процедура доказательства по принципу наилучшего первого» (PDF) . Искусственный интеллект . 12 (1): 23–40. дои : 10.1016/0004-3702(79)90003-1 . Архивировано из оригинала 27 сентября 2017 г. Проверено 29 апреля 2018 г.
• Рассел, С.Дж.; Норвиг, П. (2003). Искусственный интеллект: современный подход . Река Аппер-Сэдл, Нью-Джерси: Прентис-Холл. п. 188. ИСБН  0-13-790395-2 .
• Шеппард, Брайан (2002). «Эрудит уровня чемпионата мира». Искусственный интеллект . 134 (1–2): 241–275. дои : 10.1016/S0004-3702(01)00166-7 .