Анализ эффективности процедур генерации

Федеральное Государственное Автономное Образовательное  Учреждение

Высшего профессионального  образования

Сибирский Федеральный  Университет

Институт космических и информационных технологий

Кафедра «Системы искусственного интеллекта»

 

 

Специальность: «Информационные системы и технологии (230201.65»

 

 

 

 

 

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

АНАЛИЗ  ЭФФЕКТИВНОСТИ

ПРОЦЕДУР  ГЕНЕРАЦИИ

 

 

 

 

 

Выполнили: студенты группы КИ09-15

Наговицина  К.В.

Проверил: Перфильев Д.А.

 

 

 

 

Красноярск, 2012

 

Цель:

Дать  представление о возможности  эффективного использования

различных процедур генерации в слепых методах поиска в решении задач в пространстве состояний.

 

Задача:

Провести  относительный анализ эффективности  использования различных процедур генерации в слепых методах поиска при различных условиях проведения поиска на графе состояний для  игры «Перестановка».

 

Результат:

Должна  быть создана программа, выполняющая  всякий слепой поиск

решения. Представлены графики, анализирующие достоинства  и недостатки процедур генерации  в различных условиях неуправляемого поиска.

 

 

Пункт 1

Игра  «Перестановка»

Описание  задачи.

Суть игры «Перестановка» - получение из некоторой  заданной последовательности различных  символов другую последовательность из этих же символов.

В качестве символов в игре используются неповторяющиеся  цифры. Количество полученных последовательностей  равно n!, где n – количество цифр в  последовательности. На рисунке показана схема задачи перестановка

 

 

Для начала поиска начальное состояние игры должно отличаться от искомого расположением  символов.

Цель игры «Перестановка» является поиск и  получение из некоторого заданного  состояния конечное

Задачей является выбор наилучшего метода поиска для  поставленных целей игры. Задача выбора метода поиска предполагает анализ эффективности  методов поиска  с позиции выбора вида генерации, проверки и планирования.

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

 

 

 

 

 

 

 

Преобразование  последовательностей выполняется  следующим образом:

1. в последовательности выделяются пары соседних чисел. Например, для последовательности 123456 парами являются (1,2), (2,3) … (5,6). Количество пар равно количеству цифр в последовательности минус один.
2. первое число пары переносится в начало последовательности, а второе – в конец. Такое преобразование называется прямым. При обратном преобразовании первое число пары переносится в конец последовательности, а второе – в начало.

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

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

При проведении игры «Перестановка» следует учитывать  следующие условия:

1. если количество элементов n в последовательности четное и применяется прямое правило, то количество всех возможных последовательностей равно n!/2;
2. если количество элементов n в последовательности нечетное и применяется прямое правило, то количество всех возможных последовательностей равно n!;
3. если количество элементов n в последовательности четное и применяется обратное правило, то количество всех возможных последовательностей равно n!;
4. если количество элементов n в последовательности нечетное и применяется обратное правило, то количество всех возможных последовательностей равно n!/2;

Из условий следует, что  множество последовательностей  в игре «Перестановка» включает непересекаемые подмножества. Поэтому при задании  начальной и искомой последовательности это следует учитывать.

Определить до начала поиска принадлежность начальной и искомой  последовательности к одному множеству  поиска в игре «Перестановка» в условиях 1и 4 можно, если использовать следующее  правило:  «Если начальная последовательность отличается от искомой расположением  знаков в первой или второй паре вида 123456 213654 или 132456 321465, то эти состояния находятся в разных пространствах поиска».

Следовательно, как и в  условии  1, поиск последовательности (2134) из последовательности (1234) или  последовательности (2143) так и при  нечетной последовательности цифр в  условии 4 поиск последовательности (123) из последовательности (213) или последовательности (132) не будет выполнен.

 

 

Пункт 2

Матрица смежности для прямого правила

		1	2	3	4	5	6	7	8	9	10	11	12
		1234	2143	1423	1342	3124	2314	4213	4132	3412	3242	2431	4321
1	1234	0	1	1	1	1	1	0	0	0	0	0	0
2	2143	1	0	1	0	0	1	1	0	0	0	1	0
3	1423	1	1	0	1	0	0	1	1	0	0	0	0
4	1342	1	0	1	0	1	0	0	1	1	0	0	0
5	3124	1	0	0	1	0	1	0	0	1	1	0	0
6	2314	1	1	0	0	1	0	0	0	0	1	1	0
7	4213	0	1	1	0	0	0	0	1	0	0	1	1
8	4132	0	0	1	1	0	0	1	0	1	0	0	1
9	3412	0	0	0	1	1	0	0	1	0	1	0	1
10	3241	0	0	0	0	1	1	0	0	1	0	1	1
11	2431	0	1	0	0	0	1	1	0	0	1	0	1
12	4321	0	0	0	0	0	0	1	1	1	1	1	0

 

Анализ матрицы  смежности для прямого правила:

Матрица смежности  симметрична относительно главной  диагонали. Главная диагональ состоит  из нулей. Проанализировав матрицу, можно предположить, что она является совокупностью матриц орграфов «кольцо» и «дерево».

Анализ матрицы  инцидентности для прямого правила:

В строке (так  же как и в столбце) количество единиц равно количеству нулей. В  столбце хорошо видно, от какой вершины  связь начинается (обозначается «1») и где заканчивается (обозначается «0»).

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

 

 

 

 

 

 

 

 

Матрица смежности для обратного правила

Анализ матрицы  смежности для обратного правила:

Матрица смежности  симметрична относительно главной  диагонали. Главная диагональ состоит  из нулей. Проанализировав матрицу, можно предположить, что она является совокупностью матриц орграфов «кольцо» и «дерево».

Анализ матрицы  инцидентности для прямого правила:

В строке (так  же как и в столбце) количество единиц равно количеству нулей. В  столбце хорошо видно, от какой вершины  связь начинается (обозначается «1») и где заканчивается (обозначается «0»).

Отсутствуют корневые и терминальные вершины. Каждая вершина имеет равное количество входящих и исходящих вершин (три  входящих и три исходящих). Две  связи дублируют самих себя. Внутри орграфа имеются прямоугольные  плоскости.

 

Полученные  последовательности представляют собой  пространство состояний S={s1, s2, … sm}.

Между состояниями  пространства поиска существует отношение  «род-вид»:

Родовые признаки:

1. Элементы пространства состояний – цифры.
2. Равное количество цифр – числа четырехзначные.
3. Нет корневых и терминальных вершин.
4. Количество связей (шесть связей). Выходит 3 связи (n-1) и 3 связи входят (n-1).
5. У каждой вершины есть хотя бы одна связь, которая повторяется.
6. Если поменять местами соседние цифры в вершине – то вершина станет принадлежать другому подпространству.

Видовые признаки:

1. Правила перебора (прямое правило, обратное правило).
2. Количество вершин.
3. Расположение в пространстве.
4. Без повторяющихся связей орграф, образованный прямым правилом, имеет пять связей, а орграф, образованный обратным правилом – четыре связи.

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

 

Анализ  полученных данных и вывод

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

Результаты выхода программы для  последовательности состояний от 3 до 8 элементов:

 1). Количество итераций – 500  (Рис.1, Рис.2)

 

