8125

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

Лекция

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

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

Русский

2013-02-04

142.53 KB

27 чел.

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


 

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

22966. Історичні типи світогляду: світоглядні погляди або уявлення певної епохи 52 KB
  Будьте уважні термін філософія змінювався. Вперше в первинному розумінні терміном філософія позначалась уся сукупність зань про все в перекладі любов до мудрості. Філософія це любов до мудрості це людська справа мудрими можуть будити лише боги а люди можуть тільки любити мудрість. Те що для буденної свідомості для релігії здається безсумнівною істиною те для філософії є вихідним пунктом роздуму над цим філософія думає.
22967. Форми філософського знання 51 KB
  Онтологія теорія буття теорія дійсності розглядаються основні принципи що визначають устрій світу. Ми робимо такий висновок що Філософія це найбільш пізній зрілий тип світогляду це система найбільш загальних теоретичних уявлень про взаємодію людини і світу. В людини є виначальні орієнтації визначаються особливостями її життєдіяльності і духовного світу. Ми змушені рахуватися з закономірностями зовнішнього світу.
22968. Найважливіші філософські питання 42 KB
  Теоретичний раціональний філософія наука. Духовний емоційноціннісний філософія релігія. Але філософія не є ні наукою ні релігією філософія це тип світогляду який повязаний з наукою і релігією не більше.
22969. Структура і архітектура мікропроцесора КР580ВМ80 (8080) 2.99 MB
  Найважливішим елементом у схемі мікропроцесора є мабуть арифметикологічний пристрій АЛП який здійснює обробку інформації. Інформація яка підлягає обробці операнди потрапляє до АЛП з внутрішньої шини даних розрядність якої складає у даного мікропроцесора вісім розрядів. Його можна записати до одного з робочих регістрів РР мікропроцесора: регістрів BCDE.
22970. Як працює мікропроцесор 1.86 MB
  Машинний цикл є процедура звернення процесора до памяті чи зовнішнього пристрою для запису читання або обробки інформації. Так наприклад двобайтова команда MVI B A9 тобто записати число А9 у регістр В виконується за два машинні цикли: Звернення до памяті за адресою що міститься у лічильнику команд. Память виставляє на ШД код команди MVI B = 06 H = 0000 0110 B. У другому машинному циклі цей другий байт видобувається з памяті і заноситься до робочого регістру В.
22971. Системний контролер.Керуючий пристрій. Мікропрогамування 2.88 MB
  Мікропрогамування Як вже йшлося вище слово стану видається мікропроцесором у першому такті кожного машинного циклу і триває тільки один такт. Тому слово стану повинно десь зберігатися напротязі усього циклу. Роль такого хранителя слова стану виконує спеціальний пристрій що є обовязковою частиною мікропроцесорної системи і має назву системного контролера. Другою функцією системного контролера є перетворення коду слова стану в керуючі сигнали котрі безпосередньо подаються вже на основну память або зовнішні пристрої і керують їх роботою.
22972. Системи числення, які застосовуються у мікропроцесорній техніці 713.5 KB
  Так наприклад число 371 може бути розкладено по степенях числа 10 таким чином: 371=3х1027х1011х100 = 300701 Двійкова система числення У електроннообчислювальній техніці зручніше користуватися двійковою системою числення в основі якої лежить число 2. Так наприклад число 1001 є 4 бітовим числом а розглянутий нами вище двійковий еквівалент числа 37110 тобто 101110011 девятибітовим числом. Для цього багаторозрядне двійкове число розбивається на тетради кожна з яких містить по чотири розряди двійкового числа.
22973. Мікропрцесори та малі електронно-обчислювальнні машини (ЕОМ) 1.85 MB
  Будова і принцип дії центральної частини малої ЕОМ Кожна мала електронно обчислювальна машина ЕОМ містить два блоки процесор і основну память рис. У блоці основної памяті зберігається оброблювана інформація і програми за якими вона обробляється. Процес розвязання будь якої задачі на ЕОМ складається з послідовності елементарних дій котрі може виконувати процесор а саме операції вибірки інформації з памяті або запису до неї арифметичні та логічні операції операції порівняння тощо. На кожному кроці обробки інформації процесор...
22974. Робота з зовнішніми пристроями. Паралельний інтерфейс. 6.59 MB
  Але зручніше скористатися спеціальною ВІС паралельним програмованим адаптером ППА типу КР580ВВ55А в міжнародних позначеннях 8255А. ППА спроможний обслуговувати 3 зовнішні пристрої через три свої порти АВ і С кожний по 8 розрядів. вибір кристалу =1 ППА відключений = 0 ППА задіяний. Комбінація що відповідає DРКС означає запис в РКС регістр керуючого слова інструкції про те що має робити ППА.