Introduksjon til kunstig intelligens Hjem

CMD + K

Introduksjon til kunstig intelligensTDT4136

CMD + K

Introduksjon til kunstig intelligensKapittel 3Informert søk og heuristikker

17 min lesing

Informert søk og heuristikker

En heuristikk anslår hvor langt det er igjen til målet, slik at søket kan prioritere de lovende tilstandene. Spor grådig best-først-søk og A*, avgjør om en heuristikk er admissibel eller konsistent, og se hvorfor det bestemmer om A* finner den billigste løsningen. Til slutt lager du heuristikker fra relakserte problemer og møter minnebegrensede varianter som IDA*.

Læringsmål

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 $f = g + h$ , og bruk tie-break, måltest ved uttak og oppdatering av frontier riktig
03Avgjør om en heuristikk er admissibel med en $h^{*}$ -tabell, og om den er konsistent kant for kant i begge retninger
04Forklar hvorfor A* er optimal med admissibel $h$ , og hvorfor lukket mengde uten gjenåpning krever konsistent $h$
05Regn ut hvilke verdier én ukjent $h$ -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

0 av 18 aktiviteter

Kjerneidé

Uinformert søk leter like grundig i alle retninger. En heuristikk er et billig anslag på hvor langt det er igjen, og den lar søket prioritere noder som ser lovende ut. Tenk på å gå i en ukjent by med kirketårnet som eneste landemerke: du vet ikke hvilke gater som fører fram, men du vet omtrent hvor tårnet står. Grådig søk går rett mot tårnet uansett hvor lang veien har blitt, mens A* regner med både veien du har gått og avstanden som er igjen.

Steg 1 av 7

Heuristikker og grådig best-først-søk

Konsept

Uniform-kostnad-søket fra kapittel 2 tar ut noder i rekkefølge etter stikostnaden $g (n)$ . Det finner den billigste stien, men det er blindt: en node rett bak start i feil retning får like mye oppmerksomhet som en node på vei mot målet. Informert søk (informed search) bruker kunnskap om problemet i form av en heuristikk (heuristic function) $h (n)$ , et anslag på kostnaden for den billigste stien fra $n$ til et mål. På et kart kan $h$ være luftlinjen til målet, i et puslespill antall brikker som står feil. Vanligvis krever vi to ting: $h (n) \geq 0$ , og $h = 0$ i et mål.

Den enkleste bruken er grådig best-først-søk (greedy best-first search). Frontier er en prioritetskø ordnet på $h (n)$ alene, så søket tar alltid ut noden som ser nærmest målet ut, og bryr seg ikke om hva det har kostet å komme dit. Ellers er det som uniform-kostnad-søk: barna genereres, nådd-mengden holder styr på tilstandene som er sett, og måltesten skjer når en node tas ut.

Interaktiv figur

I turområdet under ligger utsiktspunktet C nær toppen G i luftlinje, så $h$ er lav der. Stien derfra går likevel i lange sløyfer opp den bratte lia.

Prøv: trykk Neste trinn til G tas ut og noter kostnaden, bytt så til UCS og sammenlign både kostnaden og antall ekspansjoner.

Trinn 1 av 5 · VelgFrontier inneholder bare startnoden S, så S tas ut.

Ekspandert0Frontier1

Algoritme

Variant

Flere valg

Måltest

Likhet

Gjenåpning

Forklar hvert trinn

Vis utregning

Steg	Tatt ut	Frontier etter
0	–	S(8)

Laster figur …

Figur 3.1Grådig søk i et turområde. Gangtid i minutter på stiene og h ved nodene; grafsøk, lik h avgjøres alfabetisk, og målet testes ved uttak.

Interaktiv

Konsept

Peker heuristikken rett vei, er grådig søk svært raskt. Men $h$ er bare et anslag, og algoritmen har ingen mekanisme for å oppdage at veien den har valgt, har blitt dyr. Hvor robust er det? Som trelikt søk på en graf med sykler kan det gå i ring: to naboer som begge ser nærmere målet ut enn resten av frontier, kan ekspanderes annenhver gang for alltid. Som grafsøk på en endelig graf er det fullstendig, fordi nådd-mengden hindrer at samme tilstand ekspanderes på nytt uten grunn. Kostnadsoptimalt er det aldri garantert, uansett variant og uansett hvor god $h$ er.

RegneeksempelSpor grådig best-først-søk fra S til G, og sammenlign kostnaden med den billigste stien.Vis løsning

