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

Автор: Пользователь скрыл имя, 05 Ноября 2012 в 14:26, лабораторная работа

Краткое описание

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

Файлы: 1 файл

Лабораторная работа 1 ТИПИС.docx

— 433.80 Кб (Скачать)

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

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

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

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

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

 

 

Специальность: «Информационные системы и технологии (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

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