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


 

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

29509. Психотерапія сексуальних розладів 83 KB
  Психотерапія сексуальних розладів. Психотерапія сексуальних розладів. В наш час дія при проведенні психотерапії сексуальних дисфункцій більш визначена ніж медикаментозна терапія. Карен Хорні – підкреслювала що розвиток сексуальних порушень найбільшу роль відіграє невротичний перехрест комплексів.
29510. Статеві стосунки в подружньому житті 86.5 KB
  Це важливо також при вирішенні сексуальних проблем подружжя і їх родинної взаємодії. В основі розгортання сексуальних реакцій тільки гормональна забезпеченість представляється більш важливою ніж психологічна складова. На рівні підсистеми сексуальних відносин мають значення гармонія сексуальних стосунків чи дисгармонія їх. Жіночі сексуальні розлади які призводять до дисгармонії сексуальних стосунків.
29511. Статеві стосунки в сімейному житті 91.5 KB
  Нерідко психічна імпотенція накладається на органічну але незначну і виникає психосоматична модель порушень статевого акту. Особлива схильність пацієнтів з психічною імпотенцією звинувачувати себе в онанізмі та інших “розпуствах†і шукати причини свого статевого безсилля в неіснуючих у них венеричних захворюваннях не завжди справдуються. А також алкоголізм чи застосування алкогольних напоїв для стимуляції статевого збудження. Зниження статевого потягу – може бути пов’язана з транзиторною сублімацією – переключенням сексуальної...
29512. Означення поняття сексологія і сексопатологія 158.5 KB
  Сексологія вивчає закономірності психосексуального розвитку диференціації і детермінації статі формування сексуальної орієнтації та ідентичності статевовікові особливості психосексуального розвитку і сексуальної поведінки. Статеве дозрівання статевий розвиток – це процес формування вторинних статевих ознак розвиток репродуктивних органів і здатність до народження дітей. Психосексуальний розвиток ПСР – це формування статевої самосвідомості статевої ролі і психосексуальної орієнтації а саме – формування векторів сексуального потягу...
29513. Формування сексуальної орієнтації і норми 43 KB
  Означення поняття сексуальної норми включає поведінку, відповідну віковим та статево-рольовим закономерностям даної популяції, яка здійснюється в результаті вільного вибору і не обмежує у вільному виборі партнера (А.А. Ткаченко). В сексології розрізняють поняття індивідуальної та партнерської норми.
29514. Формування сексуальної норми 98.5 KB
  запропонував робочу класифікацію ролей чоловіків і жінок в статевому циклі. Її сексуальність носить материнський характер опіка захист турбота до чоловіка що проявляється в її мові використання зменшених ласкавих слів поведінці достатньо активні але не агресивні пестощі з її боку смаки і симпатії віддають перевагу слабким невпевненим в собі інфантільним навіть хворим чоловікам яких годує лікує опікується ними тощо. Ідеальний партнер для тривожних боязких неуспішних чоловіків котрих вона “навчає коханню†підтримує....
29515. Формування сексуальної норми і орієнтації 104 KB
  При наявності високого еротичного показника 4 – 5 оргазм може виникнути без статевого акту. Пестощі бувають першого другого третього порядку – це терміни які відображають послідовність пестощів необхідних для розвитку статевого збудження. Початок статевого акту повинен проходити на фоні значного сексуального збудження жінки включаючи як фізичні так і психічні зміни. Шкала статевого збудження жінки: вегетативносудинний рівень – 10 – 20 ; моторномовленнєвий рівень – 30 – 40 ; поведінковий рівень – 40 – 50 ; психічні прояви –...
29516. Порушення статевої та психосексуальної диференціації та ідентичності, причини і форми 67.5 KB
  Психосексуальна диференціація ПСД – як процес представляє собою явище механізми котрого визначаються взаємодією детермінант статі. Статева та сексуальна ідентифікація – жіноча; Анарія – порок розвитку внутрішньоутробне порушення зовнішніх органів яєчек недорозвиток статевого органу – може бути заміна статі; Дісгенезія гонад – гермофродитизм істиний – і чоловічі і жіночі елементи внутрішніх статевих органів – частіше як дівчинки в подальшому – зміна статі. Питання зміни статі А.Бєлкін 1978 описує порушення індентифікації у...
29517. Сексологічне обстеження 164.5 KB
  Більшість спеціалістів розуміють що обстеження сексологічних пацієнтів має свої особливості: інтимність питання “закритість†пацієнтів їх невміння обговорювати своє сексуальне життя відсутність адекватної мови для обговорення цих порушень. – 4 варіанти уявних порушень: зі ставленням до себе підвищених вимог; невротична тривога – психотична; ненормальні уявлення про статеві стосунки пацієнта або пари – роз’янень.2 наявність сексуальних порушень у партнера. Аналіз статевих порушень з позицій “психогенне особистісно –...