8127

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

Лекция

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

Методы информированного поиска. Поиск сначала лучший. A*-поиск. Методы не информированного (слепого) поиска в большинстве случаев неэффективны. Эффективность поиска может быть повышена за счет использования дополнительны...

Русский

2013-02-04

316.08 KB

3 чел.

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

Методы неинформированного (слепого) поиска в большинстве случаев неэффективны. Эффективность поиска может быть повышена за счет использования дополнительных специфичных для данного класса задач значений.

Поиск сначала лучший. (Best-First SeachBFS).

В обобщенном алгоритме поиска единственным местом, где можно использовать дополнительные знания об особенностях задачи является функция построения очереди: Function BFS(problem, Eval-Fn). Она определяет следующую вершину для раскрытия.

Соответствующие значения обеспечиваются оценочной функцией. Эта функция возвращает число, отражающее желательность раскрытия вершины. Поиск, при котором  первой раскрывается вершина с максимальной оценкой, называется BFS. На базе общего обобщенного поиска General-Seach, функция BFS реализована следующим образом:

Quening-Fn построение очереди вершин, ожидающих раскрытия. Упорядочивает вершины в соответствии с Eval-Fn;

–после этого вызывается функция обобщенного поиска General-Seach(problem, Queuing-Fn), которой передается вершина упорядоченного поиска.

Название BFSстрого говоря не является точным, так как оценочная функция не гарантирует абсолютно лучшего, оптимального выбора вершины для раскрытия. Она лишь определяем вершину, которая представляется лучшей в соответствии с функцией оценки.

Жадный поиск. Минимизация оценочной стоимости.

Простейшей стратегией BFS является минимизация оценочной стоимости достижения цели, при этом первой раскрывается вершина, состояние которой оценивается как ближайшее к целевому состоянию.

Для большинства задач стоимость достижения цели из некоторого состояния может только оцениваться, но не может быть определена точно. Поэтому функция, вычисляющая оценки стоимости, является эвристической, ее принято обозначать h(n), где nвершина в дереве.

BFS, использующий функцию h для выбора следующей вершины, называется жадным поиском (Greedy).

function Greedy-Seach(Problem) returns solution or failure 

return BFS(Problem, h).

Требование к h: в целевом состоянии h(n)=0.

Рассмотрим идею жадного поиска на примере:


Будем рассматривать эвристический подход на примере поиска маршрута из A в F. Для задач поиска маршрута хорошей эвристической функцией является расстояние  до цели по прямой  Straight-Line-Distance. Hsld(n) –в качестве эвристической функции используется расстояние по прямой. Значение Hsld может быть вычислено по значению координат на карте. В следующей таблице укажем расстояние по прямой от пункта F до разных пунктов:

A

366

 F

M

L

Q

E

N

P

S

J

K

T

C

H

G

D

I

O

R

B


При выборе пути из D предпочтение было отдано вершине Е, так как она ближе по прямой до пункта F (цели) чем вершина G. Однако дальнейшее движение через пункт G к H и F позволяет получить более короткий путь или путь меньшей стоимости в целевое состояние. Действительно 99+211=310 > 80+97+101=278. Таким образом данная эвристическая функция не обеспечивает поиск оптимального пути. Это является следствием того, что стратегия выбирает самый выгодный ей шаг не учитывая дальнейших шагов. В целом жадный поиск как правило находит решение быстро, хотя оно не всегда является оптимальным. Жадный поиск аналогичен поиску в глубину, так как стремится двигаться к цели одним путем и возвращается лишь когда заходит в тупик. Временная сложность жадного поиска O(bm), где mмаксимальная глубина пространства поиска. Так как все вершины сохраняются в памяти , то емкостная сложность такая же как и временная. Тем не менее в конкретных задачах емкость или время может быть существенно сокращены от хорошей эвристической функции.

А* поиск.

Жадный поиск стремится минимизировать оценочную стоимость до цели h(n), что позволяет в ряде случаев повысить эффективность поиска, однако жадный поиск не является ни оптимальным, ни полным.

