Коефіцієнт галуження (інформатика)

У теорії графів і структур даних коефіцієнт галуження дерева — кількість прямих нащадків у кожному вузлі. Якщо це значення не однакове для всіх вузлів, можна обчислити середній коефіцієнт галуження. У теорії ігор коефіцієнтом галуження гри називають коефіцієнт галуження дерева гри, тобто кількість можливих ходів у цій позиції.

Червоно-чорне дерево з коефіцієнтом галуження 2

У Вікіпедії є статті про інші значення цього терміна: Коефіцієнт галуження.

Наприклад, у шахах, якщо «вузлом» вважати допустиму позицію, середній коефіцієнт галуження буде близько 35.^[1][2] Це означає, що в середньому на кожному ході гравець має близько 35 ходів. Для порівняння, коефіцієнт галуження для гри ґо дорівнює 250.^[1]

Високі коефіцієнти галуження роблять алгоритми, які проходять за кожним можливим виходом із вузла, такі як повний перебір, обчислювально витратнішими через експоненційне зростання кількості вузлів, що відомо як комбінаторний вибух.

Наприклад, якщо коефіцієнт галуження дорівнює 10, то від поточної позиції на рівень нижче буде 10 вузлів, на два рівні нижче буде 10² (або 100) вузлів, на три рівні нижче буде 10³ (або 1000) вузлів, і так далі. Що більший коефіцієнт галуження, то швидше відбувається «вибух». Коефіцієнт галуження можна відсікати за допомогою алгоритму скорочення надлишковості^[en].

Див. також

• Ієрархія