8125

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

Лекция

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

Методы не информированного поиска. Поиск в ширину,в глубину, однородной стоимости, ограниченный по глубине поиск. Основная проблема в области поиска - нахождение хорошей стратегии поиска для заданной задачи. Страт...

Русский

2013-02-04

142.53 KB

33 чел.

2

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

Основная проблема в области поисканахождение хорошей стратегии поиска для заданной задачи.

Стратегии принято оценивать с помощью 4 критериев:

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

Стратегии поиска в пространства состояний принято делить на две группы:

  1.  Стратегии неинформированного (слепого) поиска.
  2.  Стратегии информированного поиска (эвристические cтратегии).

Неинформированный поискэто поиск в отсутствии какой-либо информации, позволяющей отдавать предпочтение одним направлениям поиска перед другими.

Информированный поиск имеет место, когда есть некоторая информация, которая может использоваться при выборе того или иного направления поиска.

Стратегии неинформированного поиска

Поиск (сначала) в ширину.

Сначала раскрывается вершинакорень в дереве поиска. Затем все вершинынепосредственные потомки корня и т.д. Вершины глубины d раскрываются раньше, чем вершины глубины (d+1). Пока есть хотя бы одна вершина глубины dнельзя раскрывать вершину на глубине d+1. Поиск в ширину может быть реализован алгоритмом General-Search, в котором функция построения очереди помещает вновь сгенерированные вершины в конец очереди.

function Breadth-First-Search(Problem) returns solution or failure

return General-Search(Problem, En-queue-At-End)

Cтратегия помещает вновь сгенерированные вершины в конец очереди.

Поиск в ширину:

гарантирует нахождение решения, если оно существует;

–первым всегда находит решение минимальной глубины.

Однако решение минимальной глубины не всегда имеет минимальную стоимость.

Недостаток поиска в ширинубольшая сложность.

Пусть пространство поиска, в котором каждое состояние может быть раскрыто в b новых состояний. Тогда корень дерева генерирует b потомков, далее b2, затем b3 и так далее.

Следовательно, если решение лежит на глубине d, для нахождения решения потребуется раскрыть 1 + b + bb + bd вершин.

Порядок сложности поискаO(bd).

Оценим временную и емкостную сложность поиска при коэффициенте ветвления b=10 и глубине равной d. Пусть за одну секунду проверяется 1000 вершин (раскрываются и проверяются на достижение цели).

d

Вершины

Время

Память

0

мс

байт

2

,1 с

кбайт

4

с

Мбайт

6

6

18 м

Мбайт

8

8

ч

Гбайт

10

10

дн

Тбайт

12

12

лет

Тбайт

14

14

лет

Тбайт

Поиск по критерию стоимости.

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

Поиск по критерию стоимостимодифицированная стратегия поиска в ширину, при которой всегда раскрывается вершина с минимальной стоимостью пути. Пусть 

g(n) –функция стоимости пути в  вершину n.

Поиск в ширину является частным случаем поиска по критерию стоимости, когда стоимость равна глубине.

g(n) = depth(n).

Пример: Рассмотрим пути поиска в графе рис. 4.1.

Рис. 4.1.

Найти путь минимальной стоимости из S в G.

S

C

B

A

g(n)=5

g(n)=1

3


 

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

41138. Топологические элементы схемы: ветви, узлы, контуры 435 KB
  Электрическая схема представляет собой графическое изображение электрической цепи. Она показывает как осуществляется соединение элементов рассматриваемой электрической цепи. Электрическими элементами схемы служат активные и пассивные элементы цепи. Ветвь участок схемы расположенный между двумя узлами и образованный одним или несколькими последовательно соединенными электрическими элементами цепи рис.
41139. Основные понятия теории вакуума 574 KB
  Первый принцип реализован в газоперемещающих насосах. Для удаления порции газа необходимо изолировать в рабочей камере насоса определенный объем газа переместить его от входного патрубка насоса к выходному сжать в процессе перемещения до давления большего чем давление в выходном сечении насоса и вытолкнуть газ за пределы насоса. Вакуумные насосы которые откачивают газ отдельными порциями в результате периодического изменения объема и положения рабочей камеры называются объемными вакуумными насосами. Объемными вакуумными насосами...
41140. Турбомолекулярные насосы 332 KB
  Поэтому вал таких насосов должен вращаться со скоростью 10 00060 000 об мин в зависимости от диаметра насоса. По сравнению со многими другими сверхвысоковакуумными насосами турбомолекулярным насосам присущ ряд преимуществ: постоянная готовность к работе быстрый 1015 мин запуск нечувствительность к резкому повышению давления вплоть до атмосферного широкий диапазон рабочих давлений 107 101 Па примерно одинаковая быстрота действия по большинству газов чрезвычайно высокая степень сжатия 1015 для газов с большой молекулярной...
41141. Объекты логистического управления 85 KB
  Материальные потоки их характеристика и классификация. Финансовые информационные потоки и потоки услуг. Материальные потоки их характеристика и классификация. Материальные потоки образуются в результате транспортировки складирования и выполнения других материальных операций с сырьем полуфабрикатами и готовыми изделиями начиная от первичного источника сырья вплоть до конечного потребителя.
41142. Программные средства шифрования 298.5 KB
  Все звучит довольно красиво, и, как правило, оправдывается на деле при использовании шифрования. Шифрование, несомненно, является важнейшим средством обеспечения безопасности. Механизмы шифрования помогают защитить конфиденциальность и целостность информации. Механизмы шифрования помогают идентифицировать источник информации.
41143. Первый закон термодинамики 154.5 KB
  Первый закон термодинамики. До формулировки Первого начала термодинамики в 1840х годах учеными Джоулем 1840 Майером 1842 и Гельмгольцем 1847 в науке наряду с материалистическим пониманием закона сохранения и превращения энергии одной из форм которого и является Первое начало термодинамики существовала теория теплорода. Формулировка Первого начала термодинамики основана на экспериментальных исследованиях. Первый закон термодинамики вообще говоря является постулатом.
41144. ПРИБОРЫ ДЛЯ ИЗМЕРЕНИЯ ДАВЛЕНИЯ 845.5 KB
  Неотъемлемой частью любой вакуумной системы является аппаратура для измерения давления разрежённого газа. Область давления используемая в современной вакуумной технике 105 1012 Па. В практике измерения давления разрежённых газов применяются различные типы преобразователей отличающиеся по принципу действия и классу точности. При малых давлениях непосредственное измерение силы давления невозможно из-за её малости.
41145. Пошук інформації в системі 103.5 KB
  Перегляд списку та маніполювання зі списками знайдених документів Ведуть записи 3 хв. Підведення підсумків уроку Що таке пошукові реквізити Які пошукові реквізити в системі Що називається динамічним навігатором Що таке перелік документів Які операції можна проводити з переліками Відповіді студентів 2 хв.Перегляд списку та маніпулювання зі списками знайдених документів 1. Перелік кнопок Додаткової Панелі Інструментів: Переводить Робочий Стіл системи в двовіконний режим роботи Задає слова для пошуку в назві Розташовує документи...
41146. Применение теории пленочной конденсации в инженерных расчетах 225 KB
  Он представляет собой отношение теплоты конденсации к теплоте переохлаждения конденсатной пленки в диапазоне изменения температур от температуры насыщения до температуры стенки. В этом случае возникает значительный конвективный перенос тепла вдоль пленки и к тому же необходимо учитывать силы инерции. Кроме того при достаточно большой протяженности поверхности конденсации на ней возникает режим течения пленки отличный от чисто ламинарного режима.е возникают так называемые волновые режимы течения пленки что приводит к существенному...