Wat zijn de verschillen tussen A * en hebzuchtige beste eerste zoekopdracht?

Beide algoritmen vallen in de categorie “best-first search” algoritmen, dit zijn algoritmen die kunnen gebruik maken van zowel de kennis die tot nu toe is opgedaan tijdens het verkennen van de zoekruimte, aangeduid met $ g (n) $ , en een heuristische functie, aangeduid met $ h (n) $ , die de afstand tot het doelknooppunt schat, voor elk knooppunt $ n $ in de zoekruimte (vaak weergegeven als een grafiek).

Elk van deze zoekalgoritmen definieert een “evaluatiefunctie”, voor elk knooppunt $ n $ in de grafiek (of zoekruimte), aangeduid met $ f (n) $ . Deze evaluatiefunctie wordt gebruikt om te bepalen welk knooppunt tijdens het zoeken eerst wordt “uitgevouwen”, dat wil zeggen welk knooppunt het eerst wordt verwijderd uit de “fringe” (of “frontier”, of “grens”) , om zijn kinderen te “bezoeken”. Over het algemeen zit het verschil tussen de algoritmen in de categorie “beste eerst” in de definitie van de evaluatiefunctie $ f (n) $ .

In het geval van het hebzuchtige BFS-algoritme , is de evaluatiefunctie $ f (n) = h (n) $ , dat wil zeggen, het hebzuchtige BFS-algoritme breidt eerst het knooppunt uit waarvan de geschatte afstand tot het doel het kleinst is. Dus, hebzuchtige BFS gebruikt niet de “kennis uit het verleden”, d.w.z. $ g (n) $ . Vandaar de connotatie “hebzuchtig”. Over het algemeen is het hebzuchtige BST-algoritme niet compleet , dat wil zeggen dat er altijd een risico bestaat om een pad te nemen dat niet naar het doel brengen. In het hebzuchtige BFS-algoritme worden alle knooppunten op de grens (of rand of grens) in het geheugen bewaard, en knooppunten die al zijn uitgebreid, hoeven niet in het geheugen te worden opgeslagen en kunnen daarom worden weggegooid. Over het algemeen is de hebzuchtige BFS ook niet optimaal , dat wil zeggen dat het gevonden pad mogelijk niet het optimale pad is. Over het algemeen is de tijdcomplexiteit $ \ mathcal {O} (b ^ m) $ , waarbij $ b $ is de (maximale) vertakkingsfactor en $ m $ is de maximale diepte van de zoekboom. De ruimtecomplexiteit is evenredig met het aantal knooppunten in de rand en met de lengte van het gevonden pad.

In het geval van de A * algoritme , de evaluatiefunctie is $ f (n) = g (n) + h (n) $ , waarbij $ h $ is een toelaatbare heuristische functie . De “ster”, vaak aangeduid met een asterisk, *, verwijst naar het feit dat A * een toegestane heuristische functie gebruikt, wat in wezen betekent dat A * optimaal , dat wil zeggen dat het altijd het optimale pad vindt tussen het startknooppunt en het doelknooppunt. A * is ook compleet (tenzij er oneindig veel knooppunten zijn om te verkennen in de zoekruimte). De tijdcomplexiteit is $ \ mathcal {O} (b ^ m) $ . A * moet echter alle knooppunten in het geheugen bewaren tijdens het zoeken, niet alleen de knooppunten in de rand, omdat A * in wezen een uitputtende zoekopdracht uitvoert (wat geïnformeerd is, in de zin dat het een heuristische functie gebruikt). ).

Samengevat, hebzuchtige BFS is niet compleet, niet optimaal, heeft een tijdcomplexiteit van $ \ mathcal {O} (b ^ m) $ en een ruimtecomplexiteit die polynoom kan zijn. A * is compleet, optimaal en heeft een tijd- en ruimtecomplexiteit van $ \ mathcal {O} (b ^ m) $ . Over het algemeen gebruikt A * dus meer geheugen dan hebzuchtige BFS. A * wordt onpraktisch wanneer de zoekruimte enorm is. A * garandeert echter ook dat het gevonden pad tussen het startknooppunt en het doelknooppunt het optimale is en dat het algoritme uiteindelijk eindigt. Greedy BFS daarentegen gebruikt minder geheugen, maar biedt niet de optimaliteit en volledigheidsgaranties van A *. Dus, welk algoritme het “beste” is, hangt af van de context, maar beide zijn “beste” eerste zoekopdrachten.

Let op: in de praktijk mag u geen van deze algoritmen gebruiken: u kunt bijvoorbeeld gebruik in plaats daarvan IDA * .

Reacties

• Reacties zijn niet voor uitgebreide discussie; dit gesprek is verplaatst om te chatten .

Volgens het boek Kunstmatige intelligentie: A Modern Approach (3e editie), door Stuart Russel en Peter Norvig, in het bijzonder sectie 3.5.1 Hebzuchtige best-first zoekopdracht (p. 92)

Greedy best-first zoektocht probeert het knooppunt uit te breiden dat het dichtst bij het doel ligt, omdat dit leidt waarschijnlijk snel tot een oplossing. Het evalueert dus knooppunten door alleen de heuristische functie te gebruiken; dat wil zeggen, $ f (n) = h (n) $ .

In deze dezelfde sectie geven de auteurs een voorbeeld waaruit blijkt dat hebzuchtige beste-eerst-zoekopdracht niet optimaal noch volledig is.

In sectie 3.5.2 Een * zoekopdracht: Door de totale geschatte oplossingskosten van hetzelfde boek (p. 93) te minimaliseren, staat

A * zoeken evalueert knooppunten door $ g (n) $ , de kosten om het knooppunt te bereiken, en $ h (n) $ , de kosten om van het knooppunt naar het doel te komen $$ f (n) = g (n) + h (n). $$

Aangezien $ g (n) $ de padkosten geeft van het startknooppunt naar het knooppunt $ n $ , en $ h (n) $ zijn de geschatte kosten van het goedkoopste pad vanaf $ n $ naar het doel, we hebben $ f (n) $ = geschatte kosten van de goedkoopste oplossing via $ n $ .

Dus als we proberen de goedkoopste oplossing te vinden, is het redelijk om eerst te proberen het knooppunt met de laagste waarde van $ g (n) + h (n) $ . Het blijkt dat deze strategie meer dan redelijk is: op voorwaarde dat de heuristische functie $ h (n) $ aan bepaalde voorwaarden voldoet, is A * zoeken zowel volledig als optimaal. Het algoritme is identiek aan zoeken met uniforme kosten, behalve dat A * $ g + h $ gebruikt in plaats van $ g $

Wat je zei is niet helemaal verkeerd, maar het A * -algoritme wordt optimaal en compleet als de heuristische functie h toelaatbaar is, wat betekent dat deze functie nooit de kosten van het bereiken van het doel overschat. In dat geval is het A * -algoritme veel beter dan het hebzuchtige zoekalgoritme.

Reacties

• Beste, kun je je antwoord nader toelichten. Sorry om te zeggen, maar ik snapte je punt niet.
• @IramShah – TemmanRafk heeft het over het bewijs dat A * zowel optimaal als compleet is. Om dit te doen, wordt vanwege de driehoeksongelijkheid aangetoond dat de heuristiek die de resterende afstand tot het doel schat, geen overschatting is. Voor een vollediger uitleg zie en.wikipedia.org/wiki/Admibly_heuri stic