WikiDer > Фактор ветвления

Branching factor
А красно-черное дерево с фактором ветвления 2.

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

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

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

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

Средний коэффициент ветвления можно быстро вычислить как количество некорневых узлов (размер дерева минус один; или количество ребер), разделенное на количество нелистовых узлов.

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

Рекомендации

  1. ^ а б Левиновиц, Алан (12 мая 2014 г.). «Тайна го, древней игры, в которой компьютеры все еще не могут выиграть». Проводной. Получено 2014-06-02. Скорость увеличения возможных позиций напрямую связана с «фактором ветвления» игры или средним количеством ходов, доступных в любой данный ход. Коэффициент ветвления Chess равен 35. Go равен 250. В играх с высокими коэффициентами ветвления используются классические алгоритмы поиска, например минимакс чрезвычайно дорого.
  2. ^ Лараме, Франсуа Доминик (6 августа 2000 г.). "Шахматное программирование. Часть IV: Базовый поиск". GameDev.net. Получено 2007-05-01.
  3. ^ Барнс, Дэвид. «Какое среднее количество разрешенных ходов за ход?». Обмен шахматных стеков. Получено 2019-06-01.