УНІВЕРСАЛЬНИЙ ПІДХІД

У розглянутих вище прикладах вирішення завдань пошуку усвідомлено використовувався «програмістський підхід». Насправді такі завдання досить просто формалізуються до єдиним шаблоном. Вони характеризуються наявністю дискретних станів, одне з яких є початковим, інше - кінцевим, а також заданої логікою переходу з одного стану в інший. Отже, для їх вирішення досить описати початковий і кінцевий стани, а також алгоритм переходу з одного стану в інші (вибір наступника). Залежно від того, чи важливий шлях до мети, може знадобитися запам'ятовування пройдених станів. Наприклад, для завдання про фермера важливий тільки шлях до мети, оскільки кінцевий стан задано. В інших завданнях навпаки, не важливий шлях, а потрібно кінцевий стан. Приклад - завдання про восьми ферзів, де потрібно на шахівниці розставити ферзів так, щоб жоден з них не бив іншого.

Перетворимо завдання про вовка, козу і капусту в новий вид. Позначимо чотирма булеві змінними наявність або відсутність на лівому березі вовка, кози, капусти і човни відповідно (початковий стан 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 f 0, 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 буде містити список станів від початкового до кінцевого по найкоротшому шляху до мети.

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

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >