Эвристическая функция
Информи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.
Информация о конкретной задаче формулируется в виде эвристической функции. Эвристическая функция на каждом шаге перебора оценивает альтернативы на основании дополнительной информации с целью принятия решения о том, в каком направлении следует продолжать перебор.
Эвристические функции
В контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function) h(n) определена на узлах дерева перебора следующим образом:
- h(n) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.
Если n — целевой узел, то h(n) = 0.
Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function)
- f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n,
- f(n) = g(n) + h(n),
где функция g(n) определяет стоимость уже пройденного пути от начального узла до узла n.
f1(n) = g(n) + h1(n) — недопустимая эвристика
f2(n) = g(n) + h2(n) — допустимая, но не преемственная
f3(n) = g(n) + h3(n) — преемственная эвристика
Если эвристическая функция h(n) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible).
Если эвристическая функция h(n) удовлетворяет условию
- h(a) ≤ cost(a, b) + h(b),
где b — потомок a, то такая функция называется преемственной (англ. consistent).
Если f(n) = g(n) + h(n) — функция оценки, h(n) — преемственная функция, то функция f(n) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic).
Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной.
Если h1(n), h2(n) — допустимые эвристические функции, и для любого узла n верно неравенство h1(n) ≥ h2(n), то h1 является более информированной эвристикой, или доминирует над h2.
Если для задачи существуют допустимые эвристики h1 и h2, то эвристика h(n) = max(h1, h2) является допустимой и доминирует над каждой из исходных эвристик.
Сравнение эвристических функций
При сравнении допустимых эвристик имеют значение степень информированности и пространственная и временная сложность вычисления каждой из эвристик. Более информированные эвристики позволяют сократить количество развёртываемых узлов, хотя платой за это могут быть затраты времени на вычисление эвристики для каждого узла.
Эффективный коэффициент ветвления (англ. effective branching factor) — среднее число преемников узла в дереве перебора после применения эвристических методов отсечения. По эффективному коэффициенту ветвления можно судить о качестве используемой эвристической функции.
Идеальная эвристическая функция (например, таблица поиска) всегда возвращает точные значения длины кратчайшего решения, поэтому дерево перебора содержит только оптимальные решения. Эффективный коэффициент ветвления идеальной эвристической функции близок к 1.
Примеры задач поиска
hm(n)=3+0+0+3+2+4+2+4+1+3+2+2+
+3+3+2=34.
Оптимальное решение состоит из 50 ходов.
В качестве моделей для испытания алгоритмов поиска и эвристических функций часто используются перестановочные головоломки — Пятнашки 3×3, 4×4, 5×5, 6×6, кубик Рубика, Ханойская башня с четырьмя стержнями.
В головоломке «Пятнашки» может быть применена эвристика hm, основанная на манхэттенском расстоянии. Более конкретно, для каждой плитки подсчитывается манхэттенское расстояние между её текущим положением и её положением в начальном состоянии; полученные величины суммируются.
Можно показать, что эта эвристика является допустимой и преемственной: за один ход её значение не может измениться более чем на ±1.
Конструирование эвристических функций
Ослабленная задача
Эвристическая функция hm, использующаяся для решения головоломки «Пятнашки», представляет собой нижнюю оценку длины оптимального решения. Помимо этого, hm(n) — это точное значение длины оптимального решения упрощённой версии головоломки, в которой плитки можно передвигать в занятые позиции. В исходной головоломке присутствует ограничение «в одной клетке не должны находиться две и более плитки», которого нет в упрощённой версии. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей (англ. relaxed problem); стоимость решения ослабленной задачи является допустимой эвристикой для первоначальной задачи, так как любое решение первоначальной задачи является также решением ослабленной задачи.
Подзадача
Допустимая эвристика может быть основана на стоимости решения подзадачи (англ. subproblem) исходной задачи. Любое решение основной задачи одновременно является решением каждой из её подзадач.
Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.
Базы данных с шаблонами
Базы данных с шаблонами (англ. Pattern databases) — вид допустимой эвристики, в основе которого лежит идея хранения точного значения стоимости решения для каждого возможного экземпляра подзадачи.
Пример шаблона для головоломки «Пятнашки» изображён на рисунке справа: в определение подзадачи входят позиции семи фишек, находящихся в первом столбце и в первой строке. Количество конфигураций этого шаблона равно 
. Для каждой из конфигураций база данных содержит минимальное количество ходов, необходимое для перевода этой конфигурации в целевую конфигурацию подзадачи, показанную на рисунке. Построение базы данных осуществляется методом обратного поиска в ширину.
Алгоритмы поиска
Поиск по первому наилучшему совпадению
Поиск по первому наилучшему совпадению (англ. best-first search) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f(n). Для развёртывания выбирается узел с наименьшей оценкой.
Поиск A*
Поиск A* — наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f(n) стоимости наименее дорогостоящего пути решения, проходящего через узел n:
- f(n) = g(n) + h(n), где
- g(n) — стоимость пути от начального узла до узла n,
- h(n) — оценка стоимости пути от узла n до цели.
Если h(n) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.
IDA*
Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска.
Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости пути bound.
Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS.
Псевдокод
node текущий узел g стоимость начала решения root..node f оценка стоимости минимального пути через node h(node) эвристическая оценка стоимости остатка пути node..goal cost(node, succ) функция стоимости пути is_goal(node) функция проверки цели successors(node) функция развёртывания узла node procedure ida_star(root, cost(), is_goal(), h()) bound := h(root) loop t := search(root, 0, bound) if t = FOUND then return FOUND if t = ∞ then return NOT_FOUND bound := t end loop end procedure function search(node, g, bound) f := g + h(node) if f > bound then return f if is_goal(node) then return FOUND min := ∞ for succ in successors(node) do t := search(succ, g + cost(node, succ), bound) if t = FOUND then return FOUND if t < min then min := t end for return min end function
MA*
Этот раздел нужно дополнить. |
SMA*
SMA*
Этот раздел нужно дополнить. |
RBFS
Это пустой раздел, который еще не написан. |
См. также
- Неинформированный метод поиска
Примечания
- Стюарт Рассел, Питер Норвиг. Составление допустимых эвристических функций // Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд.. — М.: Вильямс, 2006. — С. 170 — 173. — 1408 с. — ISBN 5-8459-0887-6.
- Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
- Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. — 1993.
- Daniel R. Kunkle. Solving the 8 Puzzle in a Minimum Number of Moves: An Application of the A* Algorithm. — 2001.
- Richard E. Korf. Depth-first iterative-deepening: An optimal admissible tree search. — 1985.
- Joseph C. Culberson, Jonathan Schaeffer. Pattern Databases. — 1998.
- Richard E. Korf, Peter Schultze. Large-Scale Parallel Breadth-First Search. — 2005.
- Richard E. Korf, Larry A. Taylor. Finding Optimal Solutions to the Twenty-Four Puzzle. — 1996. Архивировано 10 сентября 2015 года.
- Richard E. Korf. Recent Progress in the Design and Analysis of Admissible Heuristic Functions. — 2000.
- Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. — 2002. Архивировано 7 мая 2019 года.
- Ariel Felner, Richard E. Korf, Sarit Hanan. Additive Pattern Database Heuristics. — 2004. Архивировано 1 декабря 2021 года.
- Richard E. Korf. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. — 1997.
- Richard E. Korf, Ariel Felner. Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem. — 2007.
- Основан на Lecture Notes: IDA* Архивная копия от 22 июня 2012 на Wayback Machine
Литература
- Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
- Стюарт Рассел, Питер Норвиг. Составление допустимых эвристических функций // Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд.. — М.: Вильямс, 2006. — С. 170 — 173. — 1408 с. — ISBN 5-8459-0887-6.
Ссылки
Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Эвристическая функция, Что такое Эвристическая функция? Что означает Эвристическая функция?
Informi rovannyj po isk takzhe evristicheskij poisk angl informed search heuristic search strategiya poiska reshenij v prostranstve sostoyanij v kotoroj ispolzuyutsya znaniya otnosyashiesya k konkretnoj zadache Informirovannye metody obychno obespechivayut bolee effektivnyj poisk po sravneniyu s neinformirovannymi metodami Informaciya o konkretnoj zadache formuliruetsya v vide evristicheskoj funkcii Evristicheskaya funkciya na kazhdom shage perebora ocenivaet alternativy na osnovanii dopolnitelnoj informacii s celyu prinyatiya resheniya o tom v kakom napravlenii sleduet prodolzhat perebor Evristicheskie funkciiV kontekste poiska v prostranstve sostoyanij evristicheskaya funkciya angl heuristic function h n opredelena na uzlah dereva perebora sleduyushim obrazom h n ocenka stoimosti naimenee dorogostoyashego puti ot uzla n do celevogo uzla dd Esli n celevoj uzel to h n 0 Uzel dlya razvyortyvaniya vybiraetsya na osnove funkcii ocenki angl evaluation function f n ocenka stoimosti naimenee dorogostoyashego puti resheniya prohodyashego cherez uzel n f n g n h n dd gde funkciya g n opredelyaet stoimost uzhe projdennogo puti ot nachalnogo uzla do uzla n Znacheniya funkcij vdol optimalnogo resheniya f1 n g n h1 n nedopustimaya evristika f2 n g n h2 n dopustimaya no ne preemstvennaya f3 n g n h3 n preemstvennaya evristika Esli evristicheskaya funkciya h n nikogda ne pereocenivaet fakticheskuyu minimalnuyu stoimost dostizheniya celi to est yavlyaetsya nizhnej ocenkoj fakticheskoj stoimosti to takaya funkciya nazyvaetsya dopustimoj angl admissible Esli evristicheskaya funkciya h n udovletvoryaet usloviyu h a cost a b h b dd gde b potomok a to takaya funkciya nazyvaetsya preemstvennoj angl consistent Esli f n g n h n funkciya ocenki h n preemstvennaya funkciya to funkciya f n yavlyaetsya monotonno neubyvayushej vdol lyubogo issleduemogo puti Poetomu preemstvennye funkcii takzhe nazyvayutsya monotonnymi angl monotonic Lyubaya preemstvennaya funkciya yavlyaetsya dopustimoj no ne lyubaya dopustimaya funkciya yavlyaetsya preemstvennoj Esli h1 n h2 n dopustimye evristicheskie funkcii i dlya lyubogo uzla n verno neravenstvo h1 n h2 n to h1 yavlyaetsya bolee informirovannoj evristikoj ili dominiruet nad h2 Esli dlya zadachi sushestvuyut dopustimye evristiki h1 i h2 to evristika h n max h1 h2 yavlyaetsya dopustimoj i dominiruet nad kazhdoj iz ishodnyh evristik Sravnenie evristicheskih funkcij Pri sravnenii dopustimyh evristik imeyut znachenie stepen informirovannosti i prostranstvennaya i vremennaya slozhnost vychisleniya kazhdoj iz evristik Bolee informirovannye evristiki pozvolyayut sokratit kolichestvo razvyortyvaemyh uzlov hotya platoj za eto mogut byt zatraty vremeni na vychislenie evristiki dlya kazhdogo uzla Effektivnyj koefficient vetvleniya angl effective branching factor srednee chislo preemnikov uzla v dereve perebora posle primeneniya evristicheskih metodov otsecheniya Po effektivnomu koefficientu vetvleniya mozhno sudit o kachestve ispolzuemoj evristicheskoj funkcii Idealnaya evristicheskaya funkciya naprimer tablica poiska vsegda vozvrashaet tochnye znacheniya dliny kratchajshego resheniya poetomu derevo perebora soderzhit tolko optimalnye resheniya Effektivnyj koefficient vetvleniya idealnoj evristicheskoj funkcii blizok k 1 Primery zadach poiska Summa manhettenskih rasstoyanij vseh plitok ot ih celevyh pozicij hm n 3 0 0 3 2 4 2 4 1 3 2 2 3 3 2 34 Optimalnoe reshenie sostoit iz 50 hodov V kachestve modelej dlya ispytaniya algoritmov poiska i evristicheskih funkcij chasto ispolzuyutsya perestanovochnye golovolomki Pyatnashki 3 3 4 4 5 5 6 6 kubik Rubika Hanojskaya bashnya s chetyrmya sterzhnyami V golovolomke Pyatnashki mozhet byt primenena evristika hm osnovannaya na manhettenskom rasstoyanii Bolee konkretno dlya kazhdoj plitki podschityvaetsya manhettenskoe rasstoyanie mezhdu eyo tekushim polozheniem i eyo polozheniem v nachalnom sostoyanii poluchennye velichiny summiruyutsya Mozhno pokazat chto eta evristika yavlyaetsya dopustimoj i preemstvennoj za odin hod eyo znachenie ne mozhet izmenitsya bolee chem na 1 Konstruirovanie evristicheskih funkcij Oslablennaya zadacha Evristicheskaya funkciya hm ispolzuyushayasya dlya resheniya golovolomki Pyatnashki predstavlyaet soboj nizhnyuyu ocenku dliny optimalnogo resheniya Pomimo etogo hm n eto tochnoe znachenie dliny optimalnogo resheniya uproshyonnoj versii golovolomki v kotoroj plitki mozhno peredvigat v zanyatye pozicii V ishodnoj golovolomke prisutstvuet ogranichenie v odnoj kletke ne dolzhny nahoditsya dve i bolee plitki kotorogo net v uproshyonnoj versii Zadacha s menshim kolichestvom ogranichenij na vozmozhnye dejstviya nazyvaetsya oslablennoj zadachej angl relaxed problem stoimost resheniya oslablennoj zadachi yavlyaetsya dopustimoj evristikoj dlya pervonachalnoj zadachi tak kak lyuboe reshenie pervonachalnoj zadachi yavlyaetsya takzhe resheniem oslablennoj zadachi Podzadacha Dopustimaya evristika mozhet byt osnovana na stoimosti resheniya podzadachi angl subproblem ishodnoj zadachi Lyuboe reshenie osnovnoj zadachi odnovremenno yavlyaetsya resheniem kazhdoj iz eyo podzadach Podzadachej zadachi resheniya golovolomki Pyatnashki mozhet byt zadacha peremesheniya na svoi mesta plitok 1 2 3 i 4 Stoimost resheniya etoj podzadachi yavlyaetsya dopustimoj evristikoj dlya ishodnoj zadachi Bazy dannyh s shablonami Shablon fringe celevaya konfiguraciya podzadachi Bazy dannyh s shablonami angl Pattern databases vid dopustimoj evristiki v osnove kotorogo lezhit ideya hraneniya tochnogo znacheniya stoimosti resheniya dlya kazhdogo vozmozhnogo ekzemplyara podzadachi Primer shablona dlya golovolomki Pyatnashki izobrazhyon na risunke sprava v opredelenie podzadachi vhodyat pozicii semi fishek nahodyashihsya v pervom stolbce i v pervoj stroke Kolichestvo konfiguracij etogo shablona ravno 16 8 518918400 displaystyle dfrac 16 8 518918400 Dlya kazhdoj iz konfiguracij baza dannyh soderzhit minimalnoe kolichestvo hodov neobhodimoe dlya perevoda etoj konfiguracii v celevuyu konfiguraciyu podzadachi pokazannuyu na risunke Postroenie bazy dannyh osushestvlyaetsya metodom obratnogo poiska v shirinu Algoritmy poiskaPoisk po pervomu nailuchshemu sovpadeniyu Sm takzhe Poisk po pervomu nailuchshemu sovpadeniyu Poisk po pervomu nailuchshemu sovpadeniyu angl best first search predstavlyaet soboj podhod v kotorom uzel dlya razvyortyvaniya vybiraetsya na osnove ocenochnoj funkcii f n Dlya razvyortyvaniya vybiraetsya uzel s naimenshej ocenkoj Poisk A Osnovnaya statya Algoritm poiska A Poisk A naibolee izvestnaya raznovidnost poiska po pervomu nailuchshemu sovpadeniyu V nyom primenyaetsya ocenka f n stoimosti naimenee dorogostoyashego puti resheniya prohodyashego cherez uzel n f n g n h n gdeg n stoimost puti ot nachalnogo uzla do uzla n h n ocenka stoimosti puti ot uzla n do celi dd Esli h n nikogda ne pereocenivaet stoimost dostizheniya celi to est yavlyaetsya dopustimoj to poisk A yavlyaetsya optimalnym IDA Algoritm A s iterativnym uglubleniem iterative deepening A IDA primenenie idei iterativnogo uglubleniya v kontekste evristicheskogo poiska Neinformirovannyj algoritm iterativnogo uglubleniya ostanavlivaet razvyortyvanie kogda glubina poiska d prevyshaet tekushij predel glubiny l Informirovannyj algoritm IDA ostanavlivaet razvyortyvanie kogda ocenka f n stoimosti puti cherez tekushij uzel n prevyshaet tekushij predel stoimosti puti bound Algoritm IDA otlichaetsya minimalnymi zatratami pamyati po sravneniyu s A i sravnitelno malym v sluchae udachnogo vybora evristiki kolichestvom razvyornutyh uzlov po sravneniyu s IDDFS Psevdokod node tekushij uzel g stoimost nachala resheniya root node f ocenka stoimosti minimalnogo puti cherez node h node evristicheskaya ocenka stoimosti ostatka puti node goal cost node succ funkciya stoimosti puti is goal node funkciya proverki celi successors node funkciya razvyortyvaniya uzla node procedure ida star root cost is goal h bound h root loop t search root 0 bound if t FOUND then return FOUND if t then return NOT FOUND bound t end loop end procedure function search node g bound f g h node if f gt bound then return f if is goal node then return FOUND min for succ in successors node do t search succ g cost node succ bound if t FOUND then return FOUND if t lt min then min t end for return min end function MA Etot razdel nuzhno dopolnit Pozhalujsta uluchshite i dopolnite razdel 30 noyabrya 2016 SMA SMA Etot razdel nuzhno dopolnit Pozhalujsta uluchshite i dopolnite razdel 30 noyabrya 2016 RBFS Eto pustoj razdel kotoryj eshe ne napisan Zdes mozhet raspolagatsya otdelnyj razdel Pomogite Vikipedii napisav ego 30 noyabrya 2016 Sm takzheNeinformirovannyj metod poiskaPrimechaniyaStyuart Rassel Piter Norvig Sostavlenie dopustimyh evristicheskih funkcij Iskusstvennyj intellekt sovremennyj podhod Artificial Intelligence A Modern Approach 2 e izd M Vilyams 2006 S 170 173 1408 s ISBN 5 8459 0887 6 Stefan Edelkamp Stefan Schrodl Heuristic search theory and applications Morgan Kaufmann Publishers 2012 712 s ISBN 978 0 12 372512 7 Alexander Reinefeld Complete Solution of the Eight Puzzle and the Benefit of Node Ordering in IDA 1993 Daniel R Kunkle Solving the 8 Puzzle in a Minimum Number of Moves An Application of the A Algorithm 2001 Richard E Korf Depth first iterative deepening An optimal admissible tree search 1985 Joseph C Culberson Jonathan Schaeffer Pattern Databases 1998 Richard E Korf Peter Schultze Large Scale Parallel Breadth First Search 2005 Richard E Korf Larry A Taylor Finding Optimal Solutions to the Twenty Four Puzzle 1996 Arhivirovano 10 sentyabrya 2015 goda Richard E Korf Recent Progress in the Design and Analysis of Admissible Heuristic Functions 2000 Richard E Korf Ariel Felner Disjoint Pattern Database Heuristics 2002 Arhivirovano 7 maya 2019 goda Ariel Felner Richard E Korf Sarit Hanan Additive Pattern Database Heuristics 2004 Arhivirovano 1 dekabrya 2021 goda Richard E Korf Finding Optimal Solutions to Rubik s Cube Using Pattern Databases 1997 Richard E Korf Ariel Felner Recent Progress in Heuristic Search A Case Study of the Four Peg Towers of Hanoi Problem 2007 Osnovan na Lecture Notes IDA Arhivnaya kopiya ot 22 iyunya 2012 na Wayback MachineLiteraturaStefan Edelkamp Stefan Schrodl Heuristic search theory and applications Morgan Kaufmann Publishers 2012 712 s ISBN 978 0 12 372512 7 Styuart Rassel Piter Norvig Sostavlenie dopustimyh evristicheskih funkcij Iskusstvennyj intellekt sovremennyj podhod Artificial Intelligence A Modern Approach 2 e izd M Vilyams 2006 S 170 173 1408 s ISBN 5 8459 0887 6 SsylkiImeetsya vikiuchebnik po teme Algoritm poiska A
