När som helst A*

Inom datavetenskap är när som helst A* en familj av varianter av A*-sökalgoritmen . Liksom andra när som helst algoritmer har den en flexibel tidskostnad, den kan returnera en giltig lösning till ett sökvägs- eller grafkorsningsproblem även om det avbryts innan det tar slut, genom att generera en snabb, icke-optimal lösning innan den successivt optimeras. Denna förmåga att snabbt generera lösningar har gjort det attraktivt för sökbaserade webbplatser och AI -designer.

Bakgrund och historia

Att köra den optimala A*-algoritmen till slut är för dyrt för många ändamål. A*:s optimalitet kan offras för att minska exekveringstiden genom att blåsa upp heuristiken, som i viktad A* från 1970. Att iterativt minska graden av heuristiken är "uppblåst" ger en naiv när som helst algoritm (ATA*, ​​2002). men detta upprepar tidigare arbete. En mer effektiv och felbegränsad version som återanvänder resultat, Anytime Repairing A* ( ARA* ), rapporterades 2003. En dynamisk (i betydelsen D* ) modifiering av ARA*, Anytime Dynamic A* ( ADA* ) var publicerad 2005. Den kombinerar aspekter av D* Lite och ARA*. Anytime Weighted A* (1997, 2007) liknar viktat A*, förutom att den fortsätter sökningen efter att ha hittat den första lösningen. Den hittar bättre lösningar iterativt och hittar i slutändan den optimala lösningen utan att upprepa tidigare arbete och ger även felgränser under hela sökningen. Randomized Weighted A* (2021) introducerade randomisering i Anytime Weighted A* och visade bättre empirisk prestanda.

Skillnad från A*

Viktad A*-sökning som använder en heuristik som är w = 5,0 gånger en konsekvent heuristik och erhåller en suboptimal väg.

En* sökalgoritm kan presenteras av funktionen f( n ) = g( n ) + h( n ) , där n är den sista noden på vägen, g( n ) är kostnaden för vägen från startnoden till n , och h( n ) är en heuristik som uppskattar kostnaden för den billigaste vägen från n till målet. Till skillnad från A*-algoritmen är den viktigaste funktionen hos Anytime A*-algoritmen att de kan stoppas och sedan kan startas om när som helst. När som helst A*-familj av algoritmer bygger vanligtvis på den viktade versionen av A*-sökningen: där man använder f w ( n ) = g( n ) + w × h( n ) , w > 1 , och utför A*-sökningen som vanlig, vilket så småningom sker snabbare eftersom färre noder expanderas.

ATA* innebär att köra viktat A* flera gånger med w gradvis sänkande varje gång tills w =1 när sökningen bara blir vanlig A*. Även om detta skulle kunna fungera genom att anropa A* upprepade gånger och kassera allt tidigare minne, gör ARA* detta genom att introducera ett sätt att uppdatera sökvägen. Initialvärdet för w bestämmer den minimala (första gången) körtiden för ATA*.

När som helst viktad A* förvandlar viktad A* till en när som helst algoritm enligt följande. Varje måltest görs vid nodgenerering istället för nodexpansion, och den nuvarande lösningen blir den bästa målnoden hittills. Om inte algoritmen avbryts fortsätter sökningen tills den optimala lösningen hittas. Under sökningen är felgränsen kostnaden för den aktuella lösningen c minus det minsta f-värdet i den öppna listan. Den optimala lösningen detekteras när inga fler noder med f( n ) ≤ c förblir öppna, och vid den tidpunkten avslutas algoritmen med c som kostnaden för optimal lösning. År 2021 upptäcktes att givet en tidsgräns för sökning, ger Anytime-viktad A* bättre lösningar i genomsnitt genom att helt enkelt byta vikten slumpmässigt efter varje nodexpansion än genom att använda en finjusterad statisk vikt eller genom att gradvis sänka vikten efter varje lösning.