5.6.3 Метод ветвей и границ

Перебор, который осуществляет поиск с возвратом, можно уменьшить, используя идею метода «ветвей и границ». Эта идея состоит в том, что можно не искать точную оценку хода, про который стало известно, что он не может быть лучше, чем один из ходов, рассмотренных раньше. Пусть, например, в процессе перебора стало известно, что f(p₁) = -10. Отсюда заключаем, что f(p)  10, и потому не нужно знать точное значение f(p₂), если каким-либо образом узнали, что f(p₂)  -10 (поскольку отсюда следует, что -f(p₂)  10). Итак, если p₂₁ допустимый ход из p₂ и f(p₂₁)  10, можно не исследовать другие ходы из p₂. Говорят, что ход в позицию p₂ «опровергается» (ходом в p₁), если у противника в позиции p₂ есть ответ, по крайней мере, столь же хороший, как его лучший ответ в позиции p₁. Ясно, что если ход можно опровергнуть, можно не искать наилучшее опровержение.

Эти рассуждения приводят к методу «ветвей и границ», гораздо более экономному, чем поиск с возвратом. Определим метод «ветвей и границ» как процедуру с двумя параметрами p и bound, вычисляющую f’(p, bound). Цель алгоритма – удовлетворить следующим условиям:

f’(p, bound) = f(p), если f(p) < bound,

f’(p, bound) > bound, если f(p)  bound.

Идею метода ветвей и границ реализует следующий алгоритм.

function B&B(p: position, bound: integer): integer;

{оценивает и возвращает выигрыш F’(p) для позиции p}

label done;

var

m,i,t,d: integer;

begin

Определить позиции p1,...,pd, подчиненные p;

if d = 0 then B&B := f(p) else begin

m := -;

for i:= 1 to d do begin

t := - B&B(pi, -m);

if t > m then m := t;

if m >= bound then goto done;

end;

done: B&B := m;

end;

end;

Листинг 5.17 – Алгоритм, использующий метод ветвей и границ