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

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

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

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

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

• Ієрархія

• Alan Levinovitz. The Mystery of Go, the Ancient Game That Computers Still Can’t Win. — Wired, 2014. — May. Процитовано 2014-06-02. Цитата: «Швидкість зростання можливих позицій гри прямо залежить від „коефіцієнта галуження“, середньої кількості ходів, можливих за кожного ходу. Коефіцієнт галуження шахів дорівнює 35, у грі ґо він дорівнює 250. Ігри з високим коефіцієнтом галуження роблять класичні алгоритми типу мінімакс украй витратними.»
• François Dominic Laramée. Chess Programming Part IV: Basic Search. — GameDev.net, 2000. — August. Процитовано 2007-05-01.