Hvad er forskellen mellem A * og grådig bedste-første søgning?

Begge algoritmer falder i kategorien “bedst-første søgning” algoritmer, som er algoritmer, som kan bruge både den hidtidige viden, der er erhvervet, mens de udforsker søgerummet, betegnet med $ g (n) $ , og en heuristisk funktion, betegnet med $ h (n) $ , som estimerer afstanden til målnoden for hver node $ n $ i søgerummet (ofte repræsenteret som en graf).

Hver af disse søgealgoritmer definerer en “evalueringsfunktion” for hver node $ n $ i grafen (eller søgerummet) betegnet med $ f (n) $ . Denne evalueringsfunktion bruges til at bestemme, hvilken node der under søgning først “udvides”, dvs. hvilken node først fjernes fra “frynser” (eller “frontier”, eller “grænse”) for at “besøge” sine børn. Generelt er forskellen mellem algoritmerne i kategorien “bedst først” i definitionen af evalueringsfunktionen $ f (n) $ .

I tilfælde af den grådige BFS-algoritme er evalueringsfunktionen $ f (n) = h (n) $ , det vil sige, at den grådige BFS-algoritme først udvider noden, hvis estimerede afstand til målet er den mindste. Så grådig BFS bruger ikke “tidligere viden”, dvs. $ g (n) $ . Derfor er dens konnotation “grådig”. Generelt er den grådige BST-algoritme ikke komplet , det vil sige, der er altid risiko for at tage en sti, der ikke bringe til målet. I den grådige BFS-algoritme holdes alle noder på grænsen (eller frynser eller grænser) i hukommelsen, og noder, der allerede er udvidet, behøver ikke at blive gemt i hukommelsen og kan derfor kasseres. Generelt er den grådige BFS også ikke optimal , det vil sige at den fundne vej muligvis ikke er den optimale. Generelt er tidskompleksiteten $ \ mathcal {O} (b ^ m) $ , hvor $ b $ er (maksimum) forgreningsfaktor, og $ m $ er søgetræets maksimale dybde. Rumkompleksiteten er proportional med antallet af noder i kanten og med længden af den fundne sti.

I tilfælde af A * algoritme , evalueringsfunktionen er $ f (n) = g (n) + h (n) $ , hvor $ h $ er en tilladelig heuristisk funktion . “Stjernen”, ofte betegnet med en stjerne, *, henviser til det faktum, at A * bruger en tilladelig heuristisk funktion, som i det væsentlige betyder, at A * er optimal , det vil sige, den finder altid den optimale sti mellem startknudepunktet og målknudepunktet. A * er også komplet (medmindre der er uendeligt mange noder at udforske i søgerummet). Tidskompleksiteten er $ \ mathcal {O} (b ^ m) $ . A * har imidlertid brug for at holde alle noder i hukommelsen under søgning, ikke kun dem i udkanten, fordi A * i det væsentlige udfører en “udtømmende søgning” (som er “informeret” i den forstand, at den bruger en heuristisk funktion ).

Sammenfattende er grådig BFS ikke komplet, ikke optimal, har en tidskompleksitet på $ \ mathcal {O} (b ^ m) $ og en rumkompleksitet, som kan være polynomisk. A * er komplet, optimal, og den har en tid og rumskompleksitet på $ \ mathcal {O} (b ^ m) $ . Så generelt bruger A * mere hukommelse end grådig BFS. A * bliver upraktisk, når søgerummet er stort. Imidlertid garanterer A * også, at den fundne sti mellem startknudepunktet og målknudepunktet er den optimale, og at algoritmen til sidst afsluttes. Grådig BFS bruger derimod mindre hukommelse, men giver ikke A *s optimale og fuldstændige garantier. Så hvilken algoritme der er den “bedste” afhænger af sammenhængen, men begge er de “bedste” første søgninger.

Bemærk: I praksis må du ikke bruge nogen af disse algoritmer: du kan f.eks. brug i stedet IDA * .

Kommentarer

• Kommentarer er ikke til udvidet diskussion; denne samtale er flyttet til chat .

Ifølge bogen Kunstig intelligens: A Modern Approach (3. udgave) af Stuart Russel og Peter Norvig, specifikt afsnit 3.5.1 Grådige bedste-første søgning (s. 92)

Grådig bedst-første søgning forsøger at udvide den knude, der er tættest på målet, med den begrundelse at dette vil sandsynligvis hurtigt føre til en løsning. Således evaluerer det noder ved kun at bruge den heuristiske funktion; det vil sige $ f (n) = h (n) $ .

I dette samme afsnit giver forfatterne et eksempel, der viser, at grådig bedste først-søgning hverken er optimal eller komplet.

I afsnit 3.5.2 A * søgning: Minimering af de samlede anslåede løsningsomkostninger for den samme bog (s. 93) angiver det

A * søgning evaluerer noder ved at kombinere $ g (n) $ , omkostningerne ved at nå noden og $ h (n) $ , omkostningerne ved at komme fra noden til målet $$ f (n) = g (n) + h (n). $$

Da $ g (n) $ giver stiomkostningerne fra startnoden til noden $ n $ og $ h (n) $ er de anslåede omkostninger ved den billigste vej fra $ n $ til målet, vi har $ f (n) $ = anslåede omkostninger ved den billigste løsning gennem $ n $ .

Således hvis vi prøver at finde den billigste løsning, er en rimelig ting at prøve først noden med den laveste værdi på $ g (n) + h (n) $ . Det viser sig, at denne strategi er mere end bare rimelig: forudsat at den heuristiske funktion $ h (n) $ opfylder visse betingelser, er A * -søgning både komplet og optimal. Algoritmen er identisk med ensartet søgning med undtagelse af, at A * bruger $ g + h $ i stedet for $ g $

Hvad du sagde er ikke helt forkert, men A * algoritmen bliver optimal og komplet, hvis den heuristiske funktion h er tilladt, hvilket betyder, at denne funktion aldrig overvurderer omkostningerne ved at nå målet. I så fald er A * algoritmen langt bedre end den grådige søgealgoritme. p>

Kommentarer

• kære kan du uddybe dit svar. ked af at sige, men jeg fik ikke din mening.
• @IramShah – TemmanRafk taler om beviset for, at A * er både optimal og komplet. For at gøre det vises det på grund af trekantens ulighed, at heuristikken, der estimerer den resterende afstand til målet, ikke er en overestimering. For at se en mere detaljeret forklaring se da.wikipedia.org/wiki/Admissible_heuri stic