III. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ

Задание 1.1. С использованием стратегии жадного поиска найти маршрут из Рима в Милан. В качестве эвристической функции использовать расстояние по прямой до Милана (см. табл.2). При развертывании узлов вести список развернутых узлов.

Задание 1.2. С использованием алгоритма А* найти маршрут из Рима в Милан. В качестве эвристической функции использовать расстояние по прямой до Милана (см. табл.2). При развертывании узлов вести список развернутых узлов.

Задание 1.3. С использованием стратегии жадного поиска найти путь, который необходимо преодолеть роботу для достижения целевой клетки на поле 5x5 (см. табл.3). При этом необходимо выбрать эвристическую функцию, не обязательно допустимую, для решения этой задачи и составить таблицу ее значений (для всех возможных состояний). Доказать, что для данной задачи результаты жадного поиска будут такими же, что и результаты поиска А*. Сделать выводы о полноте и оптимальности стратегии.

Примеры эвристических функций: 1) расстояние по прямой от начальной клетки до целевой; 2) количество клеток, которые пересекает прямая, проведенная от начальной клетки к целевой; 3) манхэттенское расстояние — суммарное отличие в координатах по вертикали и горизонтали между целевой клеткой и начальной.

Таблица 3

Варианты заданий

Вариант	Карта	Вариант	Карта	Вариант	Карта
1.		2.		3.
4.		5.

Для построения деревьев поиска использовать среду MS Visio.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое информированный поиск?

2. Что измеряет функция оценки f(n)?

3. В чем заключается общий принцип поиска по первому наилучшему совпадению?

4. Что такое эвристическая функция? Какая эвристическая функция называется допустимой?

5. Опишите стратегию жадного поиска?

6. Какая стратегия поиска считается оптимальной и полной?

7. Опишите стратегию поиска по алгоритму А*?

8. Является ли манхэттенское расстояние для задачи 1.3 допустимой эвристикой?

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Рассел, С. Искусственный интеллект: современный подход (AIMA): [пер. с англ.] / С. Рассел, П. Норвиг. – 2-е изд. – М.: Вильямс, 2005. – 1424 с.

Базы данных, знаний, экспертные системы. Информационное обеспечение, базы данных. Решение задач с помощью информированного поиска [Текст] + [Электронный ресурс]: методические указания к выполнению лабораторной работы для студентов очной формы обучения по направлениям подготовки 221700 «Стандартизация и метрология» (бакалавр), 221400 «Управление качеством» (бакалавр).

ЕШИН СЕМЕН ВАСИЛЬЕВИЧ

Научный редактор В.В. Мирошников

Редактор издательства Т.И. Королёва

Компьютерный набор С.В. Ешин

Темплан 2013г., п. __

Подписано в печать __.__.__. Формат 60×84 1/16. Бумага офсетная. Офсетная печать. Усл. печ.л. 0,7. Уч.-изд.л. 0,7. Тираж 20 экз. Заказ . Бесплатно.

Издательство Брянского государственного технического университета

241035, Брянск, бульвар 50-летия Октября, 7, БГТУ. 58-82-49

Лаборатория оперативной полиграфии БГТУ, ул. Институтская, 16

Лаборатория оперативной полиграфии БГТУ, ул. Институтская, 16

Дата добавления: 2015-07-26; просмотров: 171; Нарушение авторских прав

Мы поможем в написании ваших работ!