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


Полнотекстовый поиск по базе:

Главная >> Курсовая работа >> Информатика, программирование


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




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

Кафедра СИИ

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

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

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

Выполнил:

Проверил:

Саратов 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.

Введем отношение

patH2(A,P1,P,D),

означающее, что P1 - завершающий участок пути P.

Между path и patH2 имеет место соотношение:

path(A,Z,P,D) :- patH2(A,[Z],P,D).

Рекурсивное определение отношения patH2 вытекает из следующих посылок:

  • "граничный случай": начальная вершина пути 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).

patH2(A,[A|PatH2],C,[A|PatH2],C).

patH2(A,[Y|PatH2],C1,Path,C):- arca(X,Y,CXY),

not(member(X,PatH2)),C2=C1+CXY,patH2(A,[X,Y|PatH2],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)

patH2(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):- patH2(A,[Z],0,Path,C).

patH2(A,[A|PatH2],C,[A|PatH2],C).

patH2(A,[Y|PatH2],C1,Path,C):- arca(X,Y,CXY), not(member(X,PatH2)),C2=C1+CXY, patH2(A,[X,Y|PatH2],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 с., ил

Похожие работы:

  • Системное автоматизированное проектирование

    Реферат >> Информатика, программирование
    ... их для решения задач комбинаторной оптимизации, коммивояжере, задаче о раскраске карт, задаче оптимизации ... вычислительные системы. ЛЕКЦИЯ ¹8 Тема: “Экспертная система для автоматизированного проектирования” ВВЕДЕНИЕ Экспертная система для решения задач ...
  • Нейрокомпьютерные системы

    Реферат >> Информатика, программирование
    ... Например, широко пропагандировались экспер­тные системы, у которых имеется много ... передает дан­ный случай для разрешения экспертной системе. Решения, принимаемые на этом ... что сходимость решений, полученных по методу Хопфилда для задачи коммивояжера, в сильной ...
  • Теория принятия решений

    Учебное пособие >> Менеджмент
    ... их пошагово. К таким задачам относятся: задача коммивояжера; задача об управлении запасами; задача о ранце; и др. 4) ... решающих правил в задачах принятия решений. - Автоматика и телемеханика, №6, 1981. Джексон П. Введение в экспертные системы: Пер. с англ ...
  • Методы решения логистических задач

    Контрольная работа >> Остальные работы
    ... эффективное функционирование системы, решение задач и достижение ... задача коммивояжера). Задачи массового обслуживания Задачи ... программирование используется для решения задач, у которых ... для принятия решений субъективную словесную экспертную информацию ...
  • Маркетинг и его задачи

    Шпаргалка >> Маркетинг
    ... маркетинга для решения практических задач является основой ... деятельности предприятия, экспертных опросов, наблюдений за ... (политика правительства; система государственного регулирования предпринимательской ... момента для завершения сделки. Коммивояжер должен ...
  • Разработка системы управления продвижения изделий фирмы на рынок

    Реферат >> Маркетинг
    ... сбытовой (в том числе и экспертной) программы предприятия. Исследования этого ... это, прежде всего, работа коммивояжеров, торговых агентов, персонала ... система связей с общественностью. Основная задача – создание и сохранение имиджа. Для решения этой задачи ...
  • Маркетинг

    Учебное пособие >> Маркетинг
    ... Для решения задач распределения широкого плана необходимы компьютерные информационные системы ... - сохраняют традиционную сеть коммивояжеров, поддерживающих личные контакты с ... - разъяснительно-пропагандистские; - экспертно-оценочные; - общественно-бытовые. ...
  • Вопросы к гос. экзаменам ВАВТ

    Реферат >> Экономика
    ... товаров необходим для решения задач технического перевооружения ... для преимуществ в рамках Общей системы преференций для развивающихся стран; • для ... К представительству через коммивояжера применяются общие правила ... групп и экспертных комиссий охватывают ...
  • Маркетинг (шпоры)

    Шпаргалка >> Маркетинг
    ... (для проверки технологического качества). 2 Экспертное (для проверки ... посредника. Для решения задач связанных ... помощью коммивояжеров (являются ... для анализа среды  система маркетинговой информации Система маркетинговой информации - постоянно действующая система ...
  • Методы обработки колличественной и качественной информации при принятии управленческого решения

    Курсовая работа >> Менеджмент
    ... широко используемых в процессе принятия решений экспертных технологий, социологических опросов. ... как полезные для решения тех объем иных задач. Внешняя система направляет ... из деловых (бизнесмены, командировочные, коммивояжеры) и частных посетителей (туристы, ...