Informerad sökmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 29 juni 2018; kontroller kräver 3 redigeringar .

Informerad sökning (även heuristisk sökning , eng.  informed search, heuristisk sökning ) är en strategi för att hitta lösningar i det statliga rummet , som använder kunskap relaterad till en specifik uppgift. Informerade metoder ger generellt sett mer effektiva sökningar än oinformerade metoder .

Information om en specifik uppgift är formulerad som en heuristisk funktion . Den heuristiska funktionen vid varje steg i sökningen utvärderar alternativen baserat på ytterligare information för att avgöra i vilken riktning sökningen ska fortsätta [1] .

Heuristiska funktioner

I sammanhanget för tillståndsrymdsökning definieras den heuristiska funktionen h ( n ) på noderna i iterationsträdet enligt följande:  

h ( n ) = kostnadsuppskattning av den billigaste vägen från nod n till målnoden.

Om n  är målnoden, då är h ( n ) = 0.

Noden som ska distribueras väljs baserat på utvärderingsfunktionen 

f ( n ) = kostnadsuppskattning av den billigaste lösningsvägen som går genom nod n , f ( n ) = g ( n ) + h ( n ),

där funktionen g ( n ) bestämmer kostnaden för vägen som redan färdats från startnoden till noden n .

Om den heuristiska funktionen h ( n ) aldrig överskattar den faktiska minimikostnaden för att uppnå målet (det vill säga det är en lägre uppskattning av den faktiska kostnaden), så kallas en sådan funktion tillåten . 

Om den heuristiska funktionen h ( n ) uppfyller villkoret

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

där b  är en avkomling av a , då kallas en sådan funktion successiv ( engelska  konsekvent ).

Om f ( n ) = g ( n ) + h ( n ) är utvärderingsfunktionen, h ( n ) är efterföljande funktion, då är funktionen f ( n ) monotont icke-minskande längs någon väg som studeras. Därför kallas successiva funktioner även monotona ( eng.  monoton ).

Alla efterföljande funktioner är tillåtna, men inte alla tillåtna funktioner är efterföljare.

Om h 1 ( n ), h 2 ( n ) är giltiga heuristiska funktioner, och för någon nod n är olikheten h 1 ( n ) ≥ h 2 ( n ) sann, då är h 1 en mer informerad heuristik, eller dominerar h 2 .

Om problemet har tillåten heuristik h 1 och h 2 , då är heuristiken h ( n ) = max( h 1 , h 2 ) tillåten och dominerar över var och en av de ursprungliga heuristikerna [1] [2] .

Jämförelse av heuristiska funktioner

När man jämför tillåten heuristik spelar graden av medvetenhet och den rumsliga och tidsmässiga komplexiteten av att beräkna var och en av heuristikerna betydelse. Mer informerad heuristik kan minska antalet utplacerade noder, även om kostnaden för att göra det kan vara den tid det tar att beräkna heuristiken för varje nod.

Den effektiva förgreningsfaktorn är det  genomsnittliga antalet noduppföljare i uppräkningsträdet efter att ha tillämpat heuristiska beskärningsmetoder [1] [2] . Genom den effektiva förgreningsfaktorn kan man bedöma kvaliteten på den använda heuristiska funktionen.

En ideal heuristisk funktion (som en uppslagstabell ) returnerar alltid exakta värden för längden på den kortaste lösningen, så uppräkningsträdet innehåller bara optimala lösningar. Den effektiva förgreningsfaktorn för en ideal heuristisk funktion är nära 1 [1] .

Exempel på sökuppgifter

Som modeller för att testa sökalgoritmer och heuristiska funktioner används ofta permutationspussel  - Femton 3 × 3 [3] [4] , 4 × 4 [5] [6] [7] , 5 × 5 [8] [9] [ 10 ] , 6×6 [11] , Rubiks kub [9] [12] , Hanois torn med fyra spön [11] [13] .

