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

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

«Анализ процедур генерации»

Выполнили: ст. гр. КИ11-14Б

Крестьянинов Д. А.

ст. гр. КИ11-13Б

Овечкина О. О.

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

Красноярск 2010

Тема: Анализ работы «слепых» методов поиска при решении задач в пространстве состояний.

Цель: Дать представление о возможности использования «слепых» методов поиска в решении задач.

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

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

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

1. Прямой метод.

Для начала нужно взять ряд чисел (букв или других предметов), которые при перестановке образуют новый ряд.

Например: 9“ ù õ 9ù õ “

Шаг 1.

Для осуществления перестановки берем наш ряд 9“ ù õ и делим его на пары. Чтобы определить количество пар берем общее количество предметов и вычитаем из него единицу (l=n-1), в нашем случае 4-1=3, то есть делим ряд 9“ ù õ на три пары:

1 пара - 9“

2 пара - “ ù

3 пара - ù õ

Шаг 2.

Берем 1ую пару и делим ее 2 части: первая часть - 9 и вторая часть - “, проделываем то же самое и с остальными парами.

Шаг 3.

Берем то, что осталось от 1 ряда (ù õ) и в его начало ставим 1 часть пары, и в конец ряда ставим 2 часть пары и получаем новый ряд 9ù õ “, то же самое проделываем с остальными парами и получаем в результате три новых ряда.

Шаг 4.

Любой ряд можно перестанавливать не до бесконечности, имеется определенное количество рядов (комбинаций), которые могут быть образованы в результате перестановок, оно рассчитывается по формуле: n=n! /2-12/2=6

2. Обратный метод.

Для начала нужно взять ряд чисел (букв или других предметов), которые при перестановке образуют новый ряд.

Например: 9“ ù õ “ ù õ 9

Шаг 1.

Для осуществления перестановки берем наш ряд 9“ ù õ и делим его на пары. Чтобы определить количество пар берем общее количество предметов и вычитаем из него единицу (l=n-1), в нашем случае 4-1=3, то есть делим ряд 9“ ù õ на три пары:

1 пара - 9“

2 пара - “ ù

3 пара - ù õ

Шаг 2.

Берем 1ую пару и делим ее 2 части: первая часть - 9 и вторая часть - “, проделываем то же самое и с остальными парами.

Шаг 3.

Берем то, что осталось от 1 ряда (ù õ) и в его начало ставим 2 часть пары, и в конец ряда ставим 1 часть пары и получаем новый ряд “ ù õ 9, то же самое проделываем с остальными парами и получаем в результате три новых ряда.

Шаг 4.

Любой ряд можно перестанавливать не до бесконечности, имеется определенное количество рядов (комбинаций), которые могут быть образованы в результате перестановок, оно рассчитывается по формуле: n=n! =4! =12

Целью задачи является получение из некоторой заданной последовательности знаков, требуемую последовательность этих же знаков.

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

Задачей является поиск заданного состояния в образованном графе.

Рассмотрим пример преобразований на наборе цифр от 1 до 4.

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

1) В состоянии выделяются пары чисел (i, i+ 1). Например, для состояния 1234, парами являются (1, 2), (2, 3) и (3, 4), (их количество n –1 = 3);

2) Первое число пары i переносится в начало состояния, а второе i+ 1 в конец состояния (см. рисунок 1).

Рис.1.

При «обратном» преобразовании первое число пары i переносится в конец состояния, а второе i+ 1 в начало состояния (см. рисунок 2).

Рис.2.

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

Рассмотрим пример преобразований так же на наборе цифр от 1 до 4.

Полная схема преобразования состояний прямым преобразованием представлена на рисунке 3.

Рис.3.

Полная схема преобразования состояний обратным преобразованием представлена на рисунке 4.

Рис. 4.

Дополнительно организацию состояний можно отобразить с помощь матриц смежности и инцидентности. Матрица смежности позволяет представить бинарные отношения между вершинами орграфа. Отношение смежности обозначается «1», если между вершинами x_i и x_{i+ 1}существует дуга y_j, иначе «0». Матрица инцидентности позволяет представить отношения между количеством входящих и выходящих дуг некоторой вершины x_iÎ G. Отношение обозначается «1», если дуга y_j выходит из вершины x_i, иначе «0» (если дуга y_j входит в вершину x_i).

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

В таблице смежности как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот). Если связь вежду вершинами имеется то ставим «1», иначе «0». Заметим, что в главной диагонали получившейся матрицы стоят «0». Также, содержание i-того столбца соответствует содержанию i-той строки, так как и там, и там записаны вершины графа(например 1-ый столбец: 0 1 1 1 1 0 0 0 0 1 0 0 и первая строка: 0 1 1 1 1 0 0 0 0 1 0 0). Еще можно увидеть, что каждая строка(столбец) имеет пять «1», хотя из матрицы смежности следует, что каждая вершина имеет 6 дуг, это объясняется тем, что при прямом преобразовании каждая вершина имеет одну двойную связь(т.е. каждая вершина имеет парную себе вершину между которыми возникает связь «вход-выход» и «выход-вход»)

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

Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (дуга и вершина). Столбцы матрицы соответствуют вершинам, строки — ребрам. Если y_j выходит из вершины x_i то «1», иначе «0». Заметим, что в строке каждого y_j имеется одна «1» и один «0», это значит что каждая дуга из одной вершины выходит и в другую входит, следовательно в графе нет корневых вершин(которые имеют только выходы). А также, каждая вершина имеет ранвое количество входов и выходов.

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

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

Условием окончания преобразования состояний будет являться множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, должно соответствовать множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi. При использовании в состояниях 4х символов, количество входящих в состояние опереторов должно быть равно количеству выходящих из него операторов и равно n-1, т.е 3. После чего построение графа заканчивается.