8126

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

Лекция

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

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

Русский

2013-02-04

241.79 KB

19 чел.

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


 

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

15074. М.ӘУЕЗОВ ҚАЗАҚ ӘДЕБИЕТІНІҢ ТАРИХЫ ТУРАЛЫ 66 KB
  М.ӘУЕЗОВ ҚАЗАҚ ӘДЕБИЕТІНІҢ ТАРИХЫ ТУРАЛЫ ЖУМАБЕКОВА АЙКЕН АЙТМАҒАМБЕТҚЫЗЫ. Павлодар қаласы Қ.Бекқожин атындағы №12 жалпы орта білім беру мектебі. Мұхтар Әуезовтің ғалымдық жолы көпке белгілі. Ол жасынанақ жазушылық қызметпен бірге әдебиет туралы ойпікірл...
15075. М.Әуезов әңгімелеріндегі тартыс 83 KB
  Мұратбекқызы Алтынай Л.Н.Гумилев атындағы Еуразия ұлттық университеті қазақ әдебиеті кафедрасының магистранты МҰХТАР ӘУЕЗОВ ӘҢГІМЕЛЕРІНДЕГІ ТАРТЫС ХХ ғасырдың алғашқы ширегіндегі рухани серпіліс қазақ сөз ө
15076. М.Әуезовтың Хан Кене трагедиясындағы Алашшылдық идеяның көріністері 69 KB
  Лилия Серғазы Л.Н.Гумилев атындағы Еуразия ұлттық университетінің доценті филология ғылымдарының кандидаты М.ӘУЕЗОВТІҢ ХАН КЕНЕ ТРАГЕДИЯСЫНДАҒЫ АЛАШШЫЛ ИДЕЯ Қазіргі кезде М.Әуезовтің бүкіл шығармашылық жолының өн бойында алашшыл көзқарастың созылып
15077. М.Шаханов поэзиясындағы рухани-адамгершілік құндылықтар 65.5 KB
  ӘОЖ 882:929 МҰХТАР ШАХАНОВ ПОЭЗИЯСЫНДАҒЫ РУХАНИАДАМГЕРШІЛІК ҚҰНДЫЛЫҚТАР Ш.А. Өсерова Н.Ә.Асанбекова Жамбыл атындағы №5 орта мектеп Тараз қ. Қазақ халқы аса күрделі проблемаға маңдай тіреді. Өз ұлтымыздың ішінен орыс және батыс мәдениетімен жете сусындаса да а...
15078. Мағжан Жұмабаевтың Батыр Баян поэмасы 56 KB
  МАҒЖАН ЖҰМАБАЕВТЫҢ БАТЫР БАЯН ПОЭМАСЫ М. Орынбаев А. Қалшабеков Тараз мемлекеттік педагогикалық институты Тараз қ. XVIII ғасыр қазақ халқының қиынқыстау заманы болды. Жоңғар қалмақтың жанжақтан қыспағы елді қатты күйзеліске ұш...
15079. Мағжан Жұмабаевтың кестелі өлең өрнегі 73 KB
  УДК 894.342 МАҒЖАН ЖҰМАБАЕВТЫҢ КЕСТЕЛІ ӨЛЕҢ ӨРНЕГІ А.М.Мұратбек Ж.Қ. Боранбаева Л.Н. Гумилев атындағы Еуразия ұлттық университеті Астана Профессор Шериаздан Елеукеновтің: Әдебиет идеясы өмірден туындайды. Идеяны жеткізетін тіл. Ол суреткердің дүниетанымын
15080. Мағжан Жұмабаевтың өлеңдері 62 KB
  Мағжанның өлеңдері Мағжан Жұмабаевтың алғашқы өлеңдері ағартушылық сарында жазылды. Ол түсінікті еді. Мағжан өмір сүрген уақыт қаншалықты күрделі саяси қоғамдық тақырыптарды алға тартқанымен оның алдындағы Шоқан Ыбырай Абайлар бастап кеткен ағартушылық ойпиғыл ...
15081. Мағжан Жұмабаевтың Түркістан өлеңінің көркемдік ерекшеліктері 72 KB
  ӘОЖ 894.342 МАҒЖАН ЖҰМАБАЕВТЫҢ ТҮРКІСТАН ӨЛЕҢІНДЕГІ ТІЛДІК ЕРЕКШЕЛІКТЕР Ф. Уәлиева Ж.Қ. Боранбаева Л.Н. Гумилев атындағы Еуразия ұлттық университеті Астана Мағжанға дейінгі шамамен екі ғасырлық кезең патшалық Ресейдің Түркістан аймағын басып алу мақсатын...
15082. Махамбет шығармаларының жанрлық ерекшелігі 62.5 KB
  Махамбет өлеңдерінің жанрлық ерекшеліктері Махамбет өлеңдері өзінің жанр жағынан да зерттеушілердің айрықша көңілін аударуға тиіс. Оның кейбір өлеңдерін лироэпикалық түрге жатқызуға болады. Ол өлеңдерінде ақын өмір құбылыстарын Исатай бастаған шаруа...