Постановка задачи эвристического поиска

СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

 

 

РЕШЕНИЕ ЗАДАЧИ ЭВРИСТИЧЕСКОГО ПОИСКА
В ПРОСТРАНСТВЕ СОСТОЯИЙ

 

 

Методические указания
 к выполнению лабораторной работы
для студентов всех форм обучения
специальностей  230201 – «Информационные системы
 и технологии», 230104 – «Системы автоматизированного
проектирования»,  050501 – «Профессиональное обучение»

 

БРЯНСК 2006

УДК 004.896

 

Системы искусственного интеллекта. Решение задачи эвристического поиска в пространстве состояний. Методические указания к выполнению лабораторной работы для студентов всех форм обучения специальностей 230201 – «Информационные системы и технологии», 230104 – «Системы автоматизированного проектирования», 050501 – «Профессиональное обучение». – Брянск: БГТУ, 2006. – 16 с.

 

Разработал:

П.В. Казаков, канд. техн. наук,  доц.,

В.А. Шкаберин, канд. техн. наук, доц.

 

 

Рекомендовано кафедрой

«Компьютерные технологии и системы» БГТУ

(протокол №  6  от 7.04.2005)

ЦЕЛЬ РАБОТЫ

Лабораторная работа познакомит студентов, изучающих курсы «Системы искусственного интеллекта», «Интеллектуальные информационные системы», «Интеллектуальные подсистемы САПР» с особенностью организации планирования решения задач с использованием методов эвристического программирования. Это позволит совершенствовать навыки учащихся в определении стратегии поиска наилучшего плана действий при решении сложно структурированных задач. В методическом указании изложены общие положения метода эвристического поиска в пространстве состояний, а также приводится примеры решения подобных задач.

Целью работы является оказание методической помощи студентам при определении оптимального плана действий, ведущего из начального состояния задачи в одно из конечных.

Задачи лабораторной работы:

- освоить принципы эвристического поиска;

- разобрать алгоритм поиска пути на графе пространства состояний;

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

Продолжительность лабораторной работы - 4 часа. Первые два часа отводятся на ознакомление с методическими указаниями (п.1-3), оставшиеся часы рассчитаны на решение индивидуальных заданий к лабораторной работе (п.4) и оформление отчета по результатам их выполнения.

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

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Последовательность выполнения лабораторной работы.

1. Изучить теоретические положения и разобрать предлагаемые в методических указаниях примеры.

2. Решить прилагаемые индивидуальные задания.

Руководством к пункту 1 являются §1 - 3 методических указаний. Дополнительно можно воспользоваться книгами [1-3].

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Постановка задачи эвристического поиска

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

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

где S – множество состояний;

 - множество начальных состояний;

 - множество конечных состояний;

F – множество операторов.

Метод решения задачи  называется методом эвристического поиска, если он на каждом шаге находит все возможные применения операторов к данному текущему состоянию, а порядок рассмотрения состояний и порядок применения операторов управляется свойствами уже рассмотренных до этого шага состояний.