Kanter (urettet, kostnad): S–A 4, S–B 3, A–C 2, A–G 7, B–C 2, C–G 3
Heuristikk h: S 6, A 2, B 5, C 3, G 0
Grafsøk, lik h avgjøres alfabetisk, måltest ved uttak.

Steg 1. Frontier = {S(6)}. Ta ut S og generer A(2) og B(5).

Steg 2. Ta ut A, som har lavest $h$ . Generer C(3) og G(0).

Steg 3. Ta ut G. Måltesten lykkes, og ekspansjonsrekkefølgen er S, A, (G).

Steg 4. Følg foreldrepekerne: S → A → G med kostnad $4 + 7 = 11$ .

Steg 5. Den billigste stien er S → B → C → G med kostnad $3 + 2 + 3 = 8$ . Grådig søk brukte bare to ekspansjoner, men betalte 3 ekstra fordi $h (A) = 2$ trakk det inn på den lange kanten A–G.

Øving 1 av 2Flervalg

Hvilket utsagn om grådig best-først-søk på en endelig graf med positive kantkostnader stemmer?

Øving 2 av 2Rekkefølge

Kjør grådig best-først-søk som grafsøk fra S til G. Lik $h$ avgjøres alfabetisk, og måltesten skjer når en node tas ut av frontier. Skriv alle nodene i den rekkefølgen de tas ut av frontier, fra startnoden til og med målnoden (uten parentes), adskilt med komma.

Kanter (urettet, kostnad): S–A 2, S–B 3, A–C 4, B–D 2, C–E 3, D–E 2, E–G 5
Heuristikk h: S 7, A 5, B 5, C 3, D 4, E 2, G 0

Steg 2 av 7

A*: f = g + h

Konsept

Grådig søk ser bare framover, og uniform-kostnad-søk ser bare bakover. A*-søk (A* search) bruker begge deler. Prioriteten i frontier er ƒevalueringsfunksjonen:

f (n) = g (n) + h (n)

Her er $g (n)$ kostnaden for stien søket har funnet fram til $n$ , og $h (n)$ er anslaget for resten. Summen $f (n)$ anslår altså totalkostnaden for den beste løsningen som går gjennom $n$ langs denne stien. A* tar alltid ut posten med lavest $f$ .

Notasjonen for en frontier-post viser alle leddene. C(8=1+2+5) betyr at stien til C består av kanter med kostnad 1 og 2, at $h (C) = 5$ , og at $f (C) = 8$ . Skriver du frontier slik for hånd, ser du hvor hvert tall kommer fra, og sensor kan følge utregningen.

Fire regler avgjør hva A* gjør i en sporingsoppgave:

Måltest ved uttak. Et mål kan bli generert via en dyr sti. Først når det tas ut, er det billigere enn alt annet i frontier.
Oppdatering i frontier. Finner søket en strengt billigere sti til en node som ligger i frontier, får posten ny $g$ , ny $f$ og ny forelder. Den gamle posten forsvinner.
Gjenåpning. Finner søket en strengt billigere sti til en node som allerede er ekspandert, legges noden inn igjen. Det er standard grafsøk, og det får betydning i steg 4.
Likhet. Har to poster samme $f$ , avgjør oppgavens regel, oftest alfabetisk rekkefølge.

Pseudokode

A* i pseudokode

1a_stjerne(start, er_maal, barn, h):2    beste_g = {start: 0}3    frontier = prioritetskø ordnet på f = g + h(node)    # lik f: oppgavens tie-break4    legg start inn i frontier med g = 05    så lenge frontier ikke er tom:6        node = ta ut posten med lavest f7        hvis er_maal(node):                     # måltest ved uttak8            returner stien til node9        for (neste, kost) i barn(node):         # fast barnerekkefølge10            g_ny = beste_g[node] + kost11            hvis neste ikke er nådd eller g_ny < beste_g[neste]:   # strengt billigere12                beste_g[neste] = g_ny13                forelder[neste] = node14                legg neste inn med f = g_ny + h(neste)15                # ligger neste i frontier, erstattes posten;16                # er den ekspandert, åpnes den igjen (gjenåpning)17    returner feil

A* er best-først-søk med prioritet $f = g + h$ . Én betingelse, «strengt billigere», styrer både oppdatering i frontier og gjenåpning av ekspanderte noder.

Interaktiv figur

I løypenettet under kommer toppen G tidlig inn i frontier, men via en dyr sti.

