8126

Методы неинформированного поиска. Поиск с итеративным углублением, двунаправленный поиск. Поиск c удовлетворением ограничений. Cложность методов поиска

Лекция

Информатика, кибернетика и программирование

Методы не информированного поиска. Поиск с итеративным углублением, двунаправленный поиск. Поискc удовлетворением ограничений. Cложность методов поиска. Итеративно углубляющийся поиск. В ограниченном по глубине пои...

Русский

2013-02-04

241.79 KB

17 чел.

Методы неинформированного поиска. Поиск с итеративным углублением, двунаправленный поиск. Поиск c удовлетворением ограничений. Cложность методов поиска.

Итеративно углубляющийся поиск.

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

function Iterative-Deepening-Search(problem) returns solution or failure

 for depth  0 todo

  if Depth-Limited-Search(problem, depth)

  successed then return solution

 end

return failure

L=0:

L=1:

L=2:

L=3:

Итеративно углубляющийся поиск - это поиск в глубину и поиск в ширину. Он оптимален и подобен поиску в ширину, но имеет при этом умеренные требования по памяти, как и поиск в глубину. Порядок раскрытия состояний аналогичен порядку в ширину, за исключением того, что некоторые состояния расширяются много раз. Итеративно углубляющийся поиск на первый взгляд может показаться расточительным, так как состояния, раскрываются многократно, однако эта избыточность в действительности достаточно мала, поскольку в дереве поиска почти все вершины находятся на нижнем ярусе:

1 + b + b2 + … + bd-1 + bd

Число раскрытий вершин в ограничении по глубине d соответствует данной формуле. Пример, если b=10, d=5, тогда 1+10++105=111111.

В итеративно углубляющемся поиске вершины на нижнем уровне раскрываются один раз, на предпоследнем уровне дважды и так далее, следовательно, корень дерева раскрывается d+1 раз, поэтому общее число раскрытий в данном поиске равно:

(d+1)*1 + d*b + (d-1)*b2 ++3*bd-2 + 2*bd-1 + bd

Общее число раскрытий будет равно 123456. Следовательно, данный поиск раскрывает лишь на 11% больше вершин, чем поиск в ширину. При этом, чем больше коэффициент  ветвления, тем меньше накладываются расходы от повторного раскрытия состояний. При коэффициенте ветвления равном 2 итеративно углубляющийся поиск требует вдвое больше раскрытий, чем полный поиск в ширину. Сложность временная О(bd). Сложность емкостная О(b*d). В общем случае итеративно углубляющийся поиск является эффективным методом поиска при большом пространстве поиска и неизвестной глубине решения.

Двунаправленный поиск

Предполагает встречное движение от исходного состояния и целевого состояния.

Пусть bкоэффициент ветвления. Пусть также решение находится на глубине d, тогда для нахождения решения потребуется: О(2*bd/2)=O(bd/2)

Если b=10, а d=6, тогда поиск в ширину требует 1111111 шагов. Двунаправленный поиск с каждой стороны пройдет на глубину 3, и при этом будет сгенерировано 2222 вершин.

Для реализации двунаправленного поиска необходимо:

  1.  Иметь функцию, определяющую предшественников для каждого состояния.
  2.  Способ эффективной проверкине находится ли новая вершина в дереве другой половины поиска.
  3.  Выбрать вид поиска в каждой половине двунаправленного поиска, (лучше –поиск в ширину).

Проблема зацикливания при поиске

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

Существует три способа работы с повторяющимися состояниями:

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

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

3. Блокировка генерации состояний, которые уже были сгенерированы где-либо ранее в дереве поиска. Сложность О(bd), dглубина.

Сравнение методов поиска.

Критерий

ПВШ

ПКС

ПВГ

ОГП

ИУП

ДНП

Временная сложность

bd

bd

bm

bL

bd

bd/2

Емкостная сложность

bd

bd

b*m

b*L

b*d

bd/2

Оптимальность

+

+

-

-

+

+

Полнота

+

+

-

+, если L>=d

+

+

где bкоэффициент ветвления

      dглубина

      Lограничение глубины.

Поиск с удовлетворением ограничений

(CSPConstrain Satisfaction Problem).

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

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

1. Унарные ограничения.

. Бинарные ограничения относятся к парам переменных. Возможны и большие ограничения, но в практике стараются все свести на бинарные ограничения.

3. Ограничения могут быть абсолютными или предпочтительными. Для каждой переменной Vi в CSP задается область определений Di, которая может быть непрерывной или дискретной.

Унарные ограничения задают некоторые подмножества области определения. Бинарные ограничения задают подмножество декартова произведения  областей определения.

В дискретной CSP с конечной областью определения ограничения могут быть заданы путем нумерации допустимых комбинаций значений. В задаче о восьми ферзях в качестве переменной Vi можно рассматривать номер горизонтали, занимаемый ферзем на i-ой вертикали. Ограничения {(1,1), (1,2), (2,1), (2,2), (2,3)…}, где значения в скобкахномер клетки по вертикали и горизонтали. Допустимые состояния {(1,3), (1,4), (1,5)…}. Ограничения на отсутствие атаки исключает 22 состояния из 64. Используя идею нумерации, любая дискретная CSP может быть сведена к бинарной CSP. В непрерывных CSP используется более сложная алгебра для задания ограничений. Для решения дискретной CSP можно использовать поисковые алгоритмы общего назначения. При этом исходным состоянием является состояние, в котором всем переменным не назначены значения.

Операторы назначают значение переменной из множества возможных значений. Проверка целей проверяет - назначены ли значения всех переменных и все ли ограничения удовлетворены. Таким образом максимальная глубина дерева поиска равна числу переменных, но с другой стороны все решения лежат на глубине n. Таким образом можно использовать в CSP поиск в глубину, так как нет риска уйти слишком глубоко и нет необходимости ограничивать глубину поиска. В простейшем случае в каждой вершине дерева  поиска может присваиваться значение любой переменной из тех, которым еще не присвоено значение.

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

5