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


 

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

77245. Вспомогательный аппарат глаза 371.42 KB
  nulus tendineus communis Верхняя прямая мышца Нижняя прямая мышца Латеральная прямая Медиальная прямая Верхняя косая Нижняя косая Мышца поднимающая верхнее веко Бровь supercilium Веко plpebre защитная функция: plpebr superior plpebr inferior fcies nterior покрыта кожей fcies posterior покрыта хрящевой и орбитальной коньюктивой. Верхняя прямая мышца Нижняя прямая мышца Медиальная прямая Нижняя косая Мышца поднимающая верхнее веко. Латеральная прямая 6 пара ЧН отводящий Верхняя косая 4 пара ЧН блоковый Нервы слезной...
77246. Наружнее и среднее ухо,их отделы. Барабанная полость, ее стенки сообщения и содержимое. Артерии, вены, нервы барабанной полости 43.54 KB
  Артерии вены нервы барабанной полости. Наружний слуховой проход metus custicus externus Prs cortilgine Cortillgo metus custici externiсоставляет одно целое с хрящем ушной раковины Incisure crtilginis metus custici externi Сартолиниевы шели Хрящевая часть выстлана тонкой кожей в которой имеются волоски сальные и цируминозные железы prs osse Образованна барабанной частью височной кости 3.Внутреннийпродолжение слизистой оболочки выстилающей барабанную полость Кровоснабжение Среднее ухо uris medi включает в себя: Cvits timpnic tub...
77248. Внутреннее ухо. Его части, содержимое. Строение полукружных каналов и преддверия. Преддверно-улитковый нерв, ядра, части. Вестибулярный путь 145.78 KB
  Преддверноулитковый нерв ядра части. Ядра слуховые ядра: nuclei cochleres nterior et posterior вестибулярные ядра: верхнееБехтерева нижнее Роллера латеральное Дейтерса медиальное Швальбе в области латерального угла foss rhomboide 2. Место выхода из черепа: porus custicus internus Вестибулярный путь От рецепторов статокинетического аппаратаампулярные гребешки и отолитовые аппараты внутреннего уха импульсы поступают к gnglion vestibulre 1 нейроны Далее в составе rdix vestibulris они входят в мостомозжечковый угол и...
77249. Глазодвигательный, блоковый, отводящий нервы. Медиальный продольный пучок 14.76 KB
  oculomotorius IIIсмешанный: Ядра серое вещество среднего мозга: N. ciliris Место выхода из мозга foss interpedunculris 3 Место выхода из черепа fissur orbitlis superior. trochleris IV двигательный: Ядрасерое вещество среднего мозга: N.obliquus superior 2 Место выхода из мозга сбоку от velum medullre superius.
77252. Тройничный нерв, его ядра, корешки, узел. Третья ветвь тройничного нерва 42.16 KB
  tensor tympni m. lingulis В области основания черепа присоединяет chord tympni преганглионарные парасимпатические волокна от n. lingules общая и вкусовая за счёт chord tympni чувствительность передних 2 3 языка rr. sublingules к подъязычной и поднижнечелюстной слюнным железам слизистой оболочке дна полости рта десне нижней челюсти chord tympni заканчивается на gg.
77253. Лицевой нерв, его ядра, ганглии и ветви 42.5 KB
  Через metus custicus internus в cnlis n. petrosus mjor парасимпатический ответвляется на уровне коленца идёт в cnlis n. petrosi mjoris через hitus cnlis n. petrosi mjoris до formen lcerum откуда идёт через cnlis pterygoideus где к нему присоединяется симпатический n.