Prøv: gå én ekspansjon av gangen og følg posten for G fra den kommer inn i frontier til den tas ut.

Trinn 1 av 5 · VelgFrontier inneholder bare startnoden S, så S tas ut.

Ekspandert0Frontier1

Algoritme

Variant

Flere valg

Måltest

Likhet

Gjenåpning

Forklar hvert trinn

Vis utregning

Steg	Tatt ut	Frontier etter
0	–	S(6)

Laster figur …

Figur 3.2A* i et løypenett. Minutter på ski langs kantene og h ved nodene; grafsøk, lik f avgjøres alfabetisk, og målet testes ved uttak.

Interaktiv

RegneeksempelKjør A* som grafsøk fra S til G, og skriv frontier etter hver ekspansjon.Vis løsning

Kanter (urettet, kostnad): S–A 1, S–B 4, A–B 2, A–C 5, B–C 1, B–G 6, C–G 3
Heuristikk h: S 5, A 4, B 3, C 2, G 0
Lik f avgjøres alfabetisk, måltest ved uttak.

Steg 1. Ta ut S(5=0+5). Frontier: A(5=1+4), B(7=4+3).

Steg 2. Ta ut A. Via A koster B bare $1 + 2 = 3 < 4$ , så posten for B oppdateres. Frontier: B(6=1+2+3), C(8=1+5+2).

Steg 3. Ta ut B. Via B koster C $3 + 1 = 4 < 6$ , og G kommer inn med $g = 9$ . Frontier: C(6=1+2+1+2), G(9=1+2+6+0).

Steg 4. Ta ut C. Via C koster G $4 + 3 = 7 < 9$ . Frontier: G(7=1+2+1+3+0).

Steg 5. Ta ut G. Ekspansjonsrekkefølgen er S, A, B, C, (G), og stien S → A → B → C → G koster 7. G lå i frontier med $f = 9$ før den billigere stien ble funnet, og det er måltesten ved uttak som redder optimaliteten.

Øving 1 av 2Flervalg

A* har posten C(9=2+3+4) i frontier, der leddene er kantkostnadene langs stien og til slutt $h (C)$ . Hva betyr $f (C) = 9$ ?

Øving 2 av 2Rekkefølge

Kjør A* som grafsøk fra S til G. Lik $f$ avgjøres alfabetisk, og måltesten skjer når en node tas ut av frontier. Skriv alle nodene i den rekkefølgen de tas ut av frontier, fra startnoden til og med målnoden (uten parentes), adskilt med komma.

Kanter (urettet, kostnad): S–A 3, S–B 1, A–D 2, B–C 2, C–D 1, C–E 4, D–G 5, E–G 2
Heuristikk h: S 7, A 6, B 6, C 5, D 4, E 2, G 0

Steg 3 av 7

Admissibel og konsistent

Konsept

Hvor god må $h$ være for at A* skal finne den billigste stien? Fasiten heter sann restkostnad $h^{*} (n)$ (true cost to goal): kostnaden for den billigste stien fra $n$ til et mål. En admissibel heuristikk (admissible heuristic) overvurderer aldri (ƒadmissibilitetskravet):

h (n) \leq h^{*} (n) for alle n

Likhet er lov. En admissibel heuristikk er optimistisk: den kan tro at målet er nærmere enn det er, men aldri lenger unna. For å sjekke det trenger du en $h^{*}$ -tabell. Regn den baklengs: $h^{*} (m \overset{a}{˚} l) = 0$ , og hver annen node får den billigste veien til en node du allerede har regnet ut. Det er et uniform-kostnad-søk med målet som start. Sammenlign så $h$ og $h^{*}$ node for node.

En konsistent (monoton) heuristikk (consistent heuristic) er strengere. Anslaget faller aldri mer langs en kant enn kanten koster (ƒkonsistenskravet):

h (n) \leq c (n, a, n^{'}) + h (n^{'}) for hver kant, og h (m \overset{a}{˚} l) = 0

