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


 

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

8921. Теоретические основы менеджмента 156.5 KB
  Теоретические основы менеджмента Содержание и механизм проявления законов управления. Сущность и содержание принципов управления. Методы управления. Управление, как синтетическая наука, основывается на системе зак...
8922. Метрологическое обеспечение нестандартизованных средств измерения 56 KB
  Метрологическое обеспечение нестандартизованных средств измерения Студент должен иметь представление: - об условиях и причинах применения нестандартизованных средствах измерений знать: - состав технической докуме...
8923. Метрологическое обеспечение измерений при контроле качества и испытаниях продукции 49.5 KB
  Метрологическое обеспечение измерений при контроле качества и испытаниях продукции Студент должен иметь представление: - о классификации испытательного оборудования и требованиях к его метрологическому обеспечению знать:...
8924. Очистка природного газа и переработки кислых газов с получением товарной продукции (серы) на Карачаганакском месторождении 1.08 MB
  Введение Сформировавшемуся в последнее время нефтегазовому комплексу Республики Казахстан отводится ведущая роль в топливно-энергетическом балансе и экономике страны. При нынешних темпах развития производительных сил и освоения углеводородных ресурс...
8925. Отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта 131.5 KB
  Цель работы: Целью работы является отработка заданных режимов системы позиционирования при переменном моменте инерции нагрузки и следующих вариациях параметров объекта. - коэффициент жесткости с упругого звена - посто...
8926. Лекции по теории автоматов Часть 1 Теория абстрактных автоматов 241 KB
  Лекции по теории автоматов Часть 1 Теория абстрактных автоматов Учебное пособие для студентов очной и заочной форм обучения специальностям в области вычислительной техники, информатики и управления. ОГЛАВЛЕНИЕ Часть 1. Теория абстрактных автоматов...
8927. Енергозбереження - шлях до віддалення глобальної катастрофи 115.5 KB
  Тема 10. Енергозбереження - шлях до віддалення глобальної катастрофи Людська цивілізація знаходиться на порозі чергової кризи, звязаної з наслідками її діяльності, а саме - глобальним забрудненням довкілля, зокрема парниковими газами...
8928. Інвестиційна політика в галузі енергозбереження 122 KB
  Тема 9. Інвестиційна політика в галузі енергозбереження З таблиці 2 теми 1 бачимо, що обсяг капіталовкладень, які необхідні для забезпечення ефективної політики в галузі енергозбереження на Україні, становить у розрахунку на 2005 рік...
8929. Утилізація вторинних енергоресурсів 284.5 KB
  Утилізація вторинних енергоресурсів Будь-які енергоносії, чи енергія у формі тепла або стиснених газів, що отримуються внаслідок основних технологічних процесів, наприклад, коксування вугілля, металургійних процесів, роботи ГТУ чи ТЕС, називаються в...