Metoda de căutare informată

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 29 iunie 2018; verificările necesită 3 modificări .

Căutarea informată (de asemenea căutarea euristică , ing.  căutarea informată, căutarea euristică ) este o strategie de găsire a soluțiilor în spațiul de stat , care utilizează cunoștințele legate de o anumită sarcină. Metodele informate oferă în general căutări mai eficiente decât metodele neinformate .

Informațiile despre o anumită sarcină sunt formulate ca o funcție euristică . Funcția euristică la fiecare pas al căutării evaluează alternativele pe baza unor informații suplimentare pentru a decide în ce direcție să continue căutarea [1] .

Funcții euristice

În contextul căutării în spațiul de stare, funcția euristică h ( n ) este definită pe nodurile arborelui de iterație după cum urmează:  

h ( n ) = estimarea costului căii cel mai puțin costisitoare de la nodul n la nodul țintă.

Dacă n  este nodul țintă, atunci h ( n ) = 0.

Nodul care urmează să fie implementat este selectat pe baza funcției de evaluare 

f ( n ) = estimarea costului căii soluției cel mai puțin costisitoare care trece prin nodul n , f ( n ) = g ( n ) + h ( n ),

unde funcţia g ( n ) determină costul drumului deja parcurs de la nodul de plecare la nodul n .

Dacă funcția euristică h ( n ) nu supraestimează niciodată costul minim real al atingerii scopului (adică este o estimare mai mică a costului real), atunci o astfel de funcție se numește admisibilă . 

Dacă funcţia euristică h ( n ) satisface condiţia

h ( a ) ≤ cost ( a , b ) + h ( b ),

unde b  este un descendent al lui a , atunci o astfel de funcție se numește succesivă ( consistentă în engleză  ).

Dacă f ( n ) = g ( n ) + h ( n ) este funcția de evaluare, h ( n ) este funcția succesoare, atunci funcția f ( n ) este monoton nedescrescătoare pe orice cale studiată. Prin urmare, funcțiile succesive sunt numite și monotone ( ing.  monotone ).

Orice funcție succesoare este admisibilă, dar nu orice funcție admisibilă este succesor.

Dacă h 1 ( n ), h 2 ( n ) sunt funcții euristice valide, iar pentru orice nod n inegalitatea h 1 ( n ) ≥ h 2 ( n ) este adevărată, atunci h 1 este o euristică mai informată sau domină h 2 .

Dacă problema are euristicile admisibile h 1 și h 2 , atunci euristica h ( n ) = max( h 1 , h 2 ) este admisibilă și domină peste fiecare dintre euristicile originale [1] [2] .

Comparația funcțiilor euristice

Când se compară euristicile admisibile, contează gradul de conștientizare și complexitatea spațială și temporală a calculării fiecărei euristici. Euristice mai informate pot reduce numărul de noduri implementate, deși costul de a face acest lucru poate fi timpul necesar pentru a calcula euristica pentru fiecare nod.

Factorul de ramificare efectivă este numărul  mediu de succesori ai nodurilor din arborele de enumerare după aplicarea metodelor de tăiere euristică [1] [2] . După factorul de ramificare efectivă, se poate aprecia calitatea funcției euristice utilizate.

O funcție euristică ideală (cum ar fi un tabel de căutare ) returnează întotdeauna valori exacte pentru lungimea celei mai scurte soluții, astfel încât arborele de enumerare conține doar soluții optime. Factorul de ramificare efectiv al unei funcții euristice ideale este aproape de 1 [1] .

Exemple de sarcini de căutare

Ca modele pentru testarea algoritmilor de căutare și a funcțiilor euristice, puzzle-urile de permutare sunt adesea folosite  - Cincisprezece 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [ 10 ] , 6×6 [11] , Cubul lui Rubik [9] [12] , Turnul din Hanoi cu patru tije [11] [13] .

