B * - B*

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

Резюме

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

Подробности

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

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

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

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

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

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

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

Расширение

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

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

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

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

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

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

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

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

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

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

Надежность

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

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

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

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

Приложения

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

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

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

Смотрите также

Ветвь и переплет