Решение проблем методом поиска

Что такое метод поиска

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

Преобразуем задачу про волка, козу и капусту в новый вид. Обозначим четырьмя булевыми переменными наличие или отсутствие на левом берегу волка, козы, капусты и лодки соответственно (начальное состояние 1, 1, 1, 1). Необходимо переместить всех на правый берег (конечное состояние 0, 0, 0, 0). Описывать то, что находится на правом берегу нет необходимости. То, чего нет на одном берегу, есть на другом. С учетом ограничений (волка нельзя оставлять с козой, а козу — с капустой) все допустимые переходы можно отобразить в виде графа состояний (рис. 2.1). Для записи пути к цели введем еще пару переменных типа «список». В первой будет накапливаться последовательность пройденных вершин дерева решений, последняя будет использоваться для возврата результата.

Рис. 2.1. Граф состояний для задачи о волке, козе и капусте.

Запишем это на Прологе:

farmer (0, 0, 0, 0, Path, Path).

% конечное состояние — все на правом берегу farmer (W, G, С, F, Р, Path).

% klj Gj Cj В — текущее состояние next (W, G, C, F, Wl, Gl, Cl, FI),.

% выбор преемника

farmer (Wl, Gl, Cl, FI [[W, G, С, В] | P], Path).

% переход к следующему состоянию next (W, G, C, 1, W, G, C, 0): — % выбор преемника

move (W, G, C, F, Wl, Gl, Cl, FI), not (conflict (W, G, С, B)). move (1, G, C, 1, 0, G, C, 0). % везем волка вправо

move (W, 1, C, 1, W, 0, C, 0). % везем козу вправо

move (W, G, 1, 1, W, G, 0, 0). % везем капусту вправо

move (W, G, C, 1, W, G, C, 0). % идем порожняком вправо

move (W, G, C, 0, W, G, C, 1). % идем порожняком влево

move (0, G, C, 0, 1, G, C, 1). % везем волка влево

move (W, 0, C, 0, W, 1, C, 1). % везем козу влево

move (W, G, 0, 0, W, G, 1, 1). % везем капусту влево

% конфликтные состояния.

conflict (1, 1, _, 0). % волк и коза на левом берегу,

фермер — на правом

conflict (_, 1, 1_} 0). % коза и капуста на левом берегу,

фермер — на правом

conflict (0, 0, 1). % волк и коза на правом берегу,

фермер — на левом

conflict (_, 0, 0,1). % коза и капуста на правом берегу,

фермер — на левом

Изобразим дерево решений для данной программы (рис. 2.2). Поскольку Пролог начинает унифицировать предикаты в порядке их следования в программе, он реализует поиск методом «сначала вглубь» (поиск в глубину).

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

Рис. 2.2. Дерево решений задачи о волке, козе и капусте.

Модификация данного метода путем исключения повторного перехода на уже посещенные узлы позволяет избежать бесконечного спуска по дереву:

farmer (W, G, С, F, Р, Path).

% 1л1, G, С, В — текущее состояние next (W, G, С, F, Vll, Gl, Cl, F1),

% выбор преемника not (member ([W, G, С, В], Р)),.

% исключение повторного посещения

farmer (Wl, Gl, Cl, FI [[W, G, С, В] | P], Path).

% переход к следующему состоянию

Если теперь задать предикат цели.

farmer (1, 1, 1, 1, [], Path).

то переменная Path будет содержать список состояний от начального до конечного по кратчайшему пути к цели.