Det er trekantulikheten: anslaget fra $n$ kan ikke være større enn å gå til $n^{'}$ og bruke anslaget derfra. Den sjekkes kant for kant, uten $h^{*}$ . I en urettet graf kan en kant gås begge veier, så ulikheten må holde i begge retninger. Konsistens gir admissibilitet: summerer du ulikheten langs den billigste stien fra $n$ til målet, får du $h (n) \leq h^{*} (n)$ . Det omvendte gjelder ikke.

Interaktiv figur

En lagerrobot kjører mellom fem stasjoner og pakkebordet G. Kjøretidene står på kantene, robotens anslag ved nodene.

Prøv: velg Sjekk h, finn kanten der h faller mer enn kantkostnaden, og se at den motsatte retningen av samme kant holder.

Trinn 1 av 5 · VelgFrontier inneholder bare startnoden S, så S tas ut.

Ekspandert0Frontier1

Vis

Variant

Flere valg

Måltest

Likhet

Gjenåpning

Forklar hvert trinn

Vis utregning

Steg	Tatt ut	Frontier etter
0	–	S(7)

Laster figur …

Figur 3.3Admissibel, men er den konsistent? Tallet på en kant er kjøretiden og tallet ved en node er h; grafen er urettet.

Interaktiv

Playground

Koden under kjører A* med gjenåpning på en annen graf, der $h (C)$ styres av en glidebryter, og sjekker begge egenskapene.

A* med én justerbar h-verdi

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.

h_C4

Pythonkap3-astar-kode.py

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 node
beste_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'}")

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 node
beste_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'}")

Ctrl/Cmd + Enter kjører

RegneeksempelAvgjør om heuristikken er admissibel og konsistent, og navngi bruddene.Vis løsning

Kanter (urettet, kostnad): S–A 3, S–B 2, A–C 1, A–G 4, B–C 3, C–G 2
Heuristikk h: S 5, A 4, B 3, C 2, G 0

Steg 1. Sann restkostnad baklengs fra G. $h^{*} (G) = 0$ og $h^{*} (C) = 2$ . A kan gå direkte (4) eller via C ( $1 + 2 = 3$ ), så $h^{*} (A) = 3$ . B går via C: $h^{*} (B) = 3 + 2 = 5$ . For S er $h^{*} (S) = min (3 + 3, 2 + 5) = 6$ .

Steg 2. Admissibilitet. $h (A) = 4 > h^{*} (A) = 3$ . Heuristikken er ikke admissibel, og A er eneste brudd.

Steg 3. Konsistens kant for kant. S–A: $5 \leq 3 + 4$ og $4 \leq 3 + 5$ . S–B: $5 \leq 2 + 3$ og $3 \leq 2 + 5$ . A–C: $4 \leq 1 + 2$ er usant, mens $2 \leq 1 + 4$ holder. A–G, B–C og C–G holder i begge retninger. Bare retningen A → C bryter.

Steg 4. Kontroll. En heuristikk som ikke er admissibel, kan ikke være konsistent, så nei i steg 3 var ventet. Begge bruddene skyldes at $h (A)$ er for høy.

Øving 1 av 3Flervalg

En heuristikk og den sanne restkostnaden er gitt for alle noder. Hvilket utsagn stemmer?

Node:  S  A  B  C  D  G
h:     7  5  6  2  3  0
h*:    9  5  4  6  3  0

Øving 2 av 3Flervalg

I en urettet graf har kanten C–D kostnad 2, med $h (C) = 3$ og $h (D) = 6$ . Alle andre kanter oppfyller konsistensulikheten i begge retninger, og $h (G) = 0$ . Hva er riktig konklusjon?

Øving 3 av 3Liste

Hvilke noder bryter admissibilitet? Skriv nodene i alfabetisk rekkefølge, adskilt med komma.

Kanter (urettet, kostnad): S–A 2, S–B 5, A–C 4, B–C 1, B–D 3, C–G 6, D–G 2
Heuristikk h: S 9, A 6, B 6, C 7, D 2, G 0

Steg 4 av 7

Når er A* optimal?

Konsept

A* er kostnadsoptimal (cost-optimal), altså garantert å returnere en billigste sti, under vilkår som henger sammen med søkevarianten.

Admissibel $h$ holder for trelikt søk og for grafsøk med gjenåpning. Anta at A* er i ferd med å ta ut et mål med kostnad $C > C^{*}$ , der $C^{*}$ er den optimale kostnaden. Et sted på en optimal sti ligger det da en node $n$ i frontier, med $f (n) = g (n) + h (n) \leq g (n) + h^{*} (n) = C^{*}$ . Siden $f (n) \leq C^{*} < C$ , tas $n$ ut før det dyre målet, og slik fortsetter det til en optimal løsning er tatt ut.

Konsistent $h$ gir mer. Langs enhver sti er $f$ ikke-avtagende: $f (n^{'}) = g (n) + c + h (n^{'}) \geq g (n) + h (n) = f (n)$ . Første gang en node tas ut, har den derfor allerede den billigste stien sin, og gjenåpning blir aldri nødvendig. Da holder også grafsøk med lukket mengde, der en ekspandert node aldri åpnes igjen. Hver søkekontur (contour) omslutter nodene med $f$ under en grense, og A* fyller konturene innenfra: alle noder med $f < C^{*}$ ekspanderes, noen med $f = C^{*}$ og ingen med $f > C^{*}$ .

Interaktiv figur

Med admissibel, men inkonsistent $h$ kan lukket mengde gå galt. En node kan bli ekspandert via en dyr sti fordi en node på den billige stien har høy $h$ . Når den billige stien dukker opp, er noden allerede lukket, og alt som bygger på den, arver den for høye kostnaden. Derfor sier en god oppgave hvilken variant den bruker.

Prøv: kjør til målet tas ut og noter kostnaden, slå så på Gjenåpning under Flere valg og kjør på nytt: hvilken node ekspanderes to ganger?

Trinn 1 av 5 · VelgFrontier inneholder bare startnoden S, så S tas ut.

Ekspandert0Frontier1

Variant

Flere valg

Måltest

Likhet

Gjenåpning

Forklar hvert trinn

Vis utregning

Steg	Tatt ut	Frontier etter
0	–	S(5)

Laster figur …

Figur 3.4Lukket mengde eller gjenåpning. h er admissibel, men faller fra 6 til 1 langs A–B; grafsøk uten gjenåpning, lik f alfabetisk, måltest ved uttak.

Interaktiv

RegneeksempelAvgjør hvilke noder A* garantert ekspanderer, hvilke den kan ekspandere, og hvilke den aldri ekspanderer.Vis løsning

Kanter (urettet, kostnad): S–A 2, S–B 3, A–C 2, A–E 1, B–C 3, B–D 4, C–G 5, D–G 3
Heuristikk h: S 6, A 5, B 4, C 4, D 3, E 5, G 0 (konsistent)

Steg 1. Billigste stikostnad fra S. $g^{*} (A) = 2$ , $g^{*} (B) = 3$ , $g^{*} (E) = 3$ , $g^{*} (C) = min (2 + 2, 3 + 3) = 4$ , $g^{*} (D) = 7$ og $g^{*} (G) = min (4 + 5, 7 + 3) = 9$ , så $C^{*} = 9$ .

Steg 2. Verdien f langs de beste stiene. S 6, A 7, B 7, C 8, E 8, D 10 og G 9.

Steg 3. Del i konturer. $f < 9$ : S, A, B, C og E ekspanderes garantert, også blindveien E. $f > 9$ : D ekspanderes aldri. Bare G har $f = C^{*}$ . Hadde en annen node også hatt $f = 9$ , ville tie-break-regelen avgjort om den ble ekspandert.

Steg 4. Kontroll. A* med alfabetisk tie-break ekspanderer S, A, B, C, E og tar så ut G via stien S → A → C → G, som koster 9.

Øving 1 av 2Flervalg

En heuristikk er admissibel, men ikke konsistent. Når er A* som grafsøk garantert å returnere en billigste sti?

Øving 2 av 2Tallsvar

Kjør A* som grafsøk med lukket mengde: en node som er ekspandert, åpnes ikke igjen, selv om søket senere finner en billigere sti dit. Lik $f$ avgjøres alfabetisk, og måltesten skjer når en node tas ut av frontier. Hva koster stien A* returnerer?

Kanter (urettet, kostnad): S–A 1, S–C 4, A–B 1, B–C 1, C–D 2, D–G 3
Heuristikk h: S 5, A 7, B 2, C 1, D 3, G 0

Steg 5 av 7

Å lage gode heuristikker

Konsept

Hvor kommer gode heuristikker fra? Den mest brukte oppskriften er å fjerne regler. Et relaksert problem (relaxed problem) er det opprinnelige problemet med færre begrensninger på handlingene. Alle løsninger i originalen er fortsatt løsninger i det relakserte problemet, og det kan komme flere til. Derfor er den optimale kostnaden der en nedre grense for den sanne, altså admissibel. Den er også konsistent, fordi optimale kostnader i en graf alltid oppfyller trekantulikheten.

Glidebrettet på 2 × 3 felt viser hvordan. En brikke kan bare flytte til et nabofelt, og bare hvis feltet er tomt. Fjerner du begge vilkårene, kan en brikke flytte hvor som helst i ett trekk, og kostnaden blir $h_{1}$ , antall brikker på feil plass. Fjerner du bare kravet om tomt felt, må hver brikke gå hele veien selv, og kostnaden blir $h_{2}$ , summen av Manhattan-avstandene.

h₁, h₂ og h* for fire tilstander
Tilstand	h₁ feil plass	h₂ Manhattan	max(h₁, h₂)	h₁ + h₂	h*
1 2 3 / _ 4 5	2	2	2	4	2
1 5 _ / 4 3 2	3	5	5	8	5
_ 4 1 / 2 5 3	4	7	7	11	9
4 5 _ / 1 2 3	5	5	5	10	21

Markert: summen er større enn h* og overvurderer.

Laster interaktiv figur …

Figur 3.5To relaksasjoner av glidebrettet. Målet er 1 2 3 / 4 5 , der er det tomme feltet.

RegneeksempelRegn ut

h_{1}

h_{2}

for tilstanden 1 _ 3 / 5 4 2, der målet er 1 2 3 / 4 5 _.Vis løsning

Steg 1. Feilplasserte brikker. 1 og 3 står riktig, mens 2, 4 og 5 står feil. Det tomme feltet teller ikke, så $h_{1} = 3$ .

Steg 2. Manhattan-avstander. Brikke 2 står nederst til høyre og skal øverst i midten: $1 + 1 = 2$ . Brikke 4 står nederst i midten og skal ett felt til venstre: 1. Brikke 5 står nederst til venstre og skal ett felt til høyre: 1. Altså er $h_{2} = 2 + 1 + 1 = 4$ .

Steg 3. Kombiner. $max (h_{1}, h_{2}) = 4$ og $h_{1} + h_{2} = 7$ .

Steg 4. Sammenlign med fasit. Et fullt søk gir $h^{*} = 16$ . Begge heuristikkene er admissible, men langt unna, og $h_{2}$ er nærmest.

Konsept

Når $h_{2} (n) \geq h_{1} (n)$ for alle $n$ og begge er admissible, sier vi at $h_{2}$ dominerer $h_{1}$ (dominans mellom heuristikker, dominance). Med konsistente heuristikker ekspanderer A* med $h_{2}$ da aldri flere noder enn med $h_{1}$ , bortsett fra noder med $f = C^{*}$ , der tie-break avgjør. Dominerer ingen av dem, tar du ƒmaksimum av heuristikker. Maksimum av admissible heuristikker er admissibelt og dominerer hver av dem. Summen er det generelt ikke, fordi to heuristikker kan telle de samme trekkene.

Unntaket er disjunkte mønsterdatabaser (disjoint pattern databases). En mønsterdatabase (pattern database) lagrer den eksakte kostnaden for et delproblem, for eksempel å få brikke 1, 2 og 3 på plass. Teller hver database bare trekk med egne brikker, og delproblemene ikke deler brikker, kan oppslagene legges sammen.

Et mål på hvor god en heuristikk er, er effektiv forgreningsfaktor $b^{*}$ (effective branching factor). Genererer A* $N$ noder for en løsning på dybde $d$ , er $b^{*}$ forgreningsfaktoren et uniformt tre måtte hatt for å inneholde $N + 1$ noder (ƒlikningen for $b^{*}$ ):

N + 1 = 1 + b^{*} + (b^{*})^{2} + \dots + (b^{*})^{d}

Playground

Effektiv forgreningsfaktor regnet ut

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.

N120d4

Pythonkap3-effektiv-b.py

N = 120  # @param 5..2000
d = 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})")

