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


 

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

23366. Вивчення основ програмування на мові Python 562.41 KB
  Тексти програм на мові Python. Мета роботи Ознайомлення з основними типами даних в Python. Вивчення основ програмування на мові Python.
23367. Исследование термоэлектрического термометра 436.5 KB
  Произвести измерения термоЭДС на клеммах подключения термопары 1819 для значений указанных преподавателем. Рассчитать основную абсолютную погрешность прибора по формуле: где Eиtt0 – измеренное значение термоЭДС; Eдtt0 – действительное значение термоЭДС определяемое по градуировочной таблице с учетом введения поправки на температуру свободных концов. Рассчитать основную приведенную погрешность термопары по формуле: где Eвt0C и Eнt0C – значения термоЭДС соответствующие верхнему и нижнему пределам измерения температуры...
23368. Исследование уровнемера У1500 180 KB
  Порядок выполнения работы Ознакомиться с описанием уровнемера У1500. Подключить вилку разъема датчика уровнемера к соответствующему гнезду на задней панели измерителя. Установить поплавок уровнемера поочередно в пяти точках по мерной линейке по заданию преподавателя сначала по возрастанию – прямой ход а затем в тех же точках по убыванию – обратный ход и занести соответствующие показания прибора в таблицу см.
23369. Исследование метрологических характеристик электромеханических приборов 646 KB
  Построить графики зависимости абсолютной погрешности прибора от его показаний при его работе на постоянном токе. Определить максимальное значение приведенной основной погрешности прибора для постоянного тока. На основе анализа полученных данных сделать вывод о соответствии основной погрешности и вариации показаниям определяемым классом точности испытуемого прибора.
23370. Исследование преобразователя давления Метран 100 444 KB
  Провести поверку преобразователя давления Метран100 с помощью грузопоршневого и образцового пружинного манометров. Построить градуировочную характеристику зависимости унифицированного токового сигнала Iвых от входного давления Рд. Описание лабораторной установки Лабораторная установка представляет собой поверочный грузопоршневой манометр МП60 пресс на котором установлены образцовый манометр с пределом измерения 25 МПа и преобразователь давления Метран 100 с цифровым индикатором жидкокристаллическим дисплеем для представления...
23371. Создание мультимедийных приложений 115 KB
  В настоящей лабораторной работе будет показано как создать простейшие приложения для прослушивания звуковых файлов и просмотра анимации с помощью компонента MediaPlayer. Компонент MediaPlayer Компонент MediaPlayer расположен на странице System Палитры Компонентов. Общий вид компонента MediaPlayer представлен на рис. Вид MediaPlayer на форме Ниже в таблице 16.
23372. Использование компонента Timer. Организация простейшей мультипликации 68.5 KB
  В данной работе приводятся примеры работы компонента Timer обеспечивающего доступ к системному таймеру компьютера и его использование совместно с компонентом Image для создания простейшей мультипликации. Компонент Timer. Прием сообщений от таймера компьютера в приложении Delphi обеспечивает специальный компонент Timer со страницы System Палитры Компонентов.
23373. Конструирование меню и работа со стандартными окнами диалога Windows 322.4 KB
  Контекстное меню Рабочая область редактора Панель инструментов Меню Рис. Создание главного меню приложения Для создания главного меню приложения необходимо: поместить на форму компонент MainMenu Главное меню со станицы Standard Палиры Компонентов. Двойным щелчком по данному невизуальному компоненту вызвать редактор меню: Перемещаясь по обозначенным пунктам меню задаем в свойстве Caption каждого пункта.
23374. Отображение графической информации в Delphi 112.5 KB
  Объект Canvas Delphi имеет в своём распоряжении специальный объект который оформлен в виде свойства Canvas. Слово Canvas можно перевести на русский язык как холст для рисования или канва. Если у объекта есть свойство Canvas на его поверхности можно рисовать. Кроме компонентов перечисленных выше свойством Canvas обладают также: Image SpLitter ControlBox а так же объект TPrinter который благодаря этому свойству позволяет распечатывать графические изображения на принтере.