Автор: Пользователь скрыл имя, 05 Ноября 2012 в 14:26, лабораторная работа
Цель:
Дать представление о возможности эффективного использования
различных процедур генерации в слепых методах поиска в решении задач в пространстве состояний.
Федеральное Государственное Автономное Образовательное Учреждение
Высшего профессионального образования
Сибирский Федеральный Университет
Институт космических и
Кафедра «Системы искусственного интеллекта»
Специальность:
«Информационные системы и
Лабораторная работа №1
АНАЛИЗ ЭФФЕКТИВНОСТИ
ПРОЦЕДУР ГЕНЕРАЦИИ
Выполнили: студенты группы КИ09-15
Наговицина К.В.
Проверил: Перфильев Д.А.
Красноярск, 2012
Цель:
Дать представление о возможности эффективного использования
различных процедур генерации в слепых методах поиска в решении задач в пространстве состояний.
Задача:
Провести
относительный анализ эффективности
использования различных
Результат:
Должна быть создана программа, выполняющая всякий слепой поиск
решения. Представлены графики, анализирующие достоинства и недостатки процедур генерации в различных условиях неуправляемого поиска.
Пункт 1
Игра «Перестановка»
Описание задачи.
Суть игры «Перестановка» - получение из некоторой заданной последовательности различных символов другую последовательность из этих же символов.
В качестве символов в игре используются неповторяющиеся цифры. Количество полученных последовательностей равно n!, где n – количество цифр в последовательности. На рисунке показана схема задачи перестановка
Для начала поиска начальное состояние игры должно отличаться от искомого расположением символов.
Цель игры «Перестановка» является поиск и получение из некоторого заданного состояния конечное
Задачей является выбор наилучшего метода поиска для поставленных целей игры. Задача выбора метода поиска предполагает анализ эффективности методов поиска с позиции выбора вида генерации, проверки и планирования.
Схема преобразования
последовательностей в игре показана
на рисунке. Стрелки – это правила,
по которым преобразуются
Преобразование
последовательностей
Таким образом, максимально может быть сформировано количество последовательностей, равное количеству цифр в последовательности минус один. На следующем этапе в полученных последовательностях также выделяются пары, и алгоритм преобразования последовательностей повторяется до условия окончания поиска.
Например, в поиске по лучу всегда раскрывается только одна любая пара текущей последовательности. В поиске в глубину всегда раскрываются все пары одного любого состояния текущего фронта. В параллельном методе поиска всегда раскрывается одна пара из всех последовательностей текущего фронта. В поиске в ширину раскрываются все пары всех последовательностей текущих фронтов.
При проведении игры «Перестановка» следует учитывать следующие условия:
Из условий следует, что
множество последовательностей
в игре «Перестановка» включает непересекаемые
подмножества. Поэтому при задании
начальной и искомой
Определить до начала поиска
принадлежность начальной и искомой
последовательности к одному множеству
поиска в игре «Перестановка» в условиях
1и 4 можно, если использовать следующее
правило: «Если начальная
Следовательно, как и в условии 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}.
Между состояниями пространства поиска существует отношение «род-вид»:
Родовые признаки:
Видовые признаки:
Между состояниями пространства поиска существует отношение «часть-целое», так как имеется подмножество начальных состояний, из которых начинается поиск, подмножество целевых состояний, где поиск заканчивается, и подмножество текущих состояний, которое является промежуточным звеном.
Анализ полученных данных и вывод
Имеется программа, позволяющая реализовать и оценить эффективность применения способов генерации в слепых методах поиска (один из доступных методов: по лучу, параллельный, в глубину, в ширину). Программа рассчитывает и строит графики для математического ожидания и дисперсии для произвольного количество элементов в состояние и для произвольного количества итераций.
Результаты выхода программы для последовательности состояний от 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 |