În puzzle-ul „Fifteen”, se poate aplica euristica hm bazată pe distanța Manhattan . Mai precis, pentru fiecare țiglă, se calculează distanța Manhattan dintre poziția sa actuală și poziția inițială; valorile obținute sunt rezumate.

Se poate arăta că această euristică este admisibilă și succesivă: valoarea ei nu se poate modifica cu mai mult de ±1 într-o singură mișcare.

Construirea funcțiilor euristice

Sarcină relaxată

Funcția euristică h m folosită pentru a rezolva puzzle-ul „Cincisprezece” este o estimare mai mică a lungimii soluției optime. În plus, h m ( n ) este lungimea exactă a soluției optime pentru o versiune simplificată a puzzle-ului, în care plăcile pot fi mutate în pozițiile lor. În puzzle-ul original există o restricție „nu ar trebui să existe două sau mai multe plăci într-o singură celulă”, care nu este în versiunea simplificată. O problemă cu mai puține restricții asupra acțiunilor posibile se numește o problemă relaxată ; costul rezolvării problemei relaxate este o euristică validă pentru problema inițială [1] , deoarece orice soluție a problemei inițiale este și o soluție a problemei relaxate.  

Subsarcină

Euristica admisibilă se poate baza pe costul rezolvării unei subprobleme a problemei inițiale . Orice soluție la problema principală este simultan o soluție pentru fiecare dintre sarcinile sale secundare [1] .  

O subsarcină a problemei de rezolvare a puzzle-ului „Cincisprezece” poate fi sarcina de a muta piesele 1, 2, 3 și 4 în locurile lor. Costul rezolvării acestei subprobleme este o euristică validă pentru problema originală.

Baze de date șabloane

Bazele de date cu modele [ 1] sunt un  tip de euristică validă bazată pe ideea de stocare a valorii exacte a costului soluției pentru fiecare instanță posibilă a unei subprobleme [1] [6] [12] .

Un exemplu de șablon pentru puzzle-ul „Fifteen” este prezentat în figura din dreapta: definiția unei subsarcini include pozițiile celor șapte jetoane situate în prima coloană și în primul rând. Numărul de configurații pentru acest șablon este . Pentru fiecare dintre configurații, baza de date conține numărul minim de mișcări necesare pentru a traduce această configurație în configurația țintă a subsarcinii prezentate în figură. Baza de date este construită folosind metoda de căutare inversă lățimea întâi [2] [6] .

Algoritmi de căutare

Căutați după cea mai bună potrivire

Best - first search este o abordare în care un nod de implementat este selectat pe baza unei funcții de evaluare f ( n ) .  Nodul cu cel mai mic scor este selectat pentru implementare.

Caută A*

Căutarea A*  este cel mai cunoscut tip de căutare a primei cele mai bune potriviri. Utilizează o estimare f ( n ) a costului căii soluției cel mai puțin costisitoare prin nodul n :

f ( n ) = g ( n ) + h ( n ), unde g ( n ) este costul căii de la nodul de pornire la nodul n , h ( n ) este o estimare a costului căii de la nodul n la obiectiv.

Dacă h ( n ) nu supraestimează niciodată costul atingerii scopului (adică este accesibil), atunci căutarea A* este optimă.

IDA*

Algoritmul A* cu aprofundare iterativă A* ( IDA* ) este o aplicare a ideii de aprofundare iterativă în contextul căutării euristice.

Algoritmul de adâncire iterativă neinformată oprește expansiunea atunci când adâncimea de căutare d depășește limita curentă de adâncime l . Algoritmul informat IDA* oprește implementarea atunci când estimarea f ( n ) a costului căii prin nodul curent n depășește limita curentă a costului căii .

Algoritmul IDA* se caracterizează printr-o supraîncărcare minimă de memorie în comparație cu A* și un număr relativ mic (în cazul unei alegeri de succes a euristicii) de noduri implementate în comparație cu IDDFS.

Pseudocod

[paisprezece]

