Саратовский государственныйтехнический университет
Кафедра СИИ
Курсовая работа
по Методам искусственного интеллекта
Экспертная система для решения задачио коммивояжере
Выполнил:
Проверил:
Саратов 2009 г.
Содержание
1.Постановказадачи
2.Идентификацияпроблемы
3.Извлечениезнаний
4.Формализация
5.Описаниепрограммы
6.Тестированиепрограммы
7.Литература
1. Постановка задачи
Целю, данной курсовойработы, является разработка, макетирование и реализация экспертной системы длярешения задачи о коммивояжере, используя возможности языка Prolog.2. Идентификацияпроблемы
Задача о коммивояжередовольно распространенная задача. Применительно к производству ее можноинтерпретировать так, имеется один станок и набор деталей. Время обработкидеталей на станке одинаковое, но время переналадки станка разное. Требуетсяобработать все детали, но за минимальный срок. Так же ее можно адаптировать кпоиску минимально короткого пути на карте между двумя пунктами. Например, всистеме GPS-навигации для автомобилей, ищущейкратчайший путь между двумя пунктами на карте, имея карту дорог.
Данная проблематики имеетширокое применение в повседневной жизни.
В данной курсовой работерассмотрим проблему поиска кратчайшего пути между двумя пунктами на карте, имеяграф «Карта Саратовской область», в котором вершины графа это города, а дуги,соединяющие вершины-города, являются дорогами.
Необходимые ресурсы:
Литература по кибернетике
ПК с системой Prolog
Эксперт
Источниками знаний вданном случае выступают:
Книги покибернетике
Эксперт — профессор каф. СИИ Петров С.В.3. Извлечение знаний
Извлечение знаний — этопроцедура взаимодействия инженера по знаниям с источником знаний, в результатекоторой становится явным процесс рассуждений экспертов при принятии решения иструктура их представлений о предметной области.
Излечение знаний будемпроизводить путем анализа литературы по кибернетике. Для дополнительногоуточнения прибегнем к консультациям эксперта.
Представим карту в видеграфа. Граф — это сеть, состоящая из узлов, соединенных дугами (рис.1). Узламив данном случае являются городами, а дуги — будут являться городами,соединяющие соответствующие узлы (города). Наличие дороги между городамиозначает наличие дуги между соответствующими узлами.
/>
Рис. 1
Поиск кратчайшего путимежду двумя городами означает поиск кратчайшего пути между двумя узлами графа.
В процессе поиска, какправило, возникает проблема, как обрабатывать альтернативные пути поиска.
В этой связи в Прологесуществуют две основные стратегии:
1. Поиск в глубину
2. Поиск в ширину
Стратегия поиска вширину
Поиск в ширинупредусматривает переход в первую очередь к вершинам, ближайшим к стартовойвершине. В результате процесс поиска имеет тенденцию развиваться больше вширину. При поиске в ширину приходится сохранять все множество альтернативныхвершин (а не одну вершину как при поиске в глубину). Хранятся не тольковершины, но и множество путей, которые хранятся в виде списка.
Общие принципы построенияпоиска в ширину:
1) Если первый элемент(вершина) первого пути (в списке путей) — это целевая вершина, то взять этотпуть в качестве решения.
2) Иначе удалить первыйпуть и породить множество продолжений этого пути на один шаг.
Множество продолженийдобавляется к списку путей в конец.
Стратегия поиска в ширинугарантирует получение кратчайшее решение первым, в отличие от стратегии поискав глубину. Если критерием оптимальности является минимальная стоимостьрешающего пути, а не его длинна, то поиска в ширину также бывает недостаточно, посколькувозникает сложность комбинаторного характера.
Стратегия поиска вглубину
Программы искусственногоинтеллекта имеют специфическую организацию: имеется начальное состояние; инеобходимо найти путь, приводящий к конечному состоянию, т. е. цели. Где конечноесостояние может представлять собой набор приемлемых состояний.
Программа должна искатьтребуемые состояния «шагая» от состояния к состоянию при этом,распознавая ситуации, когда она находит цель или попадает в тупик.
Стратегия поиска вглубину основана на тщательном исследовании последовательности одного вариантавыбора до изучения других вариантов.
Первоначально исследуетсясамая первая левая ветвь дерева, когда процесс поиска заходит в тупик.Интерпретатор возвращается вверх, в последний пункт выбора. Где имеютсянеизученные альтернативные варианты движения.
Поиск в глубину наиболееадекватен рекурсивному стилю программирования.4. Формализация
Формализация знаний —разработка базы знаний на языке представления знаний, который, с одной стороны,соответствует структуре поля знаний, а с другой — позволяет реализоватьпрототип системы на следующей стадии программной реализации.
Исходя из полученныхзнаний, в пункте 3, знания можно представить в виде продукционной модели:
Если есть дорога из А в Б, то из Аможно переехать в Б.
Причем информация оналичие дорог не избыточна, что выражено в том, что если есть дорога из А в Б,то можно переехать из А в Б, но наоборот невозможно, то есть из Б в А. Дляпреодоления данного затруднения можно пойти двумя путями:
1. Добавить еще одно утверждение впродукционной модели, что если есть дорога из А в Б, то можно переехать нетолько из А в Б, но и из Б в А.
2. Программно реализовать, чтобы системапонимала, что наличие дороги означает, что можно переехать из А в Б, но инаооброт.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):- 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 — определяет принадлежит ли элементсписку, реализованное следующим кодом:
member(Head,[Head|_]).
member(Head,[_|Tail]):-member(Head,Tail).
Для реализации выбораоптимального выбора (минимальная длина) среди перечня путей введем отношение db0 и 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
retract(db_path(X,Y,P,C)),assert(db_path(X,Y,MP,MC)), db(X,Y).
Отношение db0 инициализирует первый возможныйпуть. Если данный путь не единичен, то 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,«ExpertSystem»,1,3,22,71),clearwindow,
write(«Enterthe name of cities»),nl,
write(«Thefirst city: „), readln(First),nl,
write(“Thesecond 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(“Optimumway: „),write(MP),nl,
write(“Lengthof 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
retract(db_path(X,Y,P,C)),assert(db_path(X,Y,MP,MC)), db(X,Y).
db(_,_). 6. Тестирование программы
а) Пусть имеем следующийграф:
/>
/> Рис.2 Рис.2а
Ищем оптимальный путь из a в х, согласно графуоптимальный путь содержит следующие узлы: acfx, что изображено на рис.2а.
Программа:
/>
Данные ручного расчета ипрограммы совпадают.
б) Изменим длину ребра a-c:
/>
/> Рис.3 Рис.3а
Ищем оптимальный путь из a в х, согласно графуоптимальный путь содержит следующие узлы: abefx, что изображено на рис.3а.
Программа:
/>
Данные ручного расчета ипрограммы совпадают.
в) Изменим длинуребра b-d:
/>
/> Рис.4 Рис.4а
Ищем оптимальный путь из a в х, согласно графуоптимальный путь содержит следующие узлы: abdefx, что изображено на рис.4а.
Программа:
/>
Данные ручного расчета ипрограммы совпадают.
Литература
1. И 57. Использование Турбо-Пролога:Пер. с англ.-М.: Мир, 1990.-410 с., ил.
2. Б 87. Братко. Программирование наязыке Пролог для искусственного интеллекта: Пер. с англ. -М.: Мир, 1990.- 560с., ил