Исходные данные для решения задачи №2

№ варианта

Матрица весов графа

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	5	2	3	0	0	0	0	0	0	0	0
X1	0	0	2	0	2	0	0	0	0	0	0	0
X2	0	0	0	3	0	3	0	0	0	0	0	0
X3	0	0	0	0	0	7	3	0	0	0	0	0
X4	0	0	0	0	0	1	0	4	0	0	0	0
X5	0	0	0	0	0	0	5	0	2	0	0	0
X6	0	0	0	0	0	0	0	0	0	5	0	0
X7	0	0	0	0	0	0	0	0	2	0	0	5
X8	0	0	0	0	0	0	0	0	0	3	4	0
X9	0	0	0	0	0	0	0	0	0	0	0	4
X10	0	0	0	0	0	0	0	0	0	0	0	6
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	2	3	5	0	0	0	0	0	0	0	0
X1	0	0	0	2	4	0	0	0	0	0	0	0
X2	0	0	0	3	0	4	0	0	0	0	0	0
X3	0	0	0	0	2	2	0	0	0	0	0	0
X4	0	0	0	0	0	0	3	0	2	0	0	0
X5	0	0	0	0	0	0	0	5	3	0	0	0
X6	0	0	0	0	0	0	0	0	4	6	0	0
X7	0	0	0	0	0	0	0	0	1	0	4	0
X8	0	0	0	0	0	0	0	0	0	1	4	4
X9	0	0	0	0	0	0	0	0	0	0	0	4
X10	0	0	0	0	0	0	0	0	0	0	0	3
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	2	6	4	0	0	0	0	0	0	0	0
X1	0	0	3	0	5	0	0	0	0	0	0	0
X2	0	0	0	1	1	2	2	0	0	0	0	0
X3	0	0	0	0	0	0	3	0	0	0	0	0
X4	0	0	0	0	0	2	0	6	3	0	0	0
X5	0	0	0	0	0	0	1	0	4	0	0	0
X6	0	0	0	0	0	0	0	0	3	7	0	0
X7	0	0	0	0	0	0	0	0	2	0	3	5
X8	0	0	0	0	0	0	0	0	0	2	6	0
X9	0	0	0	0	0	0	0	0	0	0	4	4
X10	0	0	0	0	0	0	0	0	0	0	0	5
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	3	7	2	0	0	0	0	0	0	0	0
X1	0	0	3	0	5	0	0	0	0	0	0	0
X2	0	0	0	3	3	4	0	0	0	0	0	0
X3	0	0	0	0	0	6	0	0	0	0	0	0
X4	0	0	0	0	0	0	4	3	0	0	0	0
X5	0	0	0	0	0	0	3	0	0	5	0	0
X6	0	0	0	0	0	0	0	1	6	2	0	0
X7	0	0	0	0	0	0	0	0	3	0	5	8
X8	0	0	0	0	0	0	0	0	0	2	1	0
X9	0	0	0	0	0	0	0	0	0	0	3	4
X10	0	0	0	0	0	0	0	0	0	0	0	3
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	2	7	1	0	0	0	0	0	0	0	0
X1	0	0	4	0	6	0	0	0	0	0	0	0
X2	0	0	0	5	3	2	0	0	0	0	0	0
X3	0	0	0	0	0	3	9	0	0	0	0	0
X4	0	0	0	0	0	2	0	4	7	0	0	0
X5	0	0	0	0	0	0	0	7	0	0	0	0
X6	0	0	0	0	0	0	0	3	0	0	6	0
X7	0	0	0	0	0	0	0	0	3	2	0	0
X8	0	0	0	0	0	0	0	0	0	1	0	2
X9	0	0	0	0	0	0	0	0	0	0	2	4
X10	0	0	0	0	0	0	0	0	0	0	0	4
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	6	4	2	0	0	0	0	0	0	0	0
X1	0	0	2	0	6	0	0	0	0	0	0	0
X2	0	0	0	1	0	3	2	0	0	0	0	0
X3	0	0	0	0	0	0	7	0	0	0	0	0
X4	0	0	0	0	0	2	0	3	5	0	0	0
X5	0	0	0	0	0	0	4	5	0	0	0	0
X6	0	0	0	0	0	0	0	0	0	0	6	0
X7	0	0	0	0	0	0	0	0	4	1	2	0
X8	0	0	0	0	0	0	0	0	0	3	0	7
X9	0	0	0	0	0	0	0	0	0	0	0	4
X10	0	0	0	0	0	0	0	0	0	0	0	8
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	7	2	6	0	0	0	0	0	0	0	0
X1	0	0	3	0	1	5	0	0	0	0	0	0
X2	0	0	0	3	4	0	0	0	0	0	0	0
X3	0	0	0	0	2	0	3	4	0	0	0	0
X4	0	0	0	0	0	1	0	0	0	0	0	0
X5	0	0	0	0	0	0	5	0	7	0	0	0
X6	0	0	0	0	0	0	0	0	2	4	0	0
X7	0	0	0	0	0	0	0	0	0	5	2	9
X8	0	0	0	0	0	0	0	0	0	3	6	3
X9	0	0	0	0	0	0	0	0	0	0	3	0
X10	0	0	0	0	0	0	0	0	0	0	0	5
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	3	5	2	0	0	0	0	0	0	0	0
X1	0	0	4	0	7	8	0	0	0	0	0	0
X2	0	0	0	4	0	7	2	0	0	0	0	0
X3	0	0	0	0	0	0	8	0	0	0	0	0
X4	0	0	0	0	0	4	0	5	2	0	0	0
X5	0	0	0	0	0	0	0	0	2	3	0	0
X6	0	0	0	0	0	0	0	0	0	4	0	0
X7	0	0	0	0	0	0	0	0	2	0	2	3
X8	0	0	0	0	0	0	0	0	0	4	1	0
X9	0	0	0	0	0	0	0	0	2	0	3	4
X10	0	0	0	0	0	0	0	0	0	0	0	8
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	5	4	2	0	0	0	0	0	0	0	0
X1	0	0	2	0	5	3	0	0	0	0	0	0
X2	0	0	0	3	2	3	0	0	0	0	0	0
X3	0	0	0	0	0	2	4	0	0	0	0	0
X4	0	0	0	0	0	3	0	3	0	0	0	0
X5	0	0	0	0	0	0	5	5	3	0	0	0
X6	0	0	0	0	0	0	0	0	2	6	0	0
X7	0	0	0	0	0	0	0	0	4	0	1	7
X8	0	0	0	0	0	0	0	0	0	1	3	0
X9	0	0	0	0	0	0	0	0	0	0	5	8
X10	0	0	0	0	0	0	0	0	0	0	0	9
X11	0	0	0	0	0	0	0	0	0	0	0	0

