Hva er forskjellen mellom A * og grådig best-first-søk?

Begge algoritmene faller inn i kategorien «best-first search» algoritmer, som er algoritmer som kan bruke både kunnskapen som er tilegnet så langt mens de utforsker søkeområdet, betegnet med $ g (n) $ , og en heuristisk funksjon, betegnet med $ h (n) $ , som estimerer avstanden til målnoden, for hver node $ n $ i søkeområdet (ofte representert som en graf).

Hver av disse søkealgoritmene definerer en «evalueringsfunksjon» for hver node $ n $ i grafen (eller søkeområdet), betegnet med $ f (n) $ . Denne evalueringsfunksjonen brukes til å bestemme hvilken node, mens du søker, «utvides» først, det vil si hvilken node som først fjernes fra «frynsen» (eller «frontier», eller «border») for å «besøke» barna sine. Generelt sett er forskjellen mellom algoritmene i kategorien «best først» i definisjonen av evalueringsfunksjonen $ f (n) $ .

Når det gjelder den grådige BFS-algoritmen , er evalueringsfunksjonen $ f (n) = h (n) $ , det vil si at den grådige BFS-algoritmen først utvider noden hvis estimerte avstand til målet er den minste. Så grådig BFS bruker ikke «tidligere kunnskap», dvs. $ g (n) $ . Derav konnotasjonen «grådig». Generelt er den grådige BST-algoritmen ikke fullstendig , det vil si at det alltid er risiko for å gå en vei som ikke bringe til målet. I den grådige BFS-algoritmen holdes alle noder på grensen (eller frynser eller grenser) i minnet, og noder som allerede er utvidet, trenger ikke å lagres i minnet og kan derfor kastes. Generelt er den grådige BFS også ikke optimal , det vil si at banen som er funnet ikke er den optimale. Generelt er tidskompleksiteten $ \ mathcal {O} (b ^ m) $ , der $ b $ er (maksimum) forgreningsfaktor og $ m $ er den maksimale dybden på søketreet. Romkompleksiteten er proporsjonal med antall noder i utkanten og med lengden på den funnet banen.

Når det gjelder A * algoritme , evalueringsfunksjonen er $ f (n) = g (n) + h (n) $ , der $ h $ er en tillatt heuristisk funksjon . «Stjernen», ofte betegnet med en stjerne, *, refererer til det faktum at A * bruker en tillatt heuristisk funksjon, som egentlig betyr at A * er optimal , det vil si at den alltid finner den optimale banen mellom startnoden og målnoden. A * er også komplett (med mindre det er uendelig mange noder å utforske i søkeområdet). Tidskompleksiteten er $ \ mathcal {O} (b ^ m) $ . Imidlertid trenger A * å holde alle noder i minnet mens du søker, ikke bare de i utkanten, fordi A * i hovedsak utfører et «uttømmende søk» (som er «informert», i den forstand at det bruker en heuristisk funksjon ).

Oppsummert er grådig BFS ikke komplett, ikke optimal, har en tidskompleksitet på $ \ mathcal {O} (b ^ m) $ og en romkompleksitet som kan være polynom. A * er komplett, optimal, og den har en tid og romkompleksitet på $ \ mathcal {O} (b ^ m) $ . Generelt bruker A * mer minne enn grådig BFS. A * blir upraktisk når søkeområdet er stort. Imidlertid garanterer A * også at den funnet banen mellom startnoden og målnoden er den optimale og at algoritmen til slutt avsluttes. Grådig BFS bruker derimot mindre minne, men gir ikke optimaliteten og fullstendighetsgarantiene til A *. Så hvilken algoritme som er den «beste», avhenger av sammenhengen, men begge er de «beste» første søkene.

Merk: i praksis kan du ikke bruke noen av disse algoritmene: du kan f.eks. bruk i stedet IDA * .

Kommentarer

• Kommentarer er ikke for utvidet diskusjon; denne samtalen er flyttet til chat .

I følge boka Artificial Intelligence: En moderne tilnærming (3. utgave), av Stuart Russel og Peter Norvig, spesielt, seksjon 3.5.1 Grådige best-først-søk (s. 92)

Grådige beste-første-søk prøver å utvide noden som er nærmest målet, med den begrunnelsen at dette vil sannsynligvis raskt føre til en løsning. Dermed evaluerer det noder ved å bruke bare den heuristiske funksjonen; det vil si $ f (n) = h (n) $ .

I dette samme seksjon gir forfatterne et eksempel som viser at grådige best-først-søk verken er optimal eller fullstendig.

I seksjon 3.5.2 A * søk: Ved å minimere den totale estimerte løsningskostnaden for samme bok (s. 93), står det

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

Siden $ g (n) $ gir banekostnaden fra startnoden til noden $ n $ , og $ h (n) $ er den estimerte kostnaden for den billigste banen fra $ n $ til målet, vi har $ f (n) $ = estimert kostnad for den billigste løsningen gjennom $ n $ .

Dermed hvis vi prøver å finne den billigste løsningen, er det en rimelig ting å prøve først noden med den laveste verdien $ g (n) + h (n) $ . Det viser seg at denne strategien er mer enn bare rimelig: forutsatt at den heuristiske funksjonen $ h (n) $ oppfyller visse betingelser, er A * -søk både komplett og optimalt. Algoritmen er identisk med uniformskostnadssøk bortsett fra at A * bruker $ g + h $ i stedet for $ g $

Det du sa er ikke helt feil, men A * -algoritmen blir optimal og fullstendig hvis den heuristiske funksjonen h er tillatt, noe som betyr at denne funksjonen aldri overvurderer kostnadene for å nå målet. I så fall er A * -algoritmen langt bedre enn den grådige søkealgoritmen. p>

Kommentarer

• kjære kan du utdype svaret ditt. beklager å si, men jeg forsto ikke poenget ditt.
• @IramShah – TemmanRafk snakker om beviset for at A * er både optimal og fullstendig. For å gjøre det vises det på grunn av ulikheten i trekanten at heuristikken som estimerer gjenværende avstand til målet ikke er en overestimering. For å se en mer fullstendig forklaring se no.wikipedia.org/wiki/Admissible_heuri stic