Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



ЛАБОРАТОРНА РОБОТА 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).

 

 

 




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

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.