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