Методы поиска на дереве решений

В результате освоения данной главы обучающийся будет: знать

• особенности и естественные ограничения решаемости задач, сводящихся к перебору вариантов;

уметь

• выбирать необходимые методы поиска па дереве решений для реализации поставленных задач;

владеть

• современными технологиями ускорения логического поиска.

Задачи, решаемые перебором вариантов

Программистский подход

Практически любая компьютерная программа содержит команды условного перехода, с помощью которых реализует ветвящиеся алгоритмы. Однако существуют алгоритмы, в которых ветвление преобладает над вычислениями и решение задачи сводится к перебору комбинаций состояний. Сложность такой задачи определяется числом возможных состояний. Примером может служить цифровой кодовый замок. Если в нем три цифры, то число состояний равно тысяче. Стойкость такого шифра невелика. Если тратить на каждую попытку одну секунду, то на полный перебор уйдет меньше 17 минут. Добавление еще одного разряда в кодовый замок увеличит число комбинаций до 10 000, а время перебора — почти до трех часов.

Рассмотрим известную логическую задачу о волке, козе и капусте. Фермер должен переправить на другой берег реки волка, козу и капусту. Грузоподъемность лодки такова, что за один раз можно взять на борт что-нибудь одно: или волка, или козу, или капусту. В присутствии фермера никто никого нс ест. Если же он отлучится, то волк съест козу, а коза — капусту.

Для решения этой задачи организуем два списка. Один список будет отражать содержимое левого берега, второй — правого. Первоначально все находятся на левом берегу. Список левого берега: [wolf, goat, cabbage], список правого берега (пустой): []. Определим предикаты, описывающие объекты перемещения.

stuff (wolf). stuff (goat).

stuff (cabbage). % перечисление объектов Зададим также условия возникновения конфликта. Конфликт имеет место, если на берегу одновременно присутствуют волк с козой или коза с капустой.

conflict (X) member (wolf, X), member (goat, X) .

conflict (X) member (goat, X), member (cabbage, X) .

Далее, опишем предикаты для перемещения лодки:

% С левого берега на правый go_right ([],_). % условие завершения.

% (список левого берега пуст) go_right (L, R).

stuff (X), % выбираем объект,.

member (X, L), % который есть на левом берегу.

excl (X, L, LL), % исключаем из списка.

% левого берега.

not (conflict (LL)), % на левом берегу конфликта нет.

incl (X, R, RR), % включаем в список правого берега.

writef ('%w —%w — > %w ',.

[LL, X, R]), % выводим сообщение.

go_left (LL, RR). % движемся назад Движение влево возможно в двух вариантах. Если на правом берегу конфликт не возникает, то фермер едет один:

go_left (L, R) not (conflict ®) ,.

writef ('%w <——%w ', [L, R]), % выводим сообщение.

go_right (L, R). % вызываем предикат.

% движения вправо Если на правом берегу возникает конфликт, надо кого-нибудь увезти обратно. (Это единственная подсказка, которую мы сообщаем программе. В остальном Prolog будет искать решение вполне самостоятельно.).

go_left (L, R).

stuff (X), % выбираем объект,.

member (X, R), % который есть на правом берегу.

excl (X, R, RR), % исключаем из списка правого.

% берега not (conflict (RR)), % на правом берегу конфликта нет.

incl (X, L, LL), % включаем в список левого берега.

writef ('%w <�—%w —%w ',.

[L, X, RR]), % выводим сообщение.

go_right (LL, RR). % гребем назад.

incl (H, T, [H|T]). % добавление элемента в список.

excl (Н, [Н|Т], Т). % Исключение из списка.

% (исключаем из головы).

excl (X, [Н|Т], [Н|ТТ]) :-% Если исключаемый элемент.

excl (X, Т, ТТ). % не в голове списка,.

% то исключаем из хвоста Вызов цели должен быть следующим:

go_right ([wolf, goat, cabbage], []).

Если запустить эту программу, то быстро обнаружится, что первым рейсом старик отвезет на правый берег козу. Вторым рейсом — волка. Оставить волка с козой на правом берегу нельзя, поэтому он отвезет первый попавшийся груз, а им окажется волк, обратно. И так будет возить его бесконечно.

Недостаток данной программы заключается в том, что поиск допускает повторяющиеся состояния. Иными словами, фермер не помнит, кого он только что привез. Для укрепления его памяти достаточно добавить в предикаты go_left и go_right название последнего перевезенного груза. Предлагаем читателю сделать это самостоятельно. Результат будет выглядеть следующим образом:

[wolf, cabbage] — goat — > [].

[wolf, cabbage] <�— — — - [goat].

[cabbage] - wolf -> [goat].

[cabbage] <�— goat — [wolf].

[goat] — cabbage — > [wolf].

[goat] <�— — — - [cabbage, wolf].

[] — goat — > [cabbage, wolf].

Рассмотрим теперь простую логическую игру «23 спички». Правила игры следующие. В кучке лежат 23 спички. Два игрока по очереди берут одну, две или три спички. Тот, кто берет последнюю спичку, проигрывает. На рис. 2.1 показан фрагмент графа, описывающего процесс поиска (дерева решений).

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

% Перечисление возможных ходов move (1). move (2). move (3) .

% Условие проигрыша человека (выход из рекурсии) man (1) write ('Вы проиграли')/ nl.

% Обработка хода человека.

man (X) writef ('У Bac%w спичек. Ваш ход:', [X]), get ©, М is С-48,% преобразуем код символа в цифру XI is Х-М, machine (XI).

% Условие проигрыша машины.

machine (1) write ('Вы выиграли'), nl.

% Обработка хода машины.

machine (X) writef ('У меня %w спичек.

Мой ход:', [X]),.

find_move (X, М), write (М), nl,.

XI is Х-М, man (XI).

% Найти хороший ход.

find_move (X, М) : — good_move (X, М) .

% Если хорошего хода нет, машина возьмет одну спичку.

find_move (_, 1) .

% Найти хороший ход.

good_move (X, М) : — move (М), XI is X—М, XI = 1.

good_move (X, М) : — move (М), XI is X—М,.

not (good_move (Xl,_)).

% Конец программы.

% Цель задавать в виде?- man (23) .

Рис. 2.1. Фрагмент дерева решений игры «23 спички»

Ключевым здесь является предикат good_move. Первый экземпляр этого предиката определяет, что хорошим является ход, после которого у соперника остается одна спичка:

good_move (X, М) move (М), XI is X—М, XI = 1.

Второй экземпляр предиката good_move отвечает за состояние, когда достичь выигрыша за один ход невозможно. В этом случае хорошим ходом считается такой ход из числа допустимых, после которого у соперника нет хорошего хода:

good_move (X, М) move (М), XI is Х-М,.

not (good_move (XI_А_)).

Существуют задачи, которые можно разделить на два класса. Смысл одних задач состоит исключительно в поиске правильной траектории спуска, но дереву решений. Для второго класса задач решением является не путь к цели, а только финальное состояние, например как в задаче о восьми ферзях (которая будет рассмотрена в подпараграфе 2.2.2). Приведенные выше примеры показывают, что даже принадлежность задач поиска к одному классу не означает автоматически, что для их решения можно использовать одну и ту же программу.