8126

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

Лекция

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

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

Русский

2013-02-04

241.79 KB

18 чел.

Методы неинформированного поиска. Поиск с итеративным углублением, двунаправленный поиск. Поиск 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


 

А также другие работы, которые могут Вас заинтересовать

44268. Рынок государственных ценных бумаг и особенности его функционирования 778.5 KB
  Рынок государственных ценных бумаг и особенности его функционирования. Теоретические основы функционирования рынка государственных ценных бумаг Сущность государственного рынка ценных бумаг и его участники. Характеристика государственных ценных бумаг Правовые основы функционирования рынка государственных ценных бумаг Анализ рынка государственных ценных бумаг России Оценка выпуска и обращения федеральных займов Анализ развития рынка...
44270. Интернет как модус коллективного бессознательного в информационном обществе: новейшая мифология Интернет-рекламы 3.41 MB
  Бессознательное имеет определенные специфические характеристики, которые отличают его от предсознания и самого сознания. Стремления и мотивы, сходные с инстинктами, существуют в бессознательном отвлеченно и не связано. Бессознательное лишает свое содержимое целого ряда атрибутов, таких, как время и взаимоисключение, поскольку функции, выполняющие эти атрибуты, свойственны сознанию
44271. Лингвистические особенности жаргона северодвинских рок-музыкантов 548 KB
  Особенности морфемной структуры жаргонного слова и способы образования жаргонных единиц. Материалы к словарю жаргона северодвинских рок-музыкантов. В принципе каждый социальный диалект может быть изучен с чисто структурных позиций – описан его словарь выявлены источники его пополнения безусловно что этим фактам может быть дана и социолингвистическая интерпретация но они могут быть освещены и исключительно лексикологически выявлены наиболее частотные морфологические модели особенности фонетики и синтаксиса если таковые...
44272. Система запалювання з новим способом загоряння палива 3.04 MB
  Виконаний вибір головних розмірів і обмотки якоря, розрахунок геометрії магнітопроводу і вибір проводу обмотки якоря, визначення розмірів магнітного кола, розрахунок магнітного кола, розрахунок обмотки збудження, розрахунок колектора і щіток, розрахунок додаткових полюсів, розрахунок втрат
44273. Классификация гражданско-правовых договоров 338 KB
  Общие признаки такие как: правомерность действия действие принципа допустимости и свободы договора совпадение воли и волеизъявления не могут исключить возможность их классификации. Общее для всех сделок учение о делении их на консенсуальные и реальные может применяться и к договорам. Гражданский кодекс РФ содержит в себе правила об отдельных видах обязательств и более распространенных в практике договорах. Это значит что все участники равны при заключении и исполнении договора при судебной защите их интересов.
44274. РОЗВИТОК ТВОРЧОГО МИСЛЕННЯ СТАРШОКЛАСНИКІВ В СИСТЕМІ ІННОВАЦІЙНОГО НАВЧАННЯ ПРИ ВИВЧЕННІ ТЕМИ «УКРАЇНА В УМОВАХ НЕЗАЛЕЖНОСТІ» 405.5 KB
  Час становлення України як самостійної держави ознаменував собою нову віху в історії українського народу визначальними рисами якої є зміцнення реального суверенітету демократизація суспільного життя перехід від адміністративно-директивної...
44275. Выбор источников теплоснабжения, вида теплоносителя и его параметров 739.5 KB
  Определяем расчетную площадь га по формуле 2 где S – площадь здания га. Определяем общее число жителей чел по формуле...
44276. Численное исследование процесса филаментации мощных фемтосекундных лазерных импульсов в турбулентной атмосфере на протяжённых трассах 474 KB
  В воздухе длина филаментов создаваемых импульсами Ti:Spphire лазера достигает сотен метров; их диаметр не превышает 100 мкм интенсивность светового поля в филаменте составляет величину порядка 1013 Вт см2 частотный спектр может перекрывать видимый и простираться в ближний инфракрасный диапазон длин волн При распространении мощного фемтосекундного импульса в условиях турбулентной атмосферы случайные флуктуации показателя преломления инициируют мелкомасштабную самофокусировку При высокой плотности энергии лазерного импульса...