Игра в Восемь, Изучение основных стратегий решения задач (Лабораторная работа № 3)

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра ПСиБД

Лабораторная работа №3

по курсу

Системы искусственного интеллекта

Вариант: 10 (3)

Выполнили:   Лисовой А.

                        Айбулатова Ю.

                        Славгородский И.

Преподаватели:

Журавлев В. А.

Копылова А. В.

Новосибирск,2007

Цель работы: Изучение основных стратегий решения задач. Приобретение  навыков  выбора  адекватных  стратегий в зависимости от типа задач. Выбор инструмента для реализации этих стратегий.

Задание:  "Игра в Восемь".

Суть игры:

            В головоломке используется восемь перемещаемых фишек, пронумерованных цифрами от 1 до 8. Фишки располагаются в девяти ячейках, образующим матрицу 3 на 3. Одна из ячеек всегда пуста, и любая смежная с ней фишка может быть передвинута в эту пустую ячейку. Можно сказать и по-другому, что пустой ячейке разрешается перемещаться, меняясь местами с любой из смежных с ней фишек. Конечная ситуация – это некоторая заранее заданная конфигурация фишек, как показано на рис.

1	3					1	2	3
8	2	4				8		4
7	6	5				7	6	5

Выбор «инструмента»:

Для реализации был выбран метод, разработанный Хартом, Нильсоном и Рафаэлем (1968 и 1972), известный под названием «алгоритм А*». Поскольку мы сами задаем исходную ситуацию и конечную цель, то выбор метода был обоснован существующей теоремой, гласящей: алгоритм А* приводит к цели за конечное число шагов, если существует конечная последовательность действий, которая ведет от исходной ситуации к решению.

            Алгоритм А*, как и другие градиентные алгоритмы являются строго численными, поэтому исключается формальный анализ каждой ситуации. Алгоритм основан на оценке стоимости некоторого решения. Нельзя заранее обнаружить тупики и петли. Так, если в нашей игре исходная ситуация будит иметь вид как:

8	2	3				1	2	3
1	6	4				8		4
7		5				7	6	5

то чтобы доказать, что эта задача не имеет решения, алгоритм А* должен будет исследовать абсолютно все возможные случаи и поэтому оказывается бесполезным.

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

Алгоритм  А*:

Всякой ситуации S,полученной из исходной ситуации, придается численная оценка

f(S)=g(S)+h(S) , где g(S)-реальная текущая стоимость ситуации S(в нашей задаче =1 ),h(S)-эвристическая функция , которая оценивает стоимость наилучшей последовательности действий, начинающейся с S и заканчивающейся решением.

Этап 0:

Создать поисковой граф R=(E,A),где S0E(исходная ситуация )

f(S0) O(E разделяется на 2 подмножества ситуаций: O(открытые) и F(закрытые))

OS0;F0;Делать до тех пор пока О 0

Этап 1:

На множестве выбрать ситуацию  S, такую ,что f(S) минимально.

OO-S;FF+S;

Если S решение, то конец.

Этап 2:

Если S  не решение, то развертывать ситуацию S путем построения ситуаций Si(0<=i<=ns), полученных из путем выполнения возможных действий.

Этап 3:

Для каждой порожденной ситуации подсчитать f (Si) : f (Si)= g(Si)+h(Si)(при h(Si)<= h*(Si)).

Этап 4:

Включать в О не входящие ни в О, ни  в F ситуации вместе с соответствующими значениями оценочной функции; для тех  Si,которые уже входят в О или  F, установить

f (Si)min (f (Si) – старое, f (Si)- новое);в случае принадлежности к F:сделать FF- Si;ОO+ Si

Конец цикла «до тех пор пока »

Конец А*

Эвристический поиск:

ver(B,F/G)-дерево , состоящее из 1 вершины (листа); B-вершина пространства состояний ;

G: g(B)(стоимость уже найденного пути из стартовой вершины в B);F: f(B)=G+h(B).

der(B,F/G,Пд)- дерево с непустыми поддеревьями ; B-корень дерева , Пд- список поддеревьев; G:g(B); F- уточненное значение f(B), т.е. значение f(B) для наиболее перспективного приемника вершины B;список Пд упорядочен в порядке возрастания f-оценок поддеревьев.

broad(путь,дер,предел,дер1,Решение,ЕстьРеш)-эта процедура расширяет текущее поддерево, пока f-оценка  остается = или <, чем предел.

путь- путь между стартовой вершиной и корнем дерева дер.