nodul curent nodul g costul de pornire a soluției root..node f estimarea costului minim al căii prin nodul h ( nodul ) estimarea costului euristic pentru restul căii nod..goal cost ( nod , succ ) calea cost function is_goal ( nod ) obiectiv funcția de verificare succesorii ( nod ) funcția de implementare a nodului procedura ida_star ( rădăcină , cost (), is_goal (), h ()) bound  := h ( rădăcină ) buclă t  := căutare ( rădăcină , 0, bound ) dacă t = GĂSIT , atunci returnează GĂSIT dacă t = ∞ apoi returnează NOT_FOUND bound  := t procedura de încheiere a buclei funcția căutare ( nod , g , legat ) f  := g + h ( nod ) dacă f > legat atunci returnează f dacă is_goal ( nod ) apoi returnează FOUND min  := ∞ pentru succes în succesori ( nod ) do t  := căutare ( succ , g + cost ( nod , succ ), legat ) dacă t = GĂSIT , atunci returnează GĂSIT dacă t < min , atunci min  := t final pentru funcția de returnare min end

MA*

SMA*

SMA  *

RBFS

Vezi și

Note

  1. ↑ 1 2 3 4 5 6 7 8 Stuart Russell, Peter Norvig. Compilation of admissible euristic functions // Inteligența artificială: o abordare modernă = Artificial Intelligence: A Modern Approach. - Ed. a II-a - M . : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .
  2. ↑ 1 2 3 Stefan Edelkamp, ​​​​Stefan Schrödl. Căutare euristică: teorie și aplicații. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
  3. ↑ Alexander Reinfeld. Soluția completă a opt-puzzle-ului și beneficiul ordonării nodurilor în IDA*. — 1993.
  4. ↑ Daniel R. Kunkle. Rezolvarea celor 8 puzzle într-un număr minim de mișcări: o aplicare a algoritmului A*. — 2001.
  5. ↑ Richard E. Korf. Aprofundarea iterativă în primul rând: O căutare optimă admisibilă în arbore. — 1985.
  6. ↑ 1 2 3 4 Joseph C. Culberson, Jonathan Schaeffer. Baze de date de modele. — 1998.
  7. ↑ Richard E. Korf, Peter Schultze. Căutare pe lățime paralelă la scară largă. — 2005.
  8. ↑ Richard E. Korf, Larry A. Taylor. Găsirea soluțiilor optime pentru puzzle-ul celor douăzeci și patru . — 1996.
  9. ↑ 1 2 Richard E. Korf. Progrese recente în proiectarea și analiza funcțiilor euristice admisibile. — 2000.
  10. ↑ Richard E. Korf, Ariel Felner. Euristică a bazei de date cu modele disjunse . — 2002.
  11. ↑ 1 2 Ariel Felner, Richard E. Korf, Sarit Hanan. Euristica bazei de date cu modele aditive . — 2004.
  12. ↑ 1 2 Richard E. Korf. Găsirea soluțiilor optime pentru Cubul Rubik folosind baze de date cu modele. — 1997.
  13. ↑ Richard E. Korf, Ariel Felner. Progrese recente în căutarea euristică: un studiu de caz al problemei turnurilor cu patru chei din Hanoi. — 2007.
  14. ↑ Pe baza notelor de curs: IDA* Arhivat 22 iunie 2012 la Wayback Machine

Literatură

  • Stefan Edelkamp, ​​​​Stefan Schrödl. Căutare euristică: teorie și aplicații. - Morgan Kaufmann Publishers , 2012. - 712 p. — ISBN 978-0-12-372512-7 .
  • Stuart Russell, Peter Norvig. Compilation of admissible euristic functions // Inteligența artificială: o abordare modernă = Artificial Intelligence: A Modern Approach. - Ed. a II-a - M . : Williams, 2006. - S. 170 - 173. - 1408 p. — ISBN 5-8459-0887-6 .

Link -uri

 Algoritmi de căutare grafică
Metode neinformate
Metode informate
Comenzi rapide
Arborele de întindere minim
Alte