Справжня глава присвячена вирішенню завдань за допомогою графа простору станів. Простір станів описується в вигляді безлічі станів - вершин графа, безлічі переходів від стану до стану - дуг графа, безлічі початкових станів і безлічі кінцевих станів. Рішення завдання представляється у вигляді шляху на графі простору станів, що з'єднує початковий стан з кінцевим.
Якщо простір станів завдання невелика, то будуть знаходитися всі оптимальні рішення за допомогою пошуку в глибину. У завданнях з великим простором станів буде обчислюватися тільки одне оптимальне рішення за допомогою пошуку в ширину.
До завдань застосовуються універсальні вирішувачі. Стану в різних завданнях можуть належати різним доменів. Для запам'ятовування найкращих серед знайдених рішень використовується "змінна змінна" varM. Компілятор сам знаходить потрібні типи.
13.1. Пошук в глибину в просторі станів
У цьому параграфі пошук в глибину в просторі станів застосовується для вирішення відомих завдань. Спочатку вирішувач застосовується до задачі про вовка, козу і капусту. Для вирішення інших завдань у програму додаються лише опису станів і переходів між ними.
Задача про вовка, козу і капусту полягає в наступному (Алкуїн, XIII в.). Господар з вовком, козою і купою качанів капусти повинен перебратися через річку з лівого берега на правий, маючи в розпорядженні маленький човен. В цей човен, крім господаря, може поміститися тільки щось одне - або вовк, або коза, або капуста. Не можна залишати без нагляду вовка з козою, а козу з капустою. Як слід організувати переправу?
Стану в задачах про перевезення через річку зазвичай описуються у вигляді трійки, що містить безліч істот (предметів) на лівому березі, безліч істот (предметів) на правому березі, і берег, у якого знаходиться човен.
Для вирішення завдань, як і раніше, створюється консольний проект. У цьому проекті створюється модуль depth. У цей модуль слід помістити універсальний вирішувач, який використовує пошук в глибину (листинги 13.1 -13.2) 1 У лістингу 13.2 рядок з версії Visual Prolog 7.5 V = varM :: new ([]), в версії Visual Prolog 7.4 потрібно замінити рядком V = varM *> :: new ([]).
Приклад 13.1. Декларація класу depth
Приклад 13.2. Імплементація класу depth