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-число итераций.

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

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