Ctrl/Cmd + Enter kjører

Konsept

Merk

Det finnes flere måter å bygge heuristikker på. Landemerker lagrer forhåndsregnede avstander til noen utvalgte noder, toveis heuristisk søk leter fra begge ender samtidig, og heuristikker kan læres fra løste eksempler. Metodene er nyttige i praksis, men vektes lite på eksamen.

Øving 1 av 3Flervalg

To heuristikker brukes på samme problem, der løsningen ligger på dybde $d = 3$ . Med $h_{1}$ genererer A* $N = 14$ noder, med $h_{2}$ bare $N = 3$ (startnoden er ikke med i $N$ ). Hvilket utsagn stemmer?

Øving 2 av 3Flervalg

$h_{1}$ og $h_{2}$ er begge admissible for samme problem, og ingen av dem dominerer den andre. Hvilket utsagn stemmer?

Øving 3 av 3Flervalg

Hvorfor er den optimale kostnaden i et relaksert problem en admissibel heuristikk for det opprinnelige problemet?

Steg 6 av 7

Minnebegrenset og vektet søk

Konsept

A* har et praktisk problem: frontier og nådd-mengden holder alle genererte noder i minnet, og antallet vokser eksponentielt med dybden på vanskelige problemer. Fire varianter bytter tid eller garantier mot minne:

