WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Красно-чёрное дерево с коэффициентом ветвления 2

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

Например, в шахматах, если «узлом» считается легальная позиция, средний коэффициент ветвления будет около 35[1][2]. Это значит, что в среднем игрок имеет около 35 допустимых ходов на каждом ходе. Для сравнения, коэффициент ветвления для игры Го равен 250[3].

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

Например, если коэффициент ветвления равен 10, то от текущей позиции на уровень ниже будет 10 узлов, двумя уровнями ниже будет 102 (или 100) узлов, тремя уровнями ниже будет 103 (или 1000) узлов, и так далее. Чем выше коэффициент ветвления, тем быстрее происходит «взрыв». Коэффициент ветвления может быть отсечён с помощью алгоритма сокращения избыточности[en].

См. также

Примечания

Литература

  • Alan Levinovitz. The Mystery of Go, the Ancient Game That Computers Still Can’t Win. Wired, 2014. — Май. Цитата: «Скорость роста возможных позиций игры находится в прямой зависимости от „коэффициента ветвления“, среднего числа ходов, возможных при каждом ходе. Коэффициент ветвления шахмат равен 35, в игре Го он равен 250. Игры с высоким коэффициентом ветвления делают классические алгоритмы типа минимакс крайне затратными.»
  • François Dominic Laramée. Chess Programming Part IV: Basic Search. GameDev.net, 2000. — Август.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии