В вычислении , древовидных структур данных и теории игр , то коэффициент ветвления является количество детей в каждом узле , то полустепень . Если это значение неоднородно, можно рассчитать средний коэффициент ветвления .
Например, в шахматах , если «узел» считается допустимой позицией, средний фактор ветвления, как утверждается, составляет около 35, [1] [2], а статистический анализ более 2,5 миллионов игр показал, что в среднем 31. [3] Это означает, что в среднем игрок имеет в своем распоряжении от 31 до 35 разрешенных ходов за каждый ход. Для сравнения, средний коэффициент ветвления для игры Go равен 250. [1]
Более высокие коэффициенты ветвления делают алгоритмы, которые следуют за каждой ветвью на каждом узле, такие как исчерпывающий поиск методом перебора , вычислительно более дорогостоящим из-за экспоненциально увеличивающегося числа узлов, что приводит к комбинаторному взрыву .
Например, если коэффициент ветвления равен 10, то будет 10 узлов на один уровень вниз от текущего положения, 10 2 (или 100) узлов на два уровня вниз, 10 3 (или 1000) узлов на три уровня вниз и т. Д. Чем выше коэффициент ветвления, тем быстрее происходит этот «взрыв». Коэффициент ветвления можно уменьшить с помощью алгоритма отсечения .
Средний коэффициент ветвления можно быстро вычислить как количество некорневых узлов (размер дерева минус один; или количество ребер), разделенное на количество нелистовых узлов (количество узлов с дочерними элементами).
Смотрите также
Рекомендации
- ^ a b Левиновиц, Алан (12 мая 2014 г.). «Тайна го, древней игры, в которой компьютеры до сих пор не могут выиграть» . Проводной . Проверено 2 июня 2014 .
Скорость увеличения возможных позиций напрямую связана с «фактором ветвления» игры или средним количеством ходов, доступных в любой данный ход. Коэффициент ветвления Chess равен 35. Go равен 250. Игры с высокими коэффициентами ветвления делают классические алгоритмы поиска, такие как минимакс, чрезвычайно дорогостоящими.
- ^ Лараме, Франсуа Доминик (6 августа 2000 г.). "Шахматное программирование. Часть IV: Базовый поиск" . GameDev.net . Проверено 1 мая 2007 .
- ^ Барнс, Дэвид. «Какое среднее количество разрешенных ходов за ход?» . Обмен шахматных стеков . Проверено 1 июня 2019 .