5.13. ЭФФЕКТИВНОСТЬ ПЕРЕБОРА ПРИ АЛЬФА-БЕТА ПРОЦЕДУРЕ
Для того чтобы можно было произвести отсечения, по крайней мере часть дерева перебора должна быть построена до максимальной глубины, поскольку предварительные обращенные величины должны основываться на статических значениях концевых вершин. Поэтому при использовании альфа-бета процедуры обычно прибегают к той или иной разновидности перебора в глубину. Число отсечений, возможных в процессе перебора, зависит от степени, в которой первые предварительные
величины аппроксимируют окончательные обращенные величины.
Окончательная обращенная величина для начальной вершины совпадает со статическим значением одной из концевых вершин. Если эту вершину можно достичь первой при переборе в глубину, то число отсечений будет максимальным. При максимальном числе отсечений требуется строить и оценивать минимальное число концевых вершин.
1 Пусть дерево имеет глубину 
и у каждой вершины (за исключением концевой) в точности В дочерних вершин. У такого дерева будет ровно 
концевых вершин. Предположим, что в альфа-бета процедуре дочерние вершины строятся в порядке, соответствующем их истинным обращенным величинам: для «ИЛИ» вершин строятся дочерние вершины с наибольшими значениями, а для вершин «И» — с наименьшими. (Конечно, эти обращенные величины в момент построения дочерних вершин, как правило, не известны, так что в действительности этот порядок никогда не достигается, разве что случайно.)
Оказывается, что такой порядок максимизирует число отсечений и минимизирует число построенных концевых вершин. Обозначим это минимальное число концевых вершин через 
Можно показать, что
Иными словами, число концевых вершин глубины 
которые будут построены при оптимальном альфа-бета переборе, примерно равно числу концевых вершин, которые были бы построены на глубине 
без альфа-бета процедуры. Таким образом, при тех же требованиях к памяти альфа-бета процедура с совершенным упорядочением дочерних вершин позволяет удвоить глубину перебора. Конечно, в задачах перебора невозможно добиться совершенного упорядочения (если бы это было возможно, то мы не нуждались бы ни в каком процессе перебора!), однако важно использовать наилучшую из имеющихся в нашем распрряжении функций упорядочения, поскольку это приносит большую потенциальную выгоду.
