Саратовский государственный технический университет
Кафедра СИИ
Курсовая работа
по Методам искусственного интеллекта
Экспертная система для решения задачи о коммивояжере
Выполнил:
Проверил:
Саратов 2009 г.
Содержание
1.Постановка задачи
2.Идентификация проблемы
3.Извлечение знаний
4.Формализация
5.Описание программы
6.Тестирование программы
7.Литература
Целю, данной курсовой работы, является разработка, макетирование и реализация экспертной системы для решения задачи о коммивояжере, используя возможности языка Prolog.
2. Идентификация проблемыЗадача о коммивояжере довольно распространенная задача. Применительно к производству ее можно интерпретировать так, имеется один станок и набор деталей. Время обработки деталей на станке одинаковое, но время переналадки станка разное. Требуется обработать все детали, но за минимальный срок. Так же ее можно адаптировать к поиску минимально короткого пути на карте между двумя пунктами. Например, в системе GPS-навигации для автомобилей, ищущей кратчайший путь между двумя пунктами на карте, имея карту дорог.
Данная проблематики имеет широкое применение в повседневной жизни.
В данной курсовой работе рассмотрим проблему поиска кратчайшего пути между двумя пунктами на карте, имея граф «Карта Саратовской область», в котором вершины графа это города, а дуги, соединяющие вершины-города, являются дорогами.
Необходимые ресурсы:
Литература по кибернетике
ПК с системой Prolog
Эксперт
Источниками знаний в данном случае выступают:
Книги по кибернетике
Эксперт - профессор каф. СИИ Петров С.В.
3. Извлечение знанийИзвлечение знаний — это процедура взаимодействия инженера по знаниям с источником знаний, в результате которой становится явным процесс рассуждений экспертов при принятии решения и структура их представлений о предметной области.
Излечение знаний будем производить путем анализа литературы по кибернетике. Для дополнительного уточнения прибегнем к консультациям эксперта.
Представим карту в виде графа. Граф - это сеть, состоящая из узлов, соединенных дугами (рис.1). Узлами в данном случае являются городами, а дуги - будут являться городами, соединяющие соответствующие узлы (города). Наличие дороги между городами означает наличие дуги между соответствующими узлами.
Рис. 1
Поиск кратчайшего пути между двумя городами означает поиск кратчайшего пути между двумя узлами графа.
В процессе поиска, как правило, возникает проблема, как обрабатывать альтернативные пути поиска.
В этой связи в Прологе существуют две основные стратегии:
1. Поиск в глубину
2. Поиск в ширину
Стратегия поиска в ширину
Поиск в ширину предусматривает переход в первую очередь к вершинам, ближайшим к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться больше в ширину. При поиске в ширину приходится сохранять все множество альтернативных вершин (а не одну вершину как при поиске в глубину). Хранятся не только вершины, но и множество путей, которые хранятся в виде списка.
Общие принципы построения поиска в ширину:
1) Если первый элемент (вершина) первого пути (в списке путей) - это целевая вершина, то взять этот путь в качестве решения.
2) Иначе удалить первый путь и породить множество продолжений этого пути на один шаг.
Множество продолжений добавляется к списку путей в конец.
Стратегия поиска в ширину гарантирует получение кратчайшее решение первым, в отличие от стратегии поиска в глубину. Если критерием оптимальности является минимальная стоимость решающего пути, а не его длинна, то поиска в ширину также бывает недостаточно, поскольку возникает сложность комбинаторного характера.
Стратегия поиска в глубину
Программы искусственного интеллекта имеют специфическую организацию: имеется начальное состояние; и необходимо найти путь, приводящий к конечному состоянию, т. е. цели. Где конечное состояние может представлять собой набор приемлемых состояний.
Программа должна искать требуемые состояния "шагая" от состояния к состоянию при этом, распознавая ситуации, когда она находит цель или попадает в тупик.
Стратегия поиска в глубину основана на тщательном исследовании последовательности одного варианта выбора до изучения других вариантов.
Первоначально исследуется самая первая левая ветвь дерева, когда процесс поиска заходит в тупик. Интерпретатор возвращается вверх, в последний пункт выбора. Где имеются неизученные альтернативные варианты движения.
Поиск в глубину наиболее адекватен рекурсивному стилю программирования.
4. ФормализацияФормализация знаний — разработка базы знаний на языке представления знаний, который, с одной стороны, соответствует структуре поля знаний, а с другой — позволяет реализовать прототип системы на следующей стадии программной реализации.
Исходя из полученных знаний, в пункте 3, знания можно представить в виде продукционной модели:
Если есть дорога из А в Б, то из А можно переехать в Б.
Причем информация о наличие дорог не избыточна, что выражено в том, что если есть дорога из А в Б, то можно переехать из А в Б, но наоборот невозможно, то есть из Б в А. Для преодоления данного затруднения можно пойти двумя путями:
... Architect, Visible Analyst Workbench, EasyCASE), так и новые версии и модификации перечисленных систем. 3 Глава. Разработка концептуальной модели информационной системы для поддержки принятия управленческих решений при формировании маркетинговой стратегии региона Процесс создания и внедрения любой ИС принято разделять на четыре последовательные фазы: анализ, глобальное проектирование ( ...
... . Реакции узлов более высокого уровня менее зависят от позиции и более устойчивы к искажениям. Структура Неокогнитрон имеет иерархическую структуру, ориентированную на моделирование зрительной системы человека. Он состоит из последовательности обрабатывающих слоев, организованных в иерархическую структуру (рис. 10.8). Входной образ подается на первый слой и передается через плоскости, ...
... условиях определенности математическое программирование дает точное решение поставленной задачи. Поэтому необходимости выбирать из нескольких вариантов попросту нет. Таким образом, в условиях определенности "Теория принятия решений" не используется, такими задачами занимается математическое программирование. 2) ЛПР знает вероятность реакции окружающей среды на выбор им той или иной альтернативы. ...
... и эксплуатацию подавляющего большинства ЛС. И этот факт предопределяет проблему прогнозирования затрат, цен, тарифов, т.е. рост капитальных вложений в перспективе требует оценки эффективности их в соответствующем периоде. 5. Методы решения логистических задач Научную базу логистики составляет широкий спектр методов, разработанных в рамках различных дисциплин. Перечислим некоторые из них. ...
0 комментариев