TIPS_1_laba / (готовый

1. Представление пространства поиска.

а) Каким образом организовано пространство состояний?

б) Существуют ли в пространстве состояний не пересекаемые подмножества состояний, каким образом их можно определить?

в) Какие существуют отношения между состояниями пространства поиска?

а) Организацию пространства состояний удобно представить в виде ориентированного графа (в дальнейшем  орграфа), где множество вершин орграфа сопоставимо с состояниями, а множество дуг графа сопоставимы с операторами преобразующими состояния множества.

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

Рассмотрим наиболее весомые условия соотношений множеств Yⁱⁿ{y_j} (входящих дуг) и Y^out{y_j} (выходящих дуг), устанавливающие организацию орграфа G: Если для всякой вершины x_iX орграфа G, выполняются условия: Yⁱⁿ{y_j}=n-1 и Y^out{y_j}=n-1, то орграф представляет собой замкнутую структуру.

Свойства некоторых вершин так же влияют на организацию орграфа:

1. Если для некоторой вершины x_iX орграфа G, выполняются условия: Yⁱⁿ{y_j}1 и Y^out{y_j}=, то такая вершина x_i является «терминальной». Терминальная вершина указывает на то, что для соответствующего состояния s_i, множество применимых к нему операторов: F=. Такое состояние не может быть далее преобразовано.

2. Если для некоторой вершины x_iX орграфа G, выполняются условия: Yⁱⁿ{y_j}= и Y^out{y_j}1, то такая вершина x_i является «корневой». Корневая вершина не может быть порождена ни одной вершиной орграфа G. Так, если корень дерева не представляет собой кольцо, то в дереве есть только одна корневая вершина.

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

б) В пространстве состояний существуют не пересекаемые подмножества.

Родовые признаки (одинаковое количество символов, цифры в последовательности не повторяются) выделяют пространство состояний, следовательно, родовые признаки не пересекаемых подмножеств не равны пустому множеству, т.е. К^R≠Ø

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

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

1) Если количество знаков в состоянии 2m и применяется прямое правило, то мощность пространства поиска будет равным n!/2.

2) Если количество знаков в состоянии 2m-1 и применяется прямое правило, то мощность пространства поиска будет равным n!.

3) Если количество знаков в состоянии 2m и применяется обратное правило, то мощность пространства поиска будет равным n!.

4) Если количество знаков в состоянии 2m-1 и применяется обратное правило, то мощность пространства поиска будет равным n!/2.

Эти условия необходимы для того, чтобы определить существуют ли в пространстве состояний не пересекаемые подмножества состояний. Пример: если следовать условиям 2 и 3, то таких состояний не появится т.к из родительской вершины, состоящей из n символов можно образовать n! возможных комбинаций, а если следовать условям 1 и 4, то можно образовать только половину возможных состояний и в пространстве состояний окажутся непересекаемые вершны. Можно сделать вывод, что обязательним условием существованя искомой вершины является проверка количества символов в состоянии на четность/нечетность.

в) Отношения между состояниями пространства.

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

Каждое состояние пространства состояний получено прямым или обратным преобразованием.

Глубина пространства поиска меньше либо равна n-1, где n-число цифр в состоянии.

Элементы пространства поиска различны.

3. Условия задачи:

а) Описание начального условия решения задачи.

б) Описание требуемого результата решения задачи.

а) Характеристика способов генерации.

Процедура генерации является отличительным (видовым) признаком класса «слепых» методов поиска. В отношении процедуры генерации различают слепые методы поиска: по лучу, в глубину и в ширину.

Характеристика метода поиска по лучу:

1) Для очередного s_i формируется множество применимых операторов F_i.

2) Если F_i, то выбирается одно f_jF_i, иначе s_i является терминальным состоянием. Если имеются терминальные состояния, то следует ввести в алгоритм механизма возврата. Обычно, следует вернуться назад, выбрать иное f_jF_i-1 для s_i-1 не порождающие терминальное s_i (более подробно об обходе терминальных состояний будет сказано ниже).

3) Состояние s_i раскрывается s_i  f_j = s_i+1 (далее результат генерации или раскрытие состояния будем именовать «фронтом»).

4) Если выполняется условие: s_i+1 s_j^tS^t, то задача решена (выполняется одно из условий решения первой задачи), иначе переход к п.1 применительно для очередного состояния s_i+1.

Алгоритмы поиска в методе в глубину:

1) Для одной s_iS_i формируется множество применимых операторов F_i.

2) Если F_i=, то s_i является терминальным состоянием, (при наличии терминальных состояний, используют иную s_jS_i или поступают так же, как в методе поиска по лучу).

3) Состояние s_i раскрывается s_i  F_i=S_i+1.

4) Если выполняется условие:  s_i+1 S_i+1,  s_j^tS^t, то задача решена (выполняется одно из условий решения первой задачи), иначе переход к п.1., но применительно для очередного фронта состояний S_i+1.

В методе в ширину реализуется следующий алгоритм поиска:

1) Для всех s_iS_i формируется множество применимых операторов F_i.

2) Если для всех s_iS_i, F_i=, то решения не существует, иначе п.3.

3) S_i раскрывается: S_i  F_i = S_i+1.

4) Если выполняется условие:  s_i S_i+1,  s_j^tS^t, то задача решена (выполняется одно из условий решения первой задачи), иначе переход к п.1. применительно для очередного фронта состояний S_i+1.

Для осуществления поиска необходим комплекс действий. Комплекс действий определяют процедуры генерации, проверки, планирования.

Для осуществления поиска: 1. S^o = {S1,S2…Sn}

Задать начальное состояние с которого начинается поиск.

2. S^t = {S1,S2…Sm}

Множество целевых состояний. m - мощность множества.

Пересечение множеств S^o и S^t не должно быть пустым.

3. F = {f1,f2…fk}

Множество операторов.

4. S^c ={S1,S2…Si}

Множество текущих состояний. S^c . (в некоторых случаях выполнение данного условия необязательно).

б) Используя «слепые» методы поиска возможно получить следующие результаты решения задачи:

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

2. Поиск целевого состояния (при заданном начальном состоянии) любым методом поиска.

4) Выбор методов генерации.

Выбор той или иной процедуры генерации зависит:

1. От условия решения задачи: найти все s_iS^t, найти одну s_iS^t, найти заданное количество s_iS^t, найти одну или несколько указанных s_iS^t;

2. От отношения Sи подмножества S^t, от отношения Sи подмножества S^o, от отношения подмножества S^oи подмножества S^t.

При условии, что поиск осуществляется на дереве оригинальных состояний глубиной n, и количество дочерних состояний m у всякого родителя одинаково, то вероятность нахождения одного состояния будет иметь следующий вид:

1) Для поиска по лучу: Р= 1/ m_i ⁿ– b.

2) Для поиска в глубину: Р= 1/ m_i ⁿ– b m.

3) Для поиска в ширину: Р= 1/ m_i ^n-b.

где b-число итераций.

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

Однако с увеличением числа элементов в последовательности значение вероятностей выравнивается.