Рис.1 График математического ожидания для 500 итераций

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.2 График дисперсии для 500 итераций

 

 

 

 

2). Количество итераций – 1000  (Рис.3, Рис.4)

 

Рис.3 График математического  ожидания для 1000 итераций

 

 

Рис.4 График дисперсии для 1000 итераций

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3). Количество итераций – 1500  (Рис.5, Рис.6)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.5 График математического  ожидания для 1500 итераций

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.6 График дисперсии для 1500 итераций

 

 

 

 

 

 

 

 

 

 

 

 

Таблицы значений Математического  ожидания и Дисперсии

 

Кол-во итераций - 500

		3	4	5	6	7	8
По Лучу	МО Д	5,784 32,481	31,032 922, 687	123,236 16409,81	791,096 496338,3	5124,9 2,884912Е+07	43037,96 1,587865Е+09
В Глубину	МО Д	2 1	13,432 111,281	35,176 960,27	177,204 32653,06	865,84 730075,4	5960,224 4,037263Е+07
Параллельный	МО Д	3,224 7,4938	1 1	1 1	165,124 30058,27	822,784 651917,9	6243,236 4,068731Е+07
В Ширину	МО Д	1,002 0,00199	1,002 0,00199	1,006 0,01796	1,008 0,03193	1,01 0,04989	1,012 0,07185