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

Кафедра СИИ

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

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

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

Выполнил:

Проверил:

Саратов 2009 г.

Содержание

 

1.Постановка задачи

2.Идентификация проблемы

3.Извлечение знаний

4.Формализация

5.Описание программы

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

7.Литература

1. Постановка задачи

Целю, данной курсовой работы, является разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog.

2. Идентификация проблемы

Задача о коммивояжере довольно распространенная задача. Применительно к производству ее можно интерпретировать так, имеется один станок и набор деталей. Время обработки деталей на станке одинаковое, но время переналадки станка разное. Требуется обработать все детали, но за минимальный срок. Так же ее можно адаптировать к поиску минимально короткого пути на карте между двумя пунктами. Например, в системе GPS-навигации для автомобилей, ищущей кратчайший путь между двумя пунктами на карте, имея карту дорог.

Данная проблематики имеет широкое применение в повседневной жизни.

В данной курсовой работе рассмотрим проблему поиска кратчайшего пути между двумя пунктами на карте, имея граф «Карта Саратовской область», в котором вершины графа это города, а дуги, соединяющие вершины-города, являются дорогами.

Необходимые ресурсы:

­  Литература по кибернетике

­  ПК с системой Prolog

­  Эксперт

Источниками знаний в данном случае выступают:

­  Книги по кибернетике

­  Эксперт - профессор каф. СИИ Петров С.В.

3. Извлечение знаний

Извлечение знаний — это процедура взаимодействия инженера по знаниям с источником знаний, в результате которой становится явным процесс рассуждений экспертов при принятии решения и структура их представлений о предметной области.

Излечение знаний будем производить путем анализа литературы по кибернетике. Для дополнительного уточнения прибегнем к консультациям эксперта.

Представим карту в виде графа. Граф - это сеть, состоящая из узлов, соединенных дугами (рис.1). Узлами в данном случае являются городами, а дуги - будут являться городами, соединяющие соответствующие узлы (города). Наличие дороги между городами означает наличие дуги между соответствующими узлами.

Рис. 1

Поиск кратчайшего пути между двумя городами означает поиск кратчайшего пути между двумя узлами графа.

В процессе поиска, как правило, возникает проблема, как обрабатывать альтернативные пути поиска.

В этой связи в Прологе существуют две основные стратегии:

1.  Поиск в глубину

2.  Поиск в ширину

Стратегия поиска в ширину

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

Общие принципы построения поиска в ширину:

1) Если первый элемент (вершина) первого пути (в списке путей) - это целевая вершина, то взять этот путь в качестве решения.

2) Иначе удалить первый путь и породить множество продолжений этого пути на один шаг.

Множество продолжений добавляется к списку путей в конец.

Стратегия поиска в ширину гарантирует получение кратчайшее решение первым, в отличие от стратегии поиска в глубину. ............