I "Femton"-pusslet kan h m -heuristiken baserad på Manhattan-avståndet tillämpas . Mer specifikt, för varje bricka, beräknas Manhattan-avståndet mellan dess nuvarande position och dess initiala position; de erhållna värdena sammanfattas.

Det kan visas att denna heuristik är tillåten och successiv: dess värde kan inte ändras med mer än ±1 i ett drag.

Konstruktion av heuristiska funktioner

Avslappnad uppgift

Den heuristiska funktionen h m som används för att lösa "Femton"-pusslet är en lägre uppskattning av längden på den optimala lösningen. Dessutom är h m ( n ) den exakta längden på den optimala lösningen till en förenklad version av pusslet, där brickor kan flyttas till sina positioner. I det ursprungliga pusslet finns en begränsning "det ska inte finnas två eller fler brickor i en cell", vilket inte är i den förenklade versionen. Ett problem med färre restriktioner för möjliga åtgärder kallas ett avslappnat problem ; kostnaden för att lösa det avslappnade problemet är en giltig heuristik för det ursprungliga problemet [1] , eftersom varje lösning på det ursprungliga problemet också är en lösning på det avslappnade problemet.  

Deluppgift

Den tillåtna heuristiken kan baseras på kostnaden för att lösa ett delproblem av det ursprungliga problemet. Varje lösning på huvudproblemet är samtidigt en lösning på var och en av dess deluppgifter [1] .  

En deluppgift till problemet med att lösa "Femton"-pusslet kan vara uppgiften att flytta brickor 1, 2, 3 och 4 till sina platser. Kostnaden för att lösa detta delproblem är en giltig heuristik för det ursprungliga problemet.

Malldatabaser

Mönsterdatabaser [ 1] är en  typ av giltig heuristik baserad på idén om att lagra det exakta värdet av lösningskostnaden för varje möjlig instans av ett delproblem [1] [6] [12] .

Ett exempel på en mall för "Femton"-pusslet visas i figuren till höger: definitionen av deluppgiften inkluderar positionerna för de sju markerna som finns i den första kolumnen och i den första raden. Antalet konfigurationer för denna mall är . För var och en av konfigurationerna innehåller databasen det minsta antal drag som krävs för att översätta denna konfiguration till målkonfigurationen för deluppgiften som visas i figuren. Databasen är byggd med den omvända bredd-först sökmetoden [2] [6] .

Sökalgoritmer

Sök efter första bästa matchning

Bästa -först-sökning är ett tillvägagångssätt där en nod att distribuera väljs baserat på en utvärderingsfunktion f ( n ) .  Noden med lägst poäng väljs för distribution.

Sök A*

En*-sökning  är den mest välkända typen av första bästa matchning. Den använder en uppskattning f ( n ) av kostnaden för den billigaste lösningsvägen genom nod n :

f ( n ) = g ( n ) + h ( n ), där g ( n ) är kostnaden för vägen från startnoden till noden n , h ( n ) är en uppskattning av kostnaden för vägen från nod n till målet.

Om h ( n ) aldrig överskattar kostnaden för att nå målet (det vill säga är överkomligt), så är sökningen efter A* optimal.

IDA*

Algoritm A* med iterativ fördjupning A* ( IDA* ) är en tillämpning av idén om iterativ fördjupning i samband med heuristisk sökning.

Den oinformerade iterativa fördjupningsalgoritmen stoppar expansionen när sökdjupet d överskrider den aktuella djupgränsen l . Den informerade IDA* -algoritmen stoppar driftsättningen när uppskattningen f ( n ) av vägkostnaden genom den aktuella noden n överstiger den nuvarande vägkostnadsgränsen .

IDA*-algoritmen kännetecknas av minimal minnesoverhead jämfört med A* och ett relativt litet (vid ett framgångsrikt val av heuristik) antal utplacerade noder jämfört med IDDFS.

Pseudokod

[fjorton]

