Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Informert søk og heuristikker, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En funksjon som anslår kostnaden for den billigste stien fra noden til et mål, regnet ut fra tilstanden alene. Vanligvis er den ikke-negativ og i et mål (heuristic function).
Best-først-søk som alltid tar ut noden med lavest og ser bort fra kostnaden hit. Som grafsøk på en endelig graf er det fullstendig, men aldri garantert kostnadsoptimalt (greedy best-first search).
Best-først-søk som tar ut noden med lavest , altså kjent kostnad hit pluss anslått rest. Med admissibel finner det en billigste sti, både som trelikt søk og som grafsøk med gjenåpning (A* search).
Kostnaden for den billigste stien fra til nærmeste mål. Den regnes baklengs fra målet, som et uniform-kostnad-søk med målet som start (true cost to goal).
En heuristikk som aldri overvurderer: for alle noder . Likhet er lov (admissible heuristic).
En heuristikk der for hver kant fra til , og i målene. En konsistent heuristikk er alltid admissibel, og blir aldri mindre langs en sti (consistent heuristic).
Området av noder med under en gitt grense. Med konsistent ekspanderer A* alle noder med , noen med og ingen med (search contour).
dominerer når for alle og begge er admissible. Med konsistente heuristikker ekspanderer A* med da aldri flere noder enn med , bortsett fra noder med (dominance).
Det opprinnelige problemet med færre begrensninger på handlingene, slik at flere trekk er lov. Den optimale kostnaden i det relakserte problemet er en admissibel og konsistent heuristikk for originalen (relaxed problem).
En tabell med den eksakte løsningskostnaden for et delproblem, for eksempel å få et utvalg brikker på plass, for hver plassering av brikkene i delproblemet. Oppslaget er en admissibel heuristikk (pattern database).
Mønsterdatabaser for delproblemer uten felles brikker, der hver database bare teller trekk med egne brikker. Da er summen av oppslagene admissibel, noe summen av vanlige mønsterdatabaser ikke er (disjoint pattern databases).
Forgreningsfaktoren et uniformt tre med dybde måtte hatt for å inneholde noder, der er antall noder A* genererte. Verdier nær 1 betyr at søket går nesten rett mot målet (effective branching factor).
A* med og . Søket ekspanderer ofte langt færre noder, og med admissibel koster stien høyst (weighted A*).
Best-først-søk som bare beholder de beste nodene i frontier og kaster resten. Det sparer minne, men er verken fullstendig eller optimalt (beam search).
Iterativ fordypning der grensen er en -verdi i stedet for en dybde. Hver iterasjon er et dybde-først-søk som kutter noder med over grensen, og neste grense er den minste som ble kuttet (iterative-deepening A*).
Best-først-søk med lineært minne som husker -verdien til det beste alternativet. Går den nåværende stien over den verdien, rulles søket tilbake, og noden som forlates, lagrer den beste -verdien i deltreet sitt (recursive best-first search).
A* med et fast minnetak. Når minnet er fullt, slettes bladet med høyest , og verdien lagres i forelderen, slik at grenen kan gjenskapes senere (simplified memory-bounded A*).
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Evalueringsfunksjonen
Prioriteten i frontier for A*: kostnaden for stien hit pluss anslått rest. Ved lik avgjør oppgavens tie-break. Vanlig feil: å bruke bare (det er grådig søk) eller å glemme at er summen av alle kantene langs stien.
Admissibilitetskravet
Sjekkes node for node mot en -tabell regnet baklengs fra målet. Likhet er lov, og ett eneste brudd gjør heuristikken inadmissibel.
Konsistenskravet
Sjekkes kant for kant, i begge retninger på en urettet graf. Det er en ulikhet, ikke en likhet. Konsistens gir admissibilitet, men ikke omvendt.
Maksimum av heuristikker
Er alle admissible, er maksimum admissibelt og dominerer hver av dem. Summen er derimot generelt ikke admissibel, unntatt for disjunkte mønsterdatabaser.
Vektet evalueringsfunksjon
Vektet A*: større gir færre ekspansjoner, men kan overvurdere. Med admissibel er kostnaden til stien som finnes, høyst ganger den optimale .
Likningen for $b^*$
Løses for den effektive forgreningsfaktoren når A* har generert noder (startnoden ikke medregnet) for en løsning på dybde . Løs med prøving eller halvering; betyr at bare nodene på løsningsstien ble generert.
Kodesnutter
Kodesnutter fra kapittelet, vist literal.
A* med én justerbar h-verdi
import heapq h_C = 4 # @param 0..10 kanter = {"S": {"A": 2, "B": 3}, "A": {"S": 2, "C": 2}, "B": {"S": 3, "C": 4, "G": 8}, "C": {"A": 2, "B": 4, "G": 4}, "G": {"B": 8, "C": 4}}h = {"S": 6, "A": 5, "B": 7, "C": h_C, "G": 0}h_stjerne = {"S": 8, "A": 6, "B": 8, "C": 4, "G": 0} # sann restkostnad, regnet baklengs fra G frontier = [(h["S"], "S", 0, ["S"])] # (f, node, g, sti): lik f gir alfabetisk nodebeste_g = {"S": 0}ekspandert = []while frontier: f, node, g, sti = heapq.heappop(frontier) if g > beste_g[node]: continue # utdatert post: en billigere sti hit er funnet etterpå if node == "G": break # måltest ved uttak ekspandert.append(node) for nabo, kost in sorted(kanter[node].items()): if g + kost < beste_g.get(nabo, 99): # ny node eller strengt billigere sti beste_g[nabo] = g + kost heapq.heappush(frontier, (g + kost + h[nabo], nabo, g + kost, sti + [nabo])) admissibel = all(h[n] <= h_stjerne[n] for n in h)konsistent = all(h[n] <= k + h[m] for n in kanter for m, k in kanter[n].items())print(f"Ekspansjonsrekkefølge: {', '.join(ekspandert)}, (G)")print(f"Funnet sti: {' → '.join(sti)}")print(f"Kostnad: {g}")print(f"Admissibel: {'ja' if admissibel else 'nei'}")print(f"Konsistent: {'ja' if konsistent else 'nei'}")Prøv: sett h_C til 1 og se at linja Konsistent: blir nei mens Kostnad: står på 8, og sett den så til 9 og se Admissibel: bli nei og Kostnad: hoppe til 11.
Effektiv forgreningsfaktor regnet ut
N = 120 # @param 5..2000d = 4 # @param 1..12 def noder(b, d): return sum(b ** i for i in range(1, d + 1)) # b + b² + … + b^d, altså uten roten if N < d: print(f"Effektiv forgreningsfaktor b*: ugyldig (A* må generere minst d = {d} noder)") print("Kontroll, noder med b*: ikke regnet")else: lav, hoy = 1.0, float(N) for _ in range(60): # halveringssøk: noder(b, d) vokser med b midt = (lav + hoy) / 2 if noder(midt, d) < N: lav = midt else: hoy = midt print(f"Effektiv forgreningsfaktor b*: {lav:.2f}") print(f"Kontroll, noder med b*: {noder(lav, d):.1f} (skal være N = {N})")Prøv: sett d til 6 og senk N mot 6, og se linja Effektiv forgreningsfaktor b*: nærme seg 1, som betyr et søk uten sidesteg.
Vektet A* for en lagerrobot
import heapq W = 1.0 # @param 1.0..3.0 0.25 lager = ["S~~~~~~G", ".######.", "...~~~..", ".######.", "........"] # . = gang (kost 1), ~ = travel sone (kost 3), # = reolstart, maal = (0, 0), (0, 7) def vektet_a_stjerne(W): h = lambda p: abs(p[0] - maal[0]) + abs(p[1] - maal[1]) # Manhattan-avstand, admissibel frontier, beste_g, ekspansjoner = [(W * h(start), start, 0)], {start: 0}, 0 while frontier: f, p, g = heapq.heappop(frontier) if g > beste_g[p]: continue # utdatert post if p == maal: return ekspansjoner, g ekspansjoner += 1 for q in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]: if 0 <= q[0] < 5 and 0 <= q[1] < 8 and lager[q[0]][q[1]] != "#": g_ny = g + (3 if lager[q[0]][q[1]] == "~" else 1) if g_ny < beste_g.get(q, 999): beste_g[q] = g_ny heapq.heappush(frontier, (g_ny + W * h(q), q, g_ny)) ekspansjoner, kostnad = vektet_a_stjerne(W)c_stjerne = vektet_a_stjerne(1.0)[1]print(f"Ekspansjoner: {ekspansjoner}")print(f"Kostnad: {kostnad}")print(f"Øvre grense W · C*: {W * c_stjerne:g}")Prøv: øk W fra 1.0 til 2.0 og se at linja Ekspansjoner: faller fra 23 til 8 mens Kostnad: stiger fra 15 til 19, men aldri over Øvre grense W · C*:.
Pseudokode
Pseudokode som forklarer fremgangsmåten steg for steg.
A* i pseudokode
a_stjerne(start, er_maal, barn, h): beste_g = {start: 0} frontier = prioritetskø ordnet på f = g + h(node) # lik f: oppgavens tie-break legg start inn i frontier med g = 0 så lenge frontier ikke er tom: node = ta ut posten med lavest f hvis er_maal(node): # måltest ved uttak returner stien til node for (neste, kost) i barn(node): # fast barnerekkefølge g_ny = beste_g[node] + kost hvis neste ikke er nådd eller g_ny < beste_g[neste]: # strengt billigere beste_g[neste] = g_ny forelder[neste] = node legg neste inn med f = g_ny + h(neste) # ligger neste i frontier, erstattes posten; # er den ekspandert, åpnes den igjen (gjenåpning) returner feilA* er best-først-søk med prioritet . Én betingelse, «strengt billigere», styrer både oppdatering i frontier og gjenåpning av ekspanderte noder.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Spor grådig best-først-søk og A* som grafsøk, og oppgi ekspansjonsrekkefølge, funnet sti og stikostnad
- 02Skriv frontier som C(8=1+2+5) med , og bruk tie-break, måltest ved uttak og oppdatering av frontier riktig
- 03Avgjør om en heuristikk er admissibel med en -tabell, og om den er konsistent kant for kant i begge retninger
- 04Forklar hvorfor A* er optimal med admissibel , og hvorfor lukket mengde uten gjenåpning krever konsistent
- 05Regn ut hvilke verdier én ukjent -verdi kan ha for at heuristikken skal være konsistent
- 06Konstruer admissible heuristikker ved relaksering, og sammenlign dem med dominans, maksimum og effektiv forgreningsfaktor
- 07Sammenlign strålesøk, IDA*, RBFS, SMA* og vektet A* når det gjelder minne, tid og garantier