Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

МЕТОДИ ПОШУКУ НА ДЕРЕВІ РІШЕНЬ

В результаті освоєння даного розділу навчається буде: знати

• особливості і природні обмеження решаемости завдань, що зводяться до перебору варіантів;

вміти

• вибирати необхідні методи пошуку па дереві рішень для реалізації поставлених завдань;

володіти

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

Завдання, які вирішуються перебором варіантів

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

Практично будь-яка комп'ютерна програма містить команди умовного переходу, за допомогою яких реалізує розгалужені алгоритми. Однак існують алгоритми, в яких розгалуження переважає над обчисленнями і рішення задачі зводиться до перебору комбінацій станів. Складність такого завдання визначається числом можливих станів. Прикладом може служити цифровий кодовий замок. Якщо в ньому три цифри, то число станів одно тисячі. Стійкість такого шифру невелика. Якщо витрачати на кожну спробу одну секунду, то на повний перебір піде менше 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 (R)),

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).

Фрагмент дерева рішень гри «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). Наведені вище приклади показують, що навіть приналежність завдань пошуку до одного класу не означає автоматично, що для їх вирішення можна використовувати одну і ту ж програму.

 
<<   ЗМІСТ   >>