Простір станів є формалізмом для подання задач.

ЛАБОРАТОРНА РОБОТА 15

Тема: Типові приклади застосування логічного програмування мовою Пролог. Частина 3. Операції над структурами даних, удосконалені методи подання множин деревами, основні стратегії розв'язування задач та пошук із перевагою (еврістичний пошук) у Пролог-програмах.

Мета − опановування наступних питань, покладених в основу типових прикладів логічного програмування мовою Пролог:

− можливості різноманітного подання та сортування списків;

− подання множин двійковими деревами;

− двійкові довідники (додавання та видалення елементів);

− відображення дерев;

− графи;

− двійково-трійкові довідники;

− AVL-дерево (наближено-збалансоване дерево);

− попередні поняття та приклади стосовно стратегій пошуку, стратегії пошуку в глибину та ширину, особливості пошуку в графах (технологій, оптимальності та складності пошуку), пошук із перевагою (зокрема, стосовно головоломки “гра у вісім” і в застосуванні до планування виконання задач).

ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ

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

Таблиця 15.1

Структури даних та операції над структурами даних,

які покладено в основу типових прикладів

застосування логічного програмування мовою Пролог

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

Переглянувши главу 10 навчального посібника [2], ви зможете вивчити особливості реалізації засобами Прологу таких понять, як 2-3-дерева та AVL-дерева, що є наочними прикладами збалансованих дерев.

Збалансовані та наближено-збалансовані дерева гарантують ефективне виконання трьох основних операцій над деревами: пошук, додавання та видалення елементу.

Час виконання вказаних операцій є пропорційним log n, де n – кількість вершин дерева.

Простір станів є формалізмом для подання задач.

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

Конкретна задача визначається стартовою вершиною та цільовою умовою.

Розв’язку задачі відповідає шлях у графі.

Таким чином, розв’язування задачі зводиться до пошуку шляху в графі.

Оптимізаційні задачі моделюються приписуванням кожній дузі простору станів деякого вагового коефіцієнту.

Є дві основних стратегії пошуку в просторі станів – пошук у глибину та пошук у ширину.

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

Існують два простих методи запобігання зациклюванню: обмежити глибину пошуку та не допускати дублювання вершин.

Реалізація пошуку в ширину є більш складною, оскільки вимагається зберігати множину кандидатів.

Дана множина може бути з легкістю подана списком списків, але більш економним є подання її у вигляді дерева.

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

У випадку обширних просторів станів, існує небезпека комбінаторного вибуху.

Обидві базові стратегії пошуку в просторі станів погано пристосовані для боротьби з указаною проблемою.

У таких випадках, потрібно керуватися еврістиками.

Переглянувши главу 11 навчального посібника [2], ви зможете опанувати наступні поняття: простір станів; стартова вершина; цільова умова; розв’язувальний шлях; стратегія пошуку; пошук у глибину та ширину; еврістичний пошук.

Для оцінювання ступеня віддаленості деякої вершини простору станів від найближчої цільової вершини, можна використовувати еврістичну інформацію.

Переглянувши главу 12 навчального посібника [2], ви зможете дізнатися про числові еврістичні оцінки.

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

Також у главі 12 запрограмовано алгоритм пошуку, оснований на вказаному вище принципі та представлений у літературі як А*-алгоритм.

Для того, щоб розв’язати конкретну задачу за допомогою А*-алгоритму, необхідно визначити простір станів та еврістичну функцію.

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

Теорема про припустимість допомагає встановлювати, чи завжди той А*-алгоритм, який використовує деяку конкретну еврістичну функцію, буде знаходити оптимальний розв’язок задачі.

КОНТРОЛЬНЕ ЗАВДАННЯ

Розробіть декілька власних наочних прикладів Пролог-програм для демонстрації понять і технологій, покладених в основу типових прикладів застосування логічного програмування мовою Пролог (основну увагу акцентуйте на тих аспектах, які було розглянуто в основних теоретичних відомостях до даної лабораторної роботи).

DOMAINS

charlist = char*

PREDICATES

string2charlist (string, charlist)

CLAUSES

string2charlist (Str, [H|T]):-

frontchar (Str, H, Str_Rest), !,

string2charlist (Str_Rest, T).

string2charlist (_, [ ]).

GOAL

string2charlist ("Kingston Samsung AMD Transcend", List),

write ("List=", List).

Поиск по сайту: