Универсальный подход. 
Интеллектуальные системы

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

Преобразуем задачу про волка, козу и капусту в новый вид. Обозначим четырьмя булевыми переменными наличие или отсутствие на левом берегу волка, козы, капусты и лодки соответственно (начальное состояние 1111). Необходимо переместить всех на правый берег (конечное состояние 0000). Описывать то, что находится на правом берегу, нет необходимости. То, чего нет на одном берегу, есть на другом. С учетом ограничений (волка нельзя оставлять с козой, а козу — с капустой) все допустимые переходы можно отобразить в виде графа состояний (рис. 2.2).

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

Для записи пути к цели введем еще пару переменных типа «список». В первой будет накапливаться последовательность пройденных вершин дерева решений, последняя будет использоваться для возврата результата. Запишем это на языке Prolog:

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

farmer (W, G, C, F, P, Path).

next (W, G, C, F, Wl, Gl,.

Cl, FI), % выбор преемника.

farmer (Wl, Gl, Cl, FI, [ (W, G, C,.

F) |P], Path). % переход.

% к следующему состоянию % выбор преемника.

next (W, G, С, F, Wl, Gl, Cl, F1).

move (W, G, С, F, Wl, Gl, Cl, F1),.

not (conflict (W, G, C, F)). move (1, G, C, 1,0, G, C, 0). % везем волка вправо move (W, l, C, l, W, 0, C, 0). % везем козу вправо.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

next (W, G, C, F, Wl, Gl,.

Cl, FI), % выбор преемника.

not (member ((W, G, C, F), P)), % исключение повторного.

farmer (Wl, Gl, Cl, FI,.

[ (W, G, C, F) IP], Path). % переход.

% к следующему состоянию Если теперь задать предикат цели.

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

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

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