Саратовский государственный технический университет
Кафедра СИИ
Курсовая работа
по Методам искусственного интеллекта
Экспертная система для решения задачи о коммивояжере
Выполнил:
Проверил:
Саратов 2009 г.
Содержание
Книги по кибернетике
Эксперт - профессор каф. СИИ Петров С.В.
Рис. 1
Поиск кратчайшего пути между двумя городами означает поиск кратчайшего пути между двумя узлами графа.
В процессе поиска, как правило, возникает проблема, как обрабатывать альтернативные пути поиска.
В этой связи в Прологе существуют две основные стратегии:
1. Поиск в глубину
2. Поиск в ширину
Стратегия поиска в ширину
Поиск в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться больше в ширину. При поиске в ширину приходится сохранять все множество альтернативных вершин (а не одну вершину как при поиске в глубину). Хранятся не только вершины, но и множество путей, которые хранятся в виде списка.
Общие принципы построения поиска в ширину:
1) Если первый элемент (вершина) первого пути (в списке путей) - это целевая вершина, то взять этот путь в качестве решения.
2) Иначе удалить первый путь и породить множество продолжений этого пути на один шаг.
Множество продолжений добавляется к списку путей в конец.
Стратегия поиска в ширину гарантирует получение кратчайшее решение первым, в отличие от стратегии поиска в глубину. Если критерием оптимальности является минимальная стоимость решающего пути, а не его длинна, то поиска в ширину также бывает недостаточно, поскольку возникает сложность комбинаторного характера.
Стратегия поиска в глубину
Программы искусственного интеллекта имеют специфическую организацию: имеется начальное состояние; и необходимо найти путь, приводящий к конечному состоянию, т. е. цели. Где конечное состояние может представлять собой набор приемлемых состояний.
Программа должна искать требуемые состояния "шагая" от состояния к состоянию при этом, распознавая ситуации, когда она находит цель или попадает в тупик.
Стратегия поиска в глубину основана на тщательном исследовании последовательности одного варианта выбора до изучения других вариантов.
Первоначально исследуется самая первая левая ветвь дерева, когда процесс поиска заходит в тупик. Интерпретатор возвращается вверх, в последний пункт выбора. Где имеются неизученные альтернативные варианты движения.
Поиск в глубину наиболее адекватен рекурсивному стилю программирования.
"граничный случай": начальная вершина пути 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<C,!,
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<C,!,
retract(db_path(X,Y,P,C)), assert(db_path(X,Y,MP,MC)), db(X,Y).
db(_,_).
Рис.2 |
Рис.2а |
Рис.3 |
Рис.3а |
Рис.4 |
Рис.4а |
! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
→ | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
→ | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
→ | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
→ | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
→ | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
→ | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
Курсовая работа | Политический маркетинг |
Курсовая работа | Создание и внедрение мембранного аппарата |
Курсовая работа | Социальные услуги |
Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
Курсовая работа | Карибский кризис |
Курсовая работа | Сахарный диабет |
Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |