8125

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

Лекция

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

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

Русский

2013-02-04

142.53 KB

28 чел.

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


 

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

987. Проектирование сопроцессора для умножения чисел в обратном коде 417.5 KB
  Разработка функциональной схемы операционного автомата. Особенности реализации Узлов спецпроцессора выполненных на реальных микросхемах. Разработка структурной схемы управляющего автомата. Описание функциональных узлов операционного автомата.
988. Финансово-экономический анализ предприятия агропромышленного комплекса 714 KB
  Классификация основных методов и приемов финансово-экономического анализа предприятия и его информационная база. Виды деятельности, форма собственности и основные технико-экономические показатели предприятия. Анализ статей баланса, их структуры и динамики, оценка ликвидности баланса.
989. Расчет и проектирование коническо-цилиндрического редуктора 739.5 KB
  Частота вращения тихоходного вала редуктора. Выбор материалов и допускаемые напряжения. Определение геометрических размеров передач. Определение геометрических размеров зубчатых колес. Определение сил в конической зубчатой передаче. Выбор материалов и допускаемые напряжения.
990. Планирование деятельности предприятия 496 KB
  Составление сметы расходов на производство и реализацию продукции. Определение плановой величины материальных расходов. Расчет величины прочих расходов на производство и реализацию продукции.
991. Электропитающие системы и электрические сети 236 KB
  Баланс активной мощности и выбор генераторов ТЭЦ. Обоснование схемы и напряжения электрической сети. Регулирование напряжения. Расчет установившегося режима электрической сети. Приведение нагрузок узлов и мощности ТЭЦ к стороне ВН.
992. Методы управления рисками в системе ипотечного кредитования 422 KB
  Основные принципы и структурные элементы системы ипотечного кредитования. Европейская (одноуровневая) модель ипотечного кредитования. Современная американская (двухуровневая) модель ипотечного кредитования. Законодательное обеспечение системы ипотечного кредитования в Российской Федерации. Классификация методов управления рисками в системе ипотечного кредитования. Обеспечение кредитного обязательства рыночной стоимостью предмета ипотеки.
993. Методы поиска минимума функции на отрезке. Программная реализация 579.5 KB
  Нахождение минимума функции на заданном отрезке - одна из простейших задач в разделе численных методов анализа. Существует множество различных способов определения минимума функции с разным количеством итераций и уровнем определения точности. Так же возможно комбинировать некоторые способы для достижения большей эффективности алгоритма.
994. Математические методы и исследование операций в экономике 662.91 KB
  Диагностика функционирования рыночных механизмов на предприятии. Жизненный цикл конкурентного преимущества фирмы. Внешние сигналы о возможных изменениях состояния. Сканирование внешней и внутренней среды фирмы — условие обнаружения слабых сигналов о надвигающемся кризисе.
995. Разработка технологического процесса обработки щита подшипникового 275.5 KB
  Описание конструкции и служебного назначения детали. Выбор вида и обоснование метода получения заготовки. Определение размеров, массы и стоимости детали. Проектирование технологического маршрута обработки и технологического процесса. Выбор оборудования, приспособлений, мерительного инструмента.