Vilka är skillnaderna mellan A * och giriga bästa-först-sökning?

Båda algoritmerna faller i kategorin ”bäst-först-sökning” algoritmer, som är algoritmer som kan använda både den kunskap som hittills förvärvats när man utforskar sökutrymmet, betecknad med $ g (n) $ , och en heuristisk funktion, betecknad med $ h (n) $ , som uppskattar avståndet till målnoden, för varje nod $ n $ i sökutrymmet (ofta representerat som ett diagram).

Var och en av dessa sökalgoritmer definierar en ”utvärderingsfunktion” för varje nod $ n $ i grafen (eller sökutrymmet), betecknad med $ f (n) $ . Denna utvärderingsfunktion används för att bestämma vilken nod, medan du söker, först ”utvidgas”, det vill säga vilken nod som först tas bort från ”frans” (eller ”frontier”, eller ”gräns”) för att ”besöka” sina barn. Generellt sett är skillnaden mellan algoritmerna i kategorin ”bäst först” i definitionen av utvärderingsfunktionen $ f (n) $ .

När det gäller den giriga BFS-algoritmen är utvärderingsfunktionen $ f (n) = h (n) $ , det vill säga den giriga BFS-algoritmen först expanderar noden vars uppskattade avstånd till målet är det minsta. Så giriga BFS använder inte ”tidigare kunskap”, dvs. $ g (n) $ . Därav dess konnotation ”girig”. I allmänhet är den giriga BST-algoritmen inte komplett , det vill säga det finns alltid risk att ta en väg som inte ta till målet. I den giriga BFS-algoritmen hålls alla noder på gränsen (eller fransar eller gränser) i minnet och noder som redan har utökats behöver inte lagras i minnet och kan därför kasseras. I allmänhet är den giriga BFS också inte optimal , det vill säga att den hittade sökvägen kanske inte är den optimala. I allmänhet är tidskomplexiteten $ \ mathcal {O} (b ^ m) $ , där $ b $ är (maximal) förgreningsfaktor och $ m $ är sökträdets maximala djup. Utrymmets komplexitet är proportionell mot antalet noder i utkanten och längden på den hittade banan.

I fallet med A * algoritm , utvärderingsfunktionen är $ f (n) = g (n) + h (n) $ , där $ h $ är en tillåten heuristisk funktion . ”Stjärnan”, ofta betecknad med en asterisk, *, hänvisar till det faktum att A * använder en tillåten heuristisk funktion, vilket i huvudsak betyder att A * är optimal , det vill säga den hittar alltid den optimala vägen mellan startnoden och målnoden. A * är också komplett (såvida det inte finns oändligt många noder att utforska i sökutrymmet). Tidskomplexiteten är $ \ mathcal {O} (b ^ m) $ . A * behöver dock hålla alla noder i minnet medan de söker, inte bara de i utkanten, eftersom A * i huvudsak utför en ”uttömmande sökning” (som är ”informerad”, i den meningen att den använder en heuristisk funktion ).

Sammanfattningsvis är girig BFS inte komplett, inte optimal, har en tidskomplexitet på $ \ mathcal {O} (b ^ m) $ och en rymdkomplexitet som kan vara polynom. A * är komplett, optimal och har en tids- och rymdkomplexitet på $ \ mathcal {O} (b ^ m) $ . Så generellt använder A * mer minne än giriga BFS. A * blir opraktiskt när sökutrymmet är enormt. Men A * garanterar också att den hittade sökvägen mellan startnoden och målnoden är den optimala och att algoritmen så småningom avslutas. Grådiga BFS, å andra sidan, använder mindre minne, men ger inte optimala och fullständiga garantier för A *. Så vilken algoritm som är ”bäst” beror på sammanhanget, men båda är ”bäst” -första sökningar.

Obs! I praktiken får du inte använda någon av dessa algoritmer: du kan t.ex. använd istället IDA * .

Kommentarer

• Kommentarer är inte för utökad diskussion; den här konversationen har flyttats till chatt .

Enligt boken Artificiell intelligens: A Modern Approach (3: e upplagan), av Stuart Russel och Peter Norvig, särskilt avsnitt 3.5.1 Girigaste bästa första sökningen (s. 92)

Grådig bästa första sökning försöker utvidga den nod som är närmast målet, med motiveringen att detta leder sannolikt snabbt till en lösning. Således utvärderar den noder genom att bara använda heuristiska funktionen; det vill säga $ f (n) = h (n) $ .

I detta samma avsnitt ger författarna ett exempel som visar att girig bästa-först-sökning varken är optimal eller komplett.

I avsnitt 3.5.2 A * -sökning: Minimerar den totala uppskattade lösningskostnaden för samma bok (s. 93), det står

A * sökning utvärderar noder genom att kombinera $ g (n) $ , kostnaden för att nå noden och $ h (n) $ , kostnaden för att komma från noden till målet $$ f (n) = g (n) + h (n). $$

Eftersom $ g (n) $ ger sökvägen kostnad från startnoden till noden $ n $ och $ h (n) $ är den beräknade kostnaden för den billigaste sökvägen från $ n $ till målet, vi har $ f (n) $ = beräknad kostnad för den billigaste lösningen genom $ n $ .

Således om vi försöker hitta den billigaste lösningen är en rimlig sak att försöka först noden med det lägsta värdet på $ g (n) + h (n) $ . Det visar sig att denna strategi är mer än bara rimlig: förutsatt att den heuristiska funktionen $ h (n) $ uppfyller vissa villkor är A * -sökningen både komplett och optimal. Algoritmen är identisk med sökning med enhetlig kostnad förutom att A * använder $ g + h $ istället för $ g $

Vad du sa är inte helt fel, men A * -algoritmen blir optimal och fullständig om den heuristiska funktionen h är tillåten, vilket innebär att den här funktionen aldrig överskattar kostnaden för att nå målet. I så fall är A * -algoritmen mycket bättre än den giriga sökalgoritmen. p>

Kommentarer

• kära kan du utarbeta ditt svar. ledsen att säga men jag fick inte din poäng.
• @IramShah – TemmanRafk talar om beviset för att A * är både optimal och fullständig. För att göra det visas på grund av olikheten i triangeln att heuristiken som uppskattar det återstående avståndet till målet inte är en överskattning. = ”ff5d70bb76″>