Курсовая работа по предмету "Программирование, компьютеры и кибернетика, ИТ технологии"

Узнать цену курсовой по вашей теме


Экспертная система для решения задачи о коммивояжере



Саратовский государственный технический университет

Кафедра СИИ

Курсовая работа

по Методам искусственного интеллекта

Экспертная система для решения задачи о коммивояжере

Выполнил:

Проверил:

Саратов 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<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(_,_).

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а.

Программа:

Данные ручного расчета и программы совпадают.

Литература

1. И 57. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1990.-410 с., ил.

2. Б 87. Братко. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. -М.: Мир, 1990.- 560 с., ил




Не сдавайте скачаную работу преподавателю!
Данную курсовую работу Вы можете использовать для написания своего курсового проекта.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Пишем курсовую работу самостоятельно:
! Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ.
! Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу.
! Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться.
! План курсовой работы Нумерованным списком описывается порядок и структура будующей работы.
! Введение курсовой работы Что пишется в введении, какой объем вводной части?
! Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать.
! Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа.
! Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема.
! Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом.
! Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ.

Читайте также:
Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия.
Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта.
Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты.
Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести.
Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя.
Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика.

Другие популярные курсовые работы:

Сейчас смотрят :

Курсовая работа Купля-продажа жилых помещений
Курсовая работа Управление проектами
Курсовая работа Этапы формирования кредитной политики банка
Курсовая работа Юридическая ответственность
Курсовая работа Рынок драгоценных металлов России
Курсовая работа Суд присяжных: особенности судопроизводства
Курсовая работа Оценка платёжеспособности клиентов банка
Курсовая работа Юридические факты в гражданском праве
Курсовая работа Игровая деятельность младших школьников с задержкой психического развития
Курсовая работа Дидактические игры как средство развития познавательного интереса на уроках обучения грамоте
Курсовая работа Управление системой распределения продукции (на примере ООО "Электротехмаркет")
Курсовая работа Наследование по закону и по завещанию
Курсовая работа Программа диагностики познавательных психических процессов детей младшего школьного возраста
Курсовая работа Оборотные средства организации и эффективность их использования
Курсовая работа Учет затрат на производство продукции растениеводства