Med strålesøk (beam search) beholder søket bare de $k$ beste nodene i frontier. Det er billig, men verken fullstendig eller optimalt, fordi den beste stien kan bli kastet.
IDA* (iterative-deepening A*) er iterativ fordypning med en $f$ -grense i stedet for en dybdegrense. Hver iterasjon er et dybde-først-søk som kutter noder med $f$ over grensen, og neste grense er den minste $f$ som ble kuttet. Minnet er lineært i dybden.
Et rekursivt best-først-søk (recursive best-first search) følger det beste barnet rekursivt, men husker $f$ for det beste alternativet. Går stien over den verdien, rulles søket tilbake, og noden som forlates, får den beste $f$ -verdien i deltreet sitt, slik at grenen kan tas opp igjen senere.
SMA* (simplified memory-bounded A*) er A* med et fast minnetak. Når minnet er fullt, slettes bladet med høyest $f$ , og verdien lagres i forelderen.

IDA*, RBFS og SMA* bevarer optimaliteten til A* når $h$ er admissibel, SMA* så lenge den billigste løsningen får plass i minnet. Prisen er tid: noder genereres på nytt, og IDA* og RBFS kan bruke langt flere ekspansjoner enn A*.

RegneeksempelKjør IDA* fra S til G, og oppgi grensen og ekspansjonene i hver iterasjon.Vis løsning

