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

Турбо-Пролог после запуска предпологает определенную

конфигурацию своих и пользовательских файлов. Различаются пять

каталогов:

1. Турбо-каталог. Здесь должны находиться следующие файлы:

PROLOG. EXE сама система Турбо-Пролог;

PROLOG. ERR тексты сообщений ошибок; без этого файла выдаются

только номера ошибок;

PROLOG.HLP тексты на помощь (выдаются в редакторе при <F1>)

PROLOG.SYS информации о цветах, размерах окон и конфигурации

каталогов;

PROLOG. OVL для создания EXE-файлов;

PROLOG. LIB библиотечный файл для создания ЕХЕ-файлов.

2. OBJ-каталог. Это каталог для пользовательских объектных (OBJ)

и проектных (PRJ) файлов; кроме этого здесь должен присутство-

вать файл:

INIT.OBJ содержит нужные для создания ЕХЕ-файлов коды.

3. PRO-каталог. Содержит-пользовательские исходные тексты.

4. EXE-каталог. Здесь хранятся созданные пользователем EXE-файлы.

5.DOS-каталог. В этом каталоге для выполнения команд

операционной системе должен быть файл COMMAND. СОМ.

В начале работы Турбо-Пролог выдает сообщение об имеющейся

конфигурации, например:

configuration

Workfile WORK. PRO EXE directory C: \PROLOG

PRO directory B: \USER Turbo directory C:\PROLOG

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

Методы поиска решений в пространстве состояний начнем рассматривать с простой задачи о миссионерах и людоедах. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.

Основой метода являются следующие этапы.

1. Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S=(x,y,z), где x и y — число миссионеров и людоедов на левом берегу, z= {L,R} — положение лодки на левом (L) или правом (R) берегах. Итак, начальное состояние S0=(3,3, L ) и конечное (терминальное) состояние Sk=(0,0, R ).
2. Заданы правила перехода между группами состояний. Введем понятие действия M:[u, v]w, где u — число миссионеров в лодке, v — число людоедов в лодке,w — направление движения лодки (R или L).
3. Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x y;3-x 3-y; u+v 2.
4. После этого из текущего (исходного) состояния строятся переходы в новые состояния, показанные нарис. 3.1. Два новых состояния следует сразу же вычеркнуть, так как они ведут к нарушению условий допустимости (миссионеры будут съедены).
5. При каждом переходе в новое состояние производится оценка на допустимость состояний и если при использовании правила перехода для текущего состояния получается недопустимое состояние, то производится возврат к тому предыдущему состоянию, из которого было достигнуто это текущее состояние. Эта процедура получила название бэктрекинг (bac tracing или BACKTRACK).

Рис. 3.1. Переходы из исходного состояния

Рис. 3.2. Метод поиска в пространстве состояний

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

Как уже упоминалось, фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли «съесть» друг друга.

Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи. Читатель сам может завершить решение этой задачи на основе процедуры BACKTRACK.