49473 (Экспертная система для решения задачи о коммивояжере)
Описание файла
Документ из архива "Экспертная система для решения задачи о коммивояжере", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "49473"
Текст из документа "49473"
Саратовский государственный технический университет
Кафедра СИИ
Курсовая работа
по Методам искусственного интеллекта
Экспертная система для решения задачи о коммивояжере
Выполнил:
Проверил:
Саратов 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):- 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,"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 retract(db_path(X,Y,P,C)), assert(db_path(X,Y,MP,MC)), db(X,Y). db(_,_). а) Пусть имеем следующий граф: Рис.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 с., ил
6. Тестирование программы
Литература