nod nuvarande nod g kostnad för att starta lösning rot.. nod f minimal vägkostnadsuppskattning genom nod h ( nod ) heuristisk kostnadsuppskattning för resten av vägen nod..målkostnad ( nod , succ ) vägkostnadsfunktion is_goal ( nod ) mål kontrollera funktionsefterföljare ( nod ) noddistributionsfunktion procedur ida_star ( root , kostnad (), is_goal (), h ()) bound  := h ( root ) loop t  := sök ( root , 0, bound ) om t = FOUND returnera sedan FOUND om t = ∞ returnera sedan NOT_FOUND bunden  := t end loop end procedur funktionssökning ( nod , g , bunden ) f  := g + h ( nod ) om f > bunden returnerar sedan f om is_goal ( nod ) returnerar sedan FOUND min :  = ∞ för efterföljare ( nod ) gör t :  = sök ( succ , g + kostnad ( nod , succ ), bound ) om t = FOUND returnerar sedan FOUND om t < min sedan min  := t end för retur min end funktion

MA*

SMA*

SMA  *

RBFS

Se även

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 Stuart Russell, Peter Norvig. Sammanställning av tillåtna heuristiska funktioner // Artificiell intelligens: ett modernt tillvägagångssätt = Artificial Intelligence: A Modern Approach. - 2:a uppl. - M . : Williams, 2006. - S. 170 - 173. - 1408 sid. — ISBN 5-8459-0887-6 .
  2. ↑ 1 2 3 Stefan Edelkamp, ​​​​Stefan Schrödl. Heuristisk sökning: teori och tillämpningar. - Morgan Kaufmann Publishers , 2012. - 712 sid. — ISBN 978-0-12-372512-7 .
  3. ↑ Alexander Reinfeld. Komplett lösning av åttapusslet och fördelen med nodbeställning i IDA*. — 1993.
  4. ↑ Daniel R. Kunkle. Lösning av 8-pusslet i ett minsta antal drag: En tillämpning av A*-algoritmen. – 2001.
  5. ↑ Richard E. Korf. Depth-first iterative-deepening: En optimal tillåten trädsökning. — 1985.
  6. ↑ 1 2 3 4 Joseph C. Culberson, Jonathan Schaeffer. Mönsterdatabaser. — 1998.
  7. ↑ Richard E. Korf, Peter Schultze. Storskalig parallell bredd-första sökning. — 2005.
  8. ↑ Richard E. Korf, Larry A. Taylor. Hitta optimala lösningar på tjugofyra-pusslet . — 1996.
  9. ↑ 1 2 Richard E. Korf. Nya framsteg i design och analys av tillåtna heuristiska funktioner. — 2000.
  10. ↑ Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics . – 2002.
  11. ↑ 1 2 Ariel Felner, Richard E. Korf, Sarit Hanan. Additiv mönsterdatabasheuristik . – 2004.
  12. ↑ 1 2 Richard E. Korf. Hitta optimala lösningar för Rubiks kub med hjälp av mönsterdatabaser. — 1997.
  13. ↑ Richard E. Korf, Ariel Felner. Senaste framsteg i heuristisk sökning: en fallstudie av Hanoi-problemet med fyra pinnar. – 2007.
  14. ↑ Baserat på föreläsningsanteckningar: IDA* Arkiverad 22 juni 2012 på Wayback Machine

Litteratur

  • Stefan Edelkamp, ​​Stefan Schrödl. Heuristisk sökning: teori och tillämpningar. - Morgan Kaufmann Publishers , 2012. - 712 sid. — ISBN 978-0-12-372512-7 .
  • Stuart Russell, Peter Norvig. Sammanställning av tillåtna heuristiska funktioner // Artificiell intelligens: ett modernt tillvägagångssätt = Artificial Intelligence: A Modern Approach. - 2:a uppl. - M . : Williams, 2006. - S. 170 - 173. - 1408 sid. — ISBN 5-8459-0887-6 .

Länkar

 Algoritmer för grafsökning
Oinformerade metoder
Informerade metoder
Genvägar
Minsta spännträd
Övrig