Kanter (urettet, kostnad): S–A 2, S–B 1, A–G 4, B–C 3, C–G 1
Heuristikk h: S 4, A 3, B 3, C 1, G 0
Barn i alfabetisk rekkefølge, ingen node gjentas langs stien.

Steg 1. Første grense er $f (S) = 0 + 4 = 4$ .

Steg 2. Iterasjon 1. S ekspanderes. A har $f = 2 + 3 = 5 > 4$ og kuttes. B har $f = 1 + 3 = 4$ og ekspanderes, mens barnet C har $f = 1 + 3 + 1 = 5$ og kuttes. Ekspandert: S, B. Minste kuttede $f$ er 5.

Steg 3. Iterasjon 2, grense 5. S ekspanderes, så A ( $f = 5$ ), men G via A har $f = 6$ og kuttes. Så ekspanderes B og C, og G via C har $f = 1 + 3 + 1 + 0 = 5$ . Målet er funnet: S → B → C → G med kostnad 5.

Steg 4. Prisen. S og B ble ekspandert to ganger. Til gjengjeld lagres bare stien som utforskes, aldri en hel frontier.

Konsept

Den andre veien til et raskere søk er å stole mer på heuristikken, med vektet A* (weighted A*). Den bruker en ƒvektet evalueringsfunksjon:

f (n) = g (n) + W \cdot h (n), W > 1

Playground

Større $W$ gjør søket grådigere: det ekspanderer ofte langt færre noder, men $W \cdot h$ kan overvurdere, så optimaliteten forsvinner. Med admissibel $h$ koster stien likevel høyst $W \cdot C^{*}$ . Med $W = 1$ er det vanlig A*, og når $W$ vokser mot uendelig, nærmer søket seg grådig best-først-søk.

Vektet A* for en lagerrobot

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*.

W1.00

Pythonkap3-vektet-a.py

import heapq

W = 1.0  # @param 1.0..3.0 0.25

lager = ["S~~~~~~G",
         ".######.",
         "...~~~..",
         ".######.",
         "........"]  # . = gang (kost 1), ~ = travel sone (kost 3), # = reol
start, 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}")

import heapq

W = 1.0  # @param 1.0..3.0 0.25

lager = ["S~~~~~~G",
         ".######.",
         "...~~~..",
         ".######.",
         "........"]  # . = gang (kost 1), ~ = travel sone (kost 3), # = reol
start, 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}")

Ctrl/Cmd + Enter kjører

Øving 1 av 1Flervalg

Hvilket utsagn om minnebegrenset søk stemmer?