W	X0	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11
X0	0	3	7	4	0	0	0	0	0	0	0	0
X1	0	0	3	0	7	0	0	0	0	0	0	0
X2	0	0	0	2	0	2	0	0	0	0	0	0
X3	0	0	0	0	0	3	7	0	0	0	0	0
X4	0	0	0	0	0	4	0	6	0	0	0	0
X5	0	0	0	0	0	0	5	4	2	0	0	0
X6	0	0	0	0	0	0	0	0	4	0	5	0
X7	0	0	0	0	0	0	0	0	5	3	0	0
X8	0	0	0	0	0	0	0	0	0	4	3	8
X9	0	0	0	0	0	0	0	0	0	0	0	2
X10	0	0	0	0	0	0	0	0	0	0	0	6
X11	0	0	0	0	0	0	0	0	0	0	0	0

ОФОРМЛЕНИЕ И ПОРЯДОК КОНТРОЛЯ РЕЗУЛЬТАТОВ

Результатом выполнения лабораторной работы являются последовательно решенные задания и разработанная компьютерная программа.

Отчет о лабораторной работе оформляется на листах формата A4 и сдается в написанном от руки или распечатанном виде. Отчет должен содержать задание к лабораторной работе, построенные графы пространства состояний, а также основные и промежуточные этапы решения индивидуальных заданий. Кроме этого, для задачи 2 должен быть представлен листинг компьютерной программы ее решения.

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

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

1. Что такое эвристика?

2. В каких случаях целесообразно применять эвристики?

3. Как представляется пространство состояний?

4. Опишите основные шаги алгоритма эвристического поиска в пространстве состояний.

5. Почему эвристические методы поиска эффективней полного перебора пространства состояний?

6. Опишите алгоритм поиска пути на графе. В каком случае его использование наиболее эффективно?

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

1. Искусственный интеллект: в 3 кн.: Справ. / под ред. Э.В. Попова. – М.: Радио и связь, 1990. – 464 с.

2. Лорьер, Ж. Л. Системы искусственного интеллекта / пер. с фр.
Ж.Л. Лорьер. - М.: Мир, 1991. – 568 с.

3. Иванов, Б.Н. Дискретная математика / Б.Н. Иванов. – М.: Лаборатория базовых знаний, 2001. – 288 с.

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

КАЗАКОВ ПАВЕЛ ВАЛЕРЬЕВИЧ

ШКАБЕРИН ВИТАЛИЙ АЛЕКСАНДРОВИЧ

Научный редактор Ю.М. Казаков

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

Компьютерный набор П.В. Казаков