ЕВРИСТИЧНИЙ ПОШУК У ГРАФАХ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 4
з дисципліни
„Експертні системи та автоматизовані системи навчання ”
для студентів базового напряму „Філологія”
спеціальності „Прикладна лінгвістика”
Затверджено
на засіданні кафедри інформаційних системи та мереж
Протокол №9 від 25.02.15
Евристичний пошук у графах: Методичні вказівки до лабораторної роботи № 4 / Укл.: Я.П.Кісь, В.А.Висоцька – Львів: Видавництво Національного університету ”Львівська політехніка”, 2015. – 24 с.
Укладачі
Кісь Я.П, к.т.н., доцент
Висоцька В.А., к.т.н., асистент
Відповідальний за випуск
Литвин В.В., завідувач кафедри ІСМ, д.т.н., професор
Рецензенти
Камінський Р.М., д.т.н., професор
Кравець П.О., к.т.н., доцент
(Для ознайомлення з повним текстом статті необхідно залогінитись)
1 Мета роботи
Вивчити А-алгоритм та А*-алгоритм та приклад реалізації А*-алгоритму – гру у вісімки. Вивчити методологію пошуку в глибину. Вивчити основи подання задач за допомогою І/АБО-графів та методи пошуку рішень у них. Навчитися моделювати ігрові ситуації за допомогою графів.
Вступ
Методи пошуку у графах, зокрема, у деревовидних структурах, широко використовуються як у дослідженні операцій, так і в штучному інтелекті. Пошук у графах для розв’язання задач, як правило, неможливий без вирішення проблеми комбінаторної складності, яка виникає через швидкий ріст альтернатив. Один з шляхів використання евристичної інформації про задачу – одержання евристичних оцінок для вершин простору станів. Існує багато різних підходів до проблеми пошуку шляху для задач, сформованих у термінах простору станів. Розглянемо стратегію пошуку в глибину та задачу про 8 ферзів як ілюстрацію її застосування. В основі пошуку в глибину лежить ідея вибору “найглибшої” вершини, тобто вершини, яка найбільше віддалена від стартової. Якщо досягнуто кінцевої вершини і потрібного шляху не знайдено, то відбувається повернення на рівень вище та робота алгоритму продовжується до тих пір, поки такий шлях не буде знайдено або не буде переглянуто усі вершини та встановлено факт відсутності потрібного шляху.
Подання у вигляді І/АБО-графів найкраще пристосоване до задач, які розбиваються на взаємно незалежні підзадачі. Розбиття на підзадачі дає переваги у тому випадку, коли підзадачі є взаємно незалежними, а, отже, розв’язувати їх можна незалежно одну від одної. Прикладами таких задач можуть бути: пошук маршруту, символічне інтегрування, ігрові задачі, доведення теорем тощо.
2 Пошук у глибину
У чистому вигляді пошук в глибину володіє значним недоліком: у ході роботи програми можливі зациклювання, якщо предок має лише одного нащадка і цей нащадок не є цільовою вершиною. Одним із методів розв’язання цієї проблеми є введення заборони двічі розглядати одну і ту ж вершину. Пошук в глибину є найадекватнішим для рекурсивного стилю програмування. Рекурсивне визначення означає, що якесь поняття використовується для його ж визначення. Наприклад, двійкове дерево оголошується як: порожнє дерево; складається з кореня, лівого піддерева, правого піддерева. Одним із способів застосування методології пошуку в глибину є задача про вісім ферзів.
3 Задача про вісім ферзів
Задача полягає у розміщенні восьми ферзів на шаховій дошці таким чином, щоб жоден з них “не бив” іншого. Вважатимемо дошку звичайних розмірів (8х8). Кожна позиція характеризується координатою Х та координатою Y. Нагадаємо, що ферзь може бити по горизонталі, по вертикалі та по діагоналі у різні сторони. Як спосіб подання позиції на дошці оберемо подання позиції у вигляді списку з восьми елементів з координатами Х та Y та номером вертикалі та горизонталі U та V відповідно, причому
U=X-Y,
V=X+Y,
тобто усі характеристики місця розміщення ферзя залежні між собою. Звідси області визначення
Dx=[1,2,3,4,5,6,7,8]
Dy=[1,2,3,4,5,6,7,8]
Du=[-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7]
Dv=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
Рис.1. Демонстрація пошуку в глибину
Задача пошуку розміщення ферзів зводиться до вибору восьми четвірок X, Y, U, V, що входять у відповідні області визначення, так, щоб жоден з елементів не обирався двічі з одної області визначення.
4 Подання задач у вигляді І/АБО-графів
І/АБО-граф – направлений граф, вершини якого відповідають задачам, а дуги – відношенням між задачами. Між дугами також можуть встановлюватись відношення.
Рис. 2. Приклад І/АБО-графа
Це відношення І або АБО, у залежності від того, чи повинні ми розв’язати лише одну із задач-нащадків, чи усі. З вершин можуть виходити дуги, які знаходяться у відношенні І разом з дугами, що між собою перебувають у відношенні АБО. Вершину, з якої виходить лише І дуга, називають І-вершиною. Вершина, з якої виходить лише АБО дуга, називають АБО-вершиною. Цільові вершини у випадку І/АБО-графа – тривіальні, або примітивні задачі, які не потребують подальшої деталізації. Розв’язком задачі, поданої у вигляді І/АБО-графа є включення, щонайменше, усіх підзадач І-вершин. Тобто шлях стає деревом. Таке дерево розв’язку визначається таким чином:
ü Вихідна задача Р – корінь дерева Т;
ü Якщо Р є АБО-вершиною, то в Т міститься тільки один з її нащадків (з І/АБО-графа) разом з своїм власним деревом розв’язку;
ü Якщо Р – це І-вершина, то усі її нащадки (з І/АБО-графа) разом з своїми деревами розв’язку містяться в Т.
5 Методи пошуку у І/АБО-графі
Для пошуку в І/АБО-графах використовують два методи: в глибину та евристичний пошук. Процедура пошуку в глибину є незмінною:
1) якщо досліджувана вершина - цільова, то це і є розв’язок;
2) якщо ця вершина має АБО нащадків, то потрібно розв’язати одну з відповідних задач нащадків; якщо вершина має І нащадків, то потрібно розв’язати всі задачі нащадків.
Для І/АБО графів використовується також процедура евристичного пошуку. Якщо стратегія пошуку в глибину передбачає систематичний перегляд графу і знаходження всіх розв’язків, то стратегія евристичного пошуку передбачає знаходження лише одного розв’язку. Гарантується, що цей розв’язок є найдешевший при умові, що евристична функція, що використовується, є нижньою межею реальної вартості дерева.
Вартість дерева розв’язку визначається як сума вартостей усіх дуг. Мета оптимізації – знайти розв’язок з мінімальною вартістю.
Вартістю вершини буде вартість оптимального дерева рішень цієї вершини. Вартість вершини, визначена таким чином, характеризує вартість задачі. Будемо вважати, що вартість вершини І/АБО-графа можна визначити і за допомогою відповідної евристичної функції h. Ця оцінка буде використовуватись для керування пошуком.
(Для продовження ознайомлення з повним текстом методички необхідно залогінитись та завантажити вкладення)