В вычислениях , древовидных структурах данных и теории игр коэффициент ветвления — это число потомков в каждом узле , исходящая степень . Если это значение не является равномерным, можно вычислить средний коэффициент ветвления .
Например, в шахматах , если «узел» считается допустимой позицией, средний фактор ветвления, как говорят, составляет около 35, [1] [2] и статистический анализ более 2,5 миллионов игр показал среднее значение 31. [3] Это означает, что в среднем игрок имеет в своем распоряжении около 31-35 допустимых ходов на каждом ходу. Для сравнения, средний фактор ветвления для игры Го составляет 250. [1]
Более высокие коэффициенты ветвления делают алгоритмы, которые отслеживают каждую ветвь в каждом узле, такие как исчерпывающий поиск методом грубой силы , более затратными в вычислительном отношении из-за экспоненциально растущего числа узлов, что приводит к комбинаторному взрыву .
Например, если фактор ветвления равен 10, то на один уровень ниже текущей позиции будет 10 узлов, на два уровня ниже — 10 2 (или 100), на три уровня ниже — 10 3 (или 1000) узлов и т. д. Чем выше фактор ветвления, тем быстрее происходит этот «взрыв». Фактор ветвления можно сократить с помощью алгоритма обрезки .
Средний коэффициент ветвления можно быстро рассчитать как число некорневых узлов (размер дерева минус один или число ребер), деленное на число нелистовых узлов (число узлов с дочерними элементами).
Скорость, с которой увеличиваются возможные позиции, напрямую связана с «фактором ветвления» игры или средним числом ходов, доступных на каждом ходу. Фактор ветвления шахмат равен 35. Го — 250. Игры с высоким фактором ветвления делают классические алгоритмы поиска, такие как минимакс, чрезвычайно затратными.