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