8125

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

Лекция

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

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

Русский

2013-02-04

142.53 KB

31 чел.

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


 

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

50044. ИЗУЧЕНИЕ СВОБОДНЫХ КОЛЕБАНИЙ ФИЗИЧЕСКОГО МАЯТНИКА 205 KB
  Настенный кронштейн с подушками для опорных призм физического маятника. такой математический маятник период колебаний которого равен периоду колебаний физического маятника. Длина такого математического маятника называется приведенной длиной физического маятника.
50045. Статистический характер прочности 379.5 KB
  Классификация нагрузок Нагрузки и воздействия представляют собой наиболее неопределенные величины обладающие большим статистическим разбросом. В части математического описания нагрузки делятся на: нагрузки представляющие собой случайные величины; нагрузки представляющие собой случайные функции времени; нагрузки изменяющиеся...
50047. Визначення показника заломлення та концентрації водних розчинів за допомогою рефрактометра 316 KB
  Мета роботи Ознайомитися з будовою і принципом дії рефрактометра типу РПЛ2 оволодіти методикою експериментального визначення показників заломлення та концентрацій водних розчинів цукру визначення граничних кутів які відповідають початку повного внутрішнього відбивання від межі розділу скло досліджуваний розчин Для виконання лабораторної роботи студенту попередньо необхідно: знати закони геометричної...
50048. Пересування як вид стройових вправ 44 KB
  Основи термiнологiï: випади махи ногами тулубом руками. Випади. Випад це рух або положення з виставленням i згинанням опорноï ноги. Випад лівою правою Положення коли опорна лiва права нога виставлена i зігнута вперед iнша нога стоїть позаду випрямлена в колiнi тулуб на однiй вертикалi з тазом Випад влiво вправо Положення коли опорна лiва права нога виставлена влiво впрао i зiгнута в колiнi тулуб вертикально Нахилений випад влiво вправо Положення коли виконується випад...
50050. Определение индуктивности соленоида и коэффициента взаимной индуктивности с помощью исследования вынужденных колебаний в RL – цепи 293 KB
  Определение индуктивности соленоида и коэффициента взаимной индуктивности с помощью исследования вынужденных колебаний в RL-цепи. Цепь состоит из генератора резистора обладающего активным электрическим сопротивлением цепи R и катушки индуктивности обладающей реактивным индуктивным сопротивлением 1 w = 2pn циклическая частота колебаний. Фаза колебаний напряжения на индуктивности опережает фазу колебаний напряжения...
50051. Изучение петли гистерезиса и измерение параметров ферромагнетика 168.5 KB
  Они способны сохранять намагниченность в отсутствие магнитного поля. Особенностью ферромагнетиков является сложная нелинейная зависимость между намагниченностью J и напряженностью магнитного поля H равносильно между вектором магнитной индукции В и напряженностью магнитного поля H. В действительности она является функцией напряженности поля Н и определяется как . Оно проявляется в том что при изменении намагничивающего поля Н магнитная индукция В в ферромагнетике отстает от внешнего магнитного поля Н.
50052. ЯВЛЕНИЕ САМОИНДУКЦИИ 99 KB
  Цель работы: ознакомиться с явлением самоиндукции; изучить зависимость постоянной времени электрической цепи состоящей из катушки индуктивности и омического сопротивления от величины сопротивления; определить величины индуктивности катушки и магнитной проницаемости сердечника соленоида. Найдём функциональную зависимость силы тока от времени. 12 Величину t=L R называют постоянной времени цепи которая равняется времени за которое при разрядке...