Steg 7 av 7

Eksamensfokus

Slik spørres det

Sporing. Du får en graf med kantkostnader og $h$ ved nodene, og skal kjøre grådig søk, UCS eller A*. Skriv frontier som C(8=1+2+5), så sensor ser hvor tallene kommer fra. Svarmal: ekspansjonsrekkefølge · funnet sti · stikostnad · optimal?
Les konvensjonene først. Grafsøk eller trelikt søk, gjenåpning eller lukket mengde, tie-break, når måltesten skjer og om start og mål skal tas med. Står noe ikke i oppgaven, skriv antagelsen din.
Heuristikk-egenskaper. Lag en $h^{*}$ -tabell baklengs fra målet, avgjør admissibilitet node for node og konsistens kant for kant i begge retninger, og navngi bruddene.
Intervall for én h-verdi. Hvilke verdier kan $h (C)$ ha for at $h$ skal være admissibel, konsistent eller gi en bestemt ekspansjonsrekkefølge? Skriv én ulikhet per kant eller per sammenligning i frontier. Står det «uten å stole på tie-break», blir ulikhetene strenge.
Design en heuristikk. Relakser problemet, si hvilken regel du fjerner, og begrunn admissibilitet med at hver løsning i originalen også løser det relakserte problemet.

Vanlig felleAdmissibel er tilstrekkelig, ikke nødvendig

A* kan godt finne den optimale stien med en heuristikk som ikke er admissibel. I playgrounden i steg 3 skjer det for flere verdier av $h_{C}$ . Admissibilitet er det som gir garantien, så skriv aldri at en heuristikk som ikke er admissibel, nødvendigvis gir feil svar.

Vanlig felleKonsistens er en ulikhet, og målet må ha h = 0

Konsistens krever ikke at $h$ faller med nøyaktig kantkostnaden, bare at den ikke faller med mer. Kontroller også at $h (m \overset{a}{˚} l) = 0$ , og sjekk hver urettet kant fra begge ender.

Vanlig felleLukket mengde er ikke standard

Med admissibel, men inkonsistent $h$ avhenger svaret av om grafsøket gjenåpner noder. Standard grafsøk gjenåpner. Anta ikke lukket mengde uten gjenåpning hvis oppgaven ikke sier det.

Sjekk deg selvEt mål er generert med

f = 12

, mens en annen post i frontier har

f = 10

. Kan søket stoppe nå?Vis svar

Nei. Måltesten skjer når målet tas ut. Posten med $f = 10$ kan føre til en billigere sti til målet, så A* fortsetter til målet selv har lavest $f$ i frontier.

Sjekk deg selvHvorfor er

max (h_{1}, h_{2})

bedre enn

h_{1} + h_{2}

når begge er admissible?Vis svar

Maksimum er på hver node lik en av to undervurderinger, så det er admissibelt, og det dominerer begge. Summen kan telle de samme trekkene to ganger og overvurdere, med mindre heuristikkene kommer fra disjunkte mønsterdatabaser.

Sjekk deg selvKanten B–C har kostnad 3,

h (B) = 2

h (C) = 7

. Er kanten konsistent?Vis svar

Nei. Retningen B → C holder ( $2 \leq 3 + 7$ ), men C → B krever $7 \leq 3 + 2$ , som er usant. Én retning er nok til å bryte konsistensen.

Øving 1 av 2Flervalg

Du bytter fra A* til vektet A* med $W = 2$ og en admissibel $h$ . Hvilken garanti gir du fra deg, og hva får du igjen?

Øving 2 av 2Tallsvar

Alle h-verdier unntatt $h (C)$ er gitt. Hva er den største heltallsverdien $h (C)$ kan ha for at $h$ skal være konsistent?

Kanter (urettet, kostnad): S–A 2, S–B 4, A–C 3, B–C 1, B–G 7, C–G 5
Heuristikk h: S 7, A 6, B 3, C ?, G 0

Mine notater

Skriv egne notater for dette kapittelet. De lagres automatisk og dukker opp i «Mine notater»-oversikten paa fag-siden.

Laster…

Test deg selv

Tar du quizen på kapittel 3?

15 spørsmål satt sammen til dette kapittelet — den beste måten å sjekke at det sitter.

Start quiz

Begreper & referanser

17 begreper · 6 formler · 4 referanser i kapittelet

Forrige

Søkeproblemer og uinformert søk

Kap 02

Neste

Lokalt søk og optimering

Kap 04