по Спуск по единственной непросмотренной ветви.

И01 Проверка комбинации.

110 Отход из 1101.

1100 Проверка комбинации.

110 Отход из 1100.

И Отход, так как все ветви просмотрены.

1 Отход, так как все ветви просмотрены.

10 Спуск по единственной непросмотренной ветви.

101 Спуск по самой левой непросмотренной ветви.

1011 Проверка комбинации.

101 Отход.

1010 Проверка комбинации.

101 Отход.

10 Отход.

100 Спуск по единственной непросмотренной ветви.

1001 Проверка комбинации.

100 Отход.

10 Отход; заметим, что мы не опускаемся к 1000, так как эта вершина нарушает условие о том, что должно быть по крайней мере две единицы.

1 Отход.

Корень Отход.

О Спуск по единственной непросмотренной ветви.

и т. д.

Алгоритм останавливается, когда мы возвращаемся к корню и не остается непросмотренных ветвей.

Этот простой пример иллюстрирует основные свойства, общие для всех алгоритмов с отходом назад. Если можно сформулировать задачу так, что все возможные решения могут быть образованы построением Л/-векторов, тогда ее можно решить при помощи процедуры с отходом.

Задача - головоломка «8»

Рис. 3.3.2. иллюстрирует так называемую головоломку «8». В коробке 3x3 находятся восемь подвижных квадратов, одно место - пустое (обозначенное х). Любой занумерованный квадрат, прилегающий к пустому месту, можно передвинуть на это место, при этом пустое место окажется в позиции, занимаемой до этого занумерованным квадратом. Например, на рис. 3.3.2, а квадрат 3 можно передвинуть на место, обозначенное х, пустое место окажется в позиции, занимаемой до этого квадратом 3, как показано на рис. 3.3.2, б. Попытаемся найти последовательность передвижений, которая преобра-

зует конфигурацию, изображенную на рис. 3.3.2, а, в конфигурацию, показанную на рис. 3.3.2, е.

Не очевидно, что программирование с отходом назад годится для головоломки «8». Придется построить несколько искусственную, но

Рис. 3.3.2. Головоломка

тем не менее эффективную Л/-векторную структуру. Каждая вершина дерева будет соответствовать конфигурации головоломки. Корень (на уровне 0) будет соответствовать исходной конфигурации (рис. 3.3.2, а), от него будут отходить ветви, ведущие к вершинам уровня 1, каждая из которых будет соответствовать конфигурации, полученной одним передвижением из исходной. Вершины, непосредственно следующие за любой вершиной дерева, будут упорядочены слева направо по направлению, в котором движется пустая клетка. Самая левая конфигурация будет соответствовать движению пустой клетки влево, остальные конфигурации будут соответствовать движениям пустой клетки вверх, вниз и направо. На рис. 3.3.3 показаны первые два

Рис. 3.3.3. Построение дерева отходов для головоломки

уровня нашего дерева. Заметим, что передвижение пустой клетки наверх из исходной конфигурации невозможно.

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

вершиной конфигурация повторяла непосредственно предшествующую. Например, рассмотрим самую правую вершину уровня 1 на рис. 3.3.3. Эта вершина могла бы иметь две последующие, соответствующие передвижениям пустого квадрата влево и вниз. Но передвижение влево повторит корневую конфигурацию и не приблизит нас к окончательному состоянию.

Таким образом, элементы Л-векторов, соответствующие конфигурациям, должны удовлетворять условию, состоящему в том, что (&--1)-й элемент должен получаться из fe-ro одним ходом и (&+1)-й элемент не может быть таким же, как (fe-1)-й. Каково значение N? Глубина дерева N означает максимальное число ходов, которые мы собираемся рассматривать на пути от исходной конфигурации к конечной. Так как мы не представляем себе, сколько ходов может потребоваться, N должно быть выбрано на основании нашего запаса терпения или машинного времени. Например, если N=7, то процедура покажет, может ли быть получена окончательная конфигурация не более чем за семь передвижений из исходной конфигурации.

Теперь мы подготовлены к тому, чтобы воспользоваться процедурой с отходами для головоломки «8». Как и в задаче с велосипедным замком, постараемся всегда двигаться влево вниз по дереву поиска. Рис. 3.3.4 иллюстрирует дерево отходов. Номера, стоящие рядом с конфигурациями, показывают порядок генерации вершин в процедуре. Окончательная конфигурация в вершине 20 может быть достигнута через три передвижения от исходного состояния. Продолжите в качестве упражнения процедуру с отходами, чтобы получить конфигурацию, изображенную на рис. 3.3.2, г.

В наихудшем случае алгоритмы с отходами экспоненциальные, ибо может оказаться необходимым исчерпывающий поиск на множестве решений с экспоненциальным числом элементов. В ранее рассмотренной задаче о велосипедном замке может быть 2 вершин на уровне N, так как поиск бинарный. Процедура с отходами, отбрасывающая 99% потенциально возможных решений, является все еще экспоненциальной, потому что 2/100 растет экспоненциально при

Программирование с отходом часто называют «методом на крайний случай», так как можно привести аргументы, показывающие, что оно всего лишь на один уровень эффективнее «лобовых» методов полного перебора. Следует, конечно, искать более эффективные методы, но такое пожелание легче высказать, чем осуществить. Программирование с отходом - важный инструмент, которым должен уметь пользоваться каждый программист.

Упражнения 3.3

3.3.1. пример с головоломкой «8». Продолжите процедуру с отходами, продемонстрированную на головоломке «8», с целью получить конфигурацию, показанную на рис. 3.3.2, г. Поиск ведите не дальше седьмого уровня дерева.