Повна версія

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

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


<<   ЗМІСТ   >>

ВИКОРИСТАННЯ ПРЕЦЕДЕНТІВ ДЛЯ РЕДУКУВАННЯ ДЕРЕВА РІШЕНЬ

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

Повернемося до наведеного в параграфі 2.1 наприклад з грою «23 сірники». При уважному розгляді фрагмента дерева знайти цю гру можна побачити, що дерево складається з безлічі фрагментів (рис. 3.3).

Повторювані фрагменти дерева рішень гри «23 сірники»

Мал. 3.3. Повторювані фрагменти дерева рішень гри «23 сірники»

Пунктиром на рис. 3.3 позначені повторювані фрагменти. Повний обхід фрагмента вимагає розгортання 28 вершин. Якщо запам'ятовувати результат першого обходу кожного з таких фрагментів, це позбавить від необхідності повторного поглиблення і скоротить число розгорнутих вершин до 12 (виділені заливкою), тобто більш ніж в два рази. Природно, такий прийом має сенс тільки при пошуку спочатку в глибину.

Нижче наведено фрагмент модифікованої програми на мові Prolog, що включає висновок на основі прецедентів. Напівжирним шрифтом відзначені додані предикати. Оновлена логіка програми передбачає спочатку пошук рішення серед запам'ятали прецедентів, а якщо такого не знаходиться, то відбувається спуск по дереву, а знайдене рішення запам'ятовується в базі прецедентів для використання при пошуку на сусідніх гілках дерева:

% Допустимі ходи

move (1). move (2). move (3).

% Правило хорошого ходу

good_move (X, М) precedent (X, М),! .

good_move (X, М) move (М), X- $ 5 = 1.

good_move (X, М) move (М),

XI is Х-М,

not (good_move (Xl, _)), assert (precedent (X, М)).

Повне дерево пошуку для початкового стану «23 сірники» містить 900 140 вершин, а пошук до першого рішення - 20 009 вершин; в цьому випадку запам'ятовування проміжних результатів скоротить обхід до 57 вершин, або в 351 разів.

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

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

 
<<   ЗМІСТ   >>