С другой стороны поиск по стоимости или по критерию стоимости минимизирует стоимость пути до текущего состояния g(n) и является полным и оптимальным, однако часто оказывается неэффективным. Естественно совместить эти два подхода или стратегии, чтобы использовать их преимущества. Сделать это очень просто введя аддитивную оценочную стоимость:

f(n) = g(n) +h(n)

Поскольку g(n) –это стоимость пути от начальной вершины до текущей n, а h(n) –это оценочная стоимость самого дешевого, минимального пути из n до цели, то f(n) представляет собой оценочную стоимость самого дешевого пути, проходящего через n. Стратегия, использующая такую целевую функцию, является полной и оптимальной при следующем простом ограничении на функцию h:

  1.  Функция  h не должна переоценивать или завышать стоимость достижения цели. Такая функция называется допустимой или приемлемой в теории поиска.
  2.  Если h является приемлемой, то f(n) никогда не переоценивает реальную стоимость лучшего решения, проходящего через вершину n.

BFS поиск, использующий функцию f в качестве оценочной и допустимой называется A* поиск.

Function A* - Search (Problem) return BFS(Problem, g+h)

Расстояние по прямой является примером допустимой (приемлемой) функцией для задачи поиска пути. Рассмотрим реализацию A* поиска на примере (см. предыдущий граф).

Особенность A* поиска является то, что f-стоимость любого пути от корня никогда не убывает, такая эвристическая функция, называется монотонной. В тех случаях, когда эвристика не монотонна, для восстановления монотонности используются специальные приемы. Рассмотрим пару вершин n и n1, где nродитель n1.

Пусть  g(n)=3

h(n)=4, следовательно f(n)=7

Предположим, что   g(n1)=4

  h(n1)=2, тогда f(n1)=6

Следовательно, имеется нарушение монотонности. Истинная или реальная стоимость пути по крайней мере равна 7. Для восстановления монотонности используется следующий прием:

 f(n1)=max(f(n), g(n1)+h(n1))

Это равенство называется выравниванием максимального пути. В этом случае функция f называется неубывающей вдоль любого пути. На примере графа (Жадный поиск) видно, что функция f концептуально прочерчивает контур в пространстве состояний, внутри которого находятся вершины, достижимые в пределах соответствующей стоимости. Таким образом, видно как A* поиск фокусируется в направлении целевой вершины. Обозначим f*- стоимость оптимального пути, тогда можно утверждать, что поиск A*:

  1.  Раскрывает все вершины, у которых f(n)<f*
  2.  Может раскрывать некоторые вершины, у которых f(n)=f*

Первое же найденное решение должно быть оптимальным, так как все вершины во всех последовательных контурах будут иметь более высокую f стоимость и следовательно более высокую g стоимость.

A* поиск является полным, так как по мере расширения контура с разрастанием f, неизбежно достигается контур, у которого f равна стоимости пути и целевому состоянию. A* поиск является оптимально эффективнымникакой другой оптимальный алгоритм не гарантирует нахождения оптимальных вершин эффективнее, чем A* поиск.


 

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

24367. Основные функции науки в жизни общества (наука как мировоззрение, как производительная и социальная сила) 59 KB
  Культурная сущность науки влечет за собой ее этическую и ценностную наполненность. Результативная функция науки осуществляется из систему образования воспитания обучения и подключения членов общества к исследовательской деятельности и эпосу науки. Функций у науки много и с ее развитием их становится все больше и больше.
24368. Возникновение науки. Две стратегии порождения знаний: обобщение практического опыта и конструирование теоретических моделей 104 KB
  Такой например характер имели геометрические знания древних египтян. Однако по мере развития практики наряду с отмеченными способами познания формируется новый способ построения знания. При таком методе исходные идеальные объекты черпаются уже не из практики а заимствуются из ранее сложившихся систем знаний языка и применяются в качестве строительного материала при формировании нового знания. Таким образом в науке наряду с эмпирическими правилами и зависимостями которые знала и преднаука формируется особый тип знания теория...
24369. Античный этап развития науки: логика и математика 104 KB
  Первые европейские ученые и философы любители мудрости Фалес Анакасимен Анаксимандр Гераклит опираясь на факты и логику впервые мыслили вещи не фантастически а стремились к естественнонаучном безличному целостному описанию природы космоса мира. Осуществляя многочисленные наблюдения за поведением планет Солнца природных и общественных явлений используя также и мифологически воззрения от них полностью устраниться не удалось они пытались найти как общие законы изменения и устройства мира так и частные его характеристики....
24370. Наука средневековья. Роль христианской теологии в изменении созерцательной позиции ученого 114 KB
  Начало мира это сам Бог. В результате христианское учение постепенно стало приобретать форму рациональной теологии где определенное место отводилось вопросам познания устройства мира. Предельность конечность мира в пространстве включала геоцентризм Аристотеля и Птоломея и оттеняла космическую функцию Христа. Он как бы замещал исследование причинноследственных связей превращался в важнейший способ восприятия мира и выражения опыта развивал мышление позволяя превращать истины веры в зрительные образы.
24371. Формирование идеалов (математизированное и опытное, экспериментальное знание) науки Нового времени (Г. Галилей, Ф. Бэкон, Р. Декарт) 127 KB
  это время становления новой современной науки. Этому способствовали как внутренние изменения самой науки уже Коперник и Кеплер свою гелиоцентрическую картину мира обосновывают с помощью математического расчета. Давление воды на лопатку движение деталей насоса кузнечного молота шелкопрядильной машины включали в себя непрерывную цепь механических причин и следствий ставших основой механической картины мира классического идеала науки.
24372. Формирование и соотношение естественных, технических и социально-гуманитарных наук: сходство и различия 106 KB
  Лпркшпрожю Развитие технических наук стимулирует развитие естествознания их взаимосвязь не прервалась и после выделения технической науки в отдельную область знания. В то же время существует большой разрыв между действительным применением результатов технической науки на практике и занятием самой этой наукой. С методологической точки зрения исследование в технической науке не сильно отличается от естественнонаучного исследования. Таким образом в научнотехнических дисциплинах необходимо четко различать исследования включенные в инженерную...
24373. Многообразие типов научного знания. Сущность и структура эмпирического знания 55 KB
  Материализация и первичное обобщение данных отражения в форме знания на основе правил соответствия узнавание сравнение измерение описание образуют эмпирические факты эмпирические объекты эмпирическую информацию. Эмпирические факты условно можно разделить на два вида: а факты в основание которых лежат не зависящие от субъекта явления например природные процессы и б факты созданные человеком например экономика экономические отношения. Эмпирические факты обладают большей степенью общности чем единичные данные но меньшей чем...
24374. Сущность и структура теоретического знания 52.5 KB
  Теория это высшая самая развитая форма организации научного знания дающая целостное представление о закономерностях и существенных связях определенное области действительности объекта данной теории 77. С помощью этих знаковых образований языка теории возникает возможность более точно и глубоко судить о соответствующей изучаемой предметной области. Кроме того тот или иной вид теории определяется предметом и задачами исследования глубиной раскрытия сущности предметов и др. Также имеют место попытки поиска идеальной схемы...
24375. Основания науки: нормы и идеалы науки, роль философских идей и принципов в обосновании научного знания (законы и категории) 116.5 KB
  Среди идеалов и норм можно выделить два взаимосвязанных блока: а собственно познавательные установки которые регулируют процесс воспроизведения в различных формах научного знания; б социальные нормативы фиксируют роль науки и ее ценность для общественной жизни на определенном этапе исторического развития. Существует еще и такое мнение что в период нормального эволюционного периода развития науки возможно бессознательное использование многих научных идеалов и норм. Закон единства и борьбы противоположностей является ядром диалектики...