Саратовський державний технічний університет
Кафедра СІІ
Курсова робота
по Методам штучного інтелекту
Експертна система для вирішення задачі про комівояжера
Виконав:
Перевірив:
Саратов 2009
Зміст
1.Постановка завдання
2.Ідентіфікація проблеми
3.Ізвлеченіе знань
4.Формалізація
5.Опісаніе програми
6.Тестірованіе програми
7.Література
1. Постановка завдання
Цілю, даної курсової роботи, є розробка, макетування та реалізація експертної системи для вирішення задачі про комівояжера, використовуючи можливості мови Prolog.
2. Ідентифікація проблеми
Задача про комівояжера досить поширена завдання. Стосовно до виробництва її можна інтерпретувати так, є один верстат і набір деталей. Час обробки деталей на верстаті однакове, але час переналагодження верстата різне. Потрібно обробити всі деталі, але за мінімальний термін. Так само її можна адаптувати до пошуку мінімально короткого шляху на карті між двома пунктами. Наприклад, в системі GPS-навігації для автомобілів, що шукає найкоротший шлях між двома пунктами на карті, маючи карту доріг.
Дана проблематики має широке застосування в повсякденному житті.
У цій роботі розглянемо проблему пошуку найкоротшого шляху між двома пунктами на карті, маючи граф «Карта Саратовської область», в якому вершини графа це міста, а дуги, що з'єднують вершини-міста, є дорогами.
Необхідні ресурси:
Література з кібернетики
ПК із системою Prolog
Експерт
Джерелами знань в даному випадку виступають:
Книги з кібернетики
Експерт - професор каф. ЦІ Петров С.В.
3. Вилучення знань
Вилучення знань - це процедура взаємодії інженера по знаннях з джерелом знань, в результаті якої стає явним процес міркувань експертів при прийнятті рішення і структура їх уявлень про предметну область.
Лікування знань будемо робити шляхом аналізу літератури з кібернетики. Для додаткового уточнення вдамося до консультацій експерта.
Уявімо карту у вигляді графа. Граф - це мережа, що складається з вузлів, з'єднаних дугами (рис.1). Вузлами в даному випадку є містами, а дуги - будуть містами, що з'єднують відповідні вузли (міста). Наявність дороги між містами означає наявність дуги між відповідними вузлами.
Рис. 1
Пошук найкоротшого шляху між двома містами означає пошук найкоротшого шляху між двома вузлами графа.
У процесі пошуку, як правило, виникає проблема, як обробляти альтернативні шляхи пошуку.
У цьому зв'язку в Пролозі існують дві основні стратегії:
Пошук в глибину
Пошук у ширину
Стратегія пошуку в ширину
Пошук у ширину передбачає перехід в першу чергу до вершин, найближчим до стартової вершині. У результаті процес пошуку має тенденцію розвиватися більше в ширину. При пошуку в ширину доводиться зберігати всі безліч альтернативних вершин (а не одну вершину як при пошуку в глибину). Зберігаються не лише вершини, а й безліч шляхів, які зберігаються у вигляді списку.
Загальні принципи побудови пошуку в ширину:
1) Якщо перший елемент (вершина) першого шляху (у списку шляхів) - це цільова вершина, то взяти цей шлях у якості рішення.
2) Інакше видалити перший шлях і породити безліч продовжень цього шляху на один крок.
Безліч продовжень додається до списку шляхів в кінець.
Стратегія пошуку в ширину гарантує отримання найкоротший рішення першим, на відміну від стратегії пошуку в глибину. Якщо критерієм оптимальності є мінімальна вартість вирішального шляху, а не його довжина, то пошуку в ширину також буває недостатньо, оскільки виникає складність комбінаторного характеру.
Стратегія пошуку в глибину
Програми штучного інтелекту мають специфічну організацію: є початковий стан, і необхідно знайти шлях, що приводить до кінцевого стану, тобто мета. Де кінцевий стан може являти собою набір прийнятних станів.
Програма повинна шукати необхідні стану "крокуючи" від стану до стану при цьому, розпізнаючи ситуації, коли вона знаходить ціль або потрапляє у глухий кут.
Стратегія пошуку в глибину заснована на ретельному дослідженні послідовності одного варіанта вибору до вивчення інших варіантів.
Спочатку досліджується найперша ліва гілка дерева, коли процес пошуку заходить у глухий кут. Інтерпретатор повертається вгору, в останній пункт вибору. Де є невивчені альтернативні варіанти руху.
Пошук в глибину найбільш адекватний рекурсивному стилю програмування.
4. Формалізація
Формалізація знань - розробка бази знань на мові представлення знань, який, з одного боку, відповідає структурі поля знань, а з іншого - дозволяє реалізувати прототип системи на наступній стадії програмної реалізації.
Виходячи з отриманих знань, у пункті 3, знання можна представити у вигляді продукційної моделі:
Якщо є дорога з А в Б, то з А можна переїхати в Б.
Причому інформація про наявність доріг не надлишкова, що виражено в тому, що якщо є дорога з А в Б, то можна переїхати з А в Б, але навпаки неможливо, то є з Б у А. Для подолання даного труднощі можна піти двома шляхами:
Додати ще одне твердження в продукційної моделі, що якщо є дорога з А в Б, то можна переїхати не тільки з А в Б, а й з Б в А.
Програмно реалізувати, щоб система розуміла, що наявність дороги означає, що можна переїхати з А в Б, а й наооброт.
5. Опис програми
Визначимо відношення
path (A, Z, P, D),
де P - ациклічний шлях між вершинами A і Z у графі, представленому наступними дугами:
arca (a, b, 1).
arca (a, c, 1).
arca (b, e, 1).
arca (b, d, 1).
arca (c, d, 1).
arca (c, g, 1).
arca (c, f, 1).
arca (d, e, 1).
arca (e, f, 1).
arca (f, x, 1).
Дуги прописані згідно рис.1.
Для реалізації методу пошуку виберемо метод пошук в глибину, який заснований на наступних міркуваннях:
Якщо A = Z, то покладемо P = [A];
Інакше треба знайти ациклічний шлях P1 з довільної вершини Y в Z, а потім знайти шлях з A в Y, який не містить вершин з P1.
Введемо відношення
path1 (A, P1, P, D),
означає, що P1 - завершальний ділянку шляху P.
Між path і path1 має місце співвідношення:
path (A, Z, P, D): - path1 (A, [Z], P, D).
Рекурсивне визначення ставлення path1 випливає з таких посилок:
"Граничний випадок": початкова вершина шляху P1 співпадає з початковою вершиною A шляху P;
у противному випадку повинна існувати така вершина X, що: 1) Y - вершина, суміжна з X, 2) X - не міститься в P1, 3) для P виконується ставлення path (A, [Y | P1], P).
Ставлення можна реалізувати згідно:
path (A, Z, Path, C): - path 1 (A, [Z], 0, Path, C).
path1 (A, [A | Path1], C, [A | Path1], C).
path1 (A, [Y | Path1], C1, Path, C): - arca (X, Y, CXY),
not (member (X, Path1)), C2 = C1 + CXY, path1 (A, [X, Y | Path1], C2, Path, C).
Де ставлення member - визначає чи належить елемент списку, реалізоване наступним кодом:
member (Head, [Head |_]).
member (Head, [_ | Tail]): - member (Head, Tail).
Для реалізації вибору оптимального вибору (мінімальна довжина) серед переліку шляхів введемо відношення db 0 і db:
db0 (X, Y):-path (X, Y, P, C), assert (db_path (X, Y, P, C)).
db (X, Y):-db_path (X, Y, P, C), path (X, Y, MP, MC), MC <C,!,
retract (db_path (X, Y, P, C)), assert (db_path (X, Y, MP, MC)), db (X, Y).
Ставлення db 0 ініціалізує перший можливий шлях. Якщо цей шлях не поодинокий, то db ініціалізує наступний шлях, і в той же час порівнює довжини двох даних шляхів. У процесі подальших рекурсій і порівняння залишається тільки один шлях, довжина якого мінімальна.
Текст програми:
domains
i = integer
s = symbol
list = s *
database
db_path (s, s, list, i)
predicates
path (s, s, list, i)
path1 (s, list, i, list, i)
member (s, list)
arca (s, s, i)
db0 (s, s)
db (s, s)
run (s, s)
start
goal
start.
clauses
start:-makewindow (1,7,7, "Expert System", 1,3,22,71), clearwindow,
write ("Enter the name of cities"), nl,
write ("The first city:"), readln (First), nl,
write ("The second city:"), readln (Second), nl,
run (First, Second), readchar (_).
arca (a, b, 1).
arca (a, c, 1).
arca (b, e, 1).
arca (b, d, 1).
arca (c, d, 1).
arca (c, g, 1).
arca (c, f, 1).
arca (d, e, 1).
arca (e, f, 1).
arca (f, x, 1).
run (Start, End):-db0 (Start, End), db (Start, End), db_path (Start, End, MP, MD),
write ("Optimum way:"), write (MP), nl,
write ("Length of an optimum way ="), write (MD),
nl, nl.
path (A, Z, Path, C): - path1 (A, [Z], 0, Path, C).
path1 (A, [A | Path1], C, [A | Path1], C).
path1 (A, [Y | Path1], C1, Path, C): - arca (X, Y, CXY), not (member (X, Path1)), C2 = C1 + CXY, path1 (A, [X, Y | Path1], C2, Path, C).
member (Head, [Head |_]).
member (Head, [_ | Tail]): - member (Head, Tail).
db0 (X, Y):-path (X, Y, P, C), assert (db_path (X, Y, P, C)).
db (X, Y):-db_path (X, Y, P, C), path (X, Y, MP, MC), MC <C,!,
retract (db_path (X, Y, P, C)), assert (db_path (X, Y, MP, MC)), db (X, Y).
db (_,_).
6. Тестування програми
а) Нехай маємо наступний граф:
Рис.2 | Мал.2а |
Шукаємо оптимальний шлях з a у х, згідно графу оптимальний шлях містить наступні вузли: a c f x, що зображено на рис.2.
Програма:
Дані ручного розрахунку і програми збігаються.
б) Змінимо довжину ребра a - c:
Рис.3 | Рис.3 |
Шукаємо оптимальний шлях з a у х, згідно графу оптимальний шлях містить наступні вузли: a b e f x, що зображено на рис.3.
Програма:
Дані ручного розрахунку і програми збігаються.
в) Змінимо довжину ребра b - d:
Рис.4 | Рис.4а |
Шукаємо оптимальний шлях з a у х, згідно графу оптимальний шлях містить наступні вузли: a b d e f x, що зображено на рис.4а.
Програма:
Дані ручного розрахунку і програми збігаються.
Література
І 57. Використання Турбо-Прологу: Пер. з англ.-М.: Світ, 1990.-410 с., іл.
Б 87. Братко. Програмування на мові Пролог для штучного інтелекту: Пер. з англ. -М.: Світ, 1990 .- 560 с., Мул