В * - B*

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

Резюме

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

Подробности

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

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

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

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

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

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

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

Расширение

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

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

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

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

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

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

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

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

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

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

Надежность

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

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

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

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

Приложения

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

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

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

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

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

Languages

In other projects