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

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

Кафедра СИИ

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

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

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

Выполнил:

Проверил:

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

6. Тестирование программы

а) Пусть имеем следующий граф:

Ищем оптимальный путь из a в х, согласно графу оптимальный путь содержит следующие узлы: a c f x, что изображено на рис.2а.

Программа:

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

б) Изменим длину ребра a-c:

Ищем оптимальный путь из a в х, согласно графу оптимальный путь содержит следующие узлы: a b e f x, что изображено на рис.3а.

Программа:

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

в) Изменим длину ребра b-d:

Ищем оптимальный путь из a в х, согласно графу оптимальный путь содержит следующие узлы: a b d e f x, что изображено на рис.4а.

Программа:

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

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

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