2018-01-08
689
Приведенная нами в подразделе 2.1 схема алгоритма довольно проста, однако она обычно неприемлема для реализации. Действительно, вложенные друг в друга циклы – очень жесткая структура и если нам надо решать задачу для 100 ферзей, то нам придется писать 100 вложенных друг в друга циклов. Более того, для каждого n нам придётся писать свой вариант алгоритма, отличающийся количеством вложенных циклов. Поэтому вариант с вложенными циклами обычно бывает неприемлемым для реализации перебора с возвратом. В книге [2] приведён алгоритм перебора с возвратом основанный на интерпретации перебора как последовательности переходов вперед-назад. Мы сейчас приведем схему алгоритма перебора с возвратом, построенную на принципах структурного программирования (т.е. без переходов) с использованием рекурсии.
Посмотрим на текст алгоритма. Сам текст алгоритма рекурсивен! Текст для n=k состоит из текста для n=k- 1, помещённого в цикл. Таким образом, алгоритм легко переписать в рекурсивном виде. Сначала мы приведём рекурсивный вариант алгоритма полного перебора.
procedure полный_перебор(m: integer); var i: integer; begin if m > n then <проверка построенной позиции> else for i:= 1 to n do begin ферзь[m]:= i; полный_перебор(m+1); end ; end ;Теперь – рекурсивный вариант алгоритма перебора с возвратом.
procedure перебор_с_возвратом(m: integer); var i: integer; begin if m > n then <найдено решение> else for i:= 1 to n do begin ферзь[m]:= i; if <ферзь[m] не бьёт предыдущих> then перебор_с_возвратом(m+1); end ; end ;Чем отличаются данные алгоритмы? Тем, что в первом проверка позиции происходит на самом позднем (``глубоком'') этапе перебора, а во втором на каждом этапе перебора происходит частичная проверка. (Если же все частичные проверки завершились успешно, получившуюся позицию уже можно не проверять.) Таким образом, перебор с возвратом исключает из перебора большое количество вариантов по сравнению с полным перебором.
