Søkeproblemer og uinformert søk

Et sykkelbud starter ved lageret, skal levere to pakker og avslutte ved kontoret. Før en algoritme kan hjelpe, må oppgaven gjøres om til et søkeproblem. Det har seks deler:

• •et tilstandsrom (state space), alle tilstandene verden kan være i: her krysset budet står i og hvilke pakker som er levert;
• •en starttilstand: ved lageret, ingen pakker levert;
• •en måltest som sier om en tilstand er et mål: begge pakkene levert og budet ved kontoret;
• •handlingene som er lov i hver tilstand: sykle til et nabokryss, eller levere en pakke ved riktig adresse;
• •en overgangsmodell (transition model) $\text{Result}(s,a)$ som sier hvilken tilstand en handling fører til;
• •en handlingskostnad (action cost) $c(s,a,s^{\prime })$ for hvert steg, her minutter.

Måltesten kan sjekke én bestemt tilstand, en liste av tilstander eller en egenskap som mange tilstander har.

En løsning er en sekvens av handlinger fra starttilstanden til en måltilstand. Kostnaden til en sti, stikostnaden (path cost), er summen av handlingskostnadene langs den. Begge begrepene står under handlingskostnad og stikostnad, og formelen er ƒstikostnad:

En løsning er optimal når ingen annen løsning har lavere stikostnad.

Formuleringen er en abstraksjon. Været, hvilken sykkel budet bruker og nøyaktig hvor i gata det står, er utelatt. En abstraksjon er god når hver abstrakt løsning kan gjøres om til en konkret, og når den er så enkel som mulig uten å miste noe som påvirker svaret. Fjerner vi for mye, finner algoritmen planer som ikke virker; tar vi med for mye, blir tilstandsrommet unødvendig stort. Har byen 15 kryss og budet 3 pakker, er det $15\cdot 2^3=120$ tilstander. Tar vi også med hvilken av 4 sykler budet bruker, blir det 480, uten at en eneste rute blir bedre.

Glidebrettet er et leketøysproblem: lite, presist og likt for alle, og derfor godt egnet til å teste og sammenligne algoritmer. Budet er nærmere et praktisk problem, der svaret faktisk skal brukes og modellen aldri blir helt riktig. Andre eksempler er å velge rekkefølgen en brøytebil tar gatene i, å finne de færreste redigeringene som gjør én DNA-streng om til en annen, eller å finne trekkene en lagerrobot trenger for å hente en pall bakerst i en hylle. Praktiske problemer har som regel langt flere tilstander, og kostnadene må anslås, men formuleringen i seks deler er den samme.

Søkealgoritmer bygger et søketre (search tree) over tilstandsrommet. Roten er starttilstanden, og hver kant er en handling. Å ekspandere en node er å bruke handlingene og overgangsmodellen på tilstanden og lage én barnenode per handling. Nodene som er generert, men ikke ekspandert ennå, er frontier: grensen mellom det utforskede og det ukjente.

En node i treet er en liten datastruktur: tilstanden, forelderen, handlingen som førte dit, og stikostnaden $g$. Når søket finner et mål, følger vi foreldrepekerne tilbake til roten og leser av stien. To noder kan ha samme tilstand, men ulike stier dit.

Alle søkene i kapitlet er varianter av samme løkke: ta ut en node fra frontier, sjekk om den er et mål, ekspander den, og legg barna inn. Det eneste som skiller dem, er hvilken node som tas ut. I best-først-søk velger vi noden med lavest verdi av en evalueringsfunksjon $f(n)$, som heter prioritet i pseudokoden:

1best_forst(start, er_maal, naboer, prioritet):2    beste_g = {start: 0}             # nådd-mengden: billigste kjente sti hit3    forelder = {start: ingen}4    kø = prioritetskø med posten (prioritet(start, 0), 0, start)5    så lenge kø ikke er tom:6        (_, g, x) = ta ut posten med lavest prioritet7        hvis g > beste_g[x]:8            hopp over posten         # utdatert: x er nådd billigere siden9        hvis er_maal(x):             # måltest ved uttak10            returner stien til x langs forelder, og g11        for (y, kost) i naboer(x):12            g_y = g + kost13            hvis y ikke er i beste_g eller g_y < beste_g[y]:   # ny eller strengt billigere14                beste_g[y] = g_y15                forelder[y] = x16                legg (prioritet(y, g_y), g_y, y) i kø17    returner «ingen løsning»

Med en FIFO-kø i stedet for en prioritetskø blir det bredde-først-søk, med $f(n)=g(n)$ uniform-kostnad-søk, og med en stakk dybde-først-søk.

Søketreet er ikke det samme som tilstandsrommet. Har grafen en sykel, kan samme tilstand dukke opp mange ganger i treet, og et søk som ikke husker hvor det har vært, kan gå i ring. Botemiddelet er en nådd-mengde (reached set): en tabell over tilstandene søket har nådd, med beste kjente stikostnad til hver. Et barn legges bare inn hvis tilstanden er ny, eller hvis den nye stien er strengt billigere. Et søk med nådd-mengde er et grafsøk (graph search). Et søk uten er et trelikt søk (tree-like search), som sparer minnet til nådd-mengden og er raskere per node, men som kan gjenta arbeid og i verste fall gå i ring for alltid.

Ferjenettet under har en sykel mellom øyene S, A og B.

Når samme tilstand kan nås på flere måter, har vi tre valg. Vi kan huske alle nådde tilstander, som i grafsøk. Vi kan nøye oss med å sjekke at en tilstand ikke allerede står på stien fra roten, en billig sykelsjekk som stopper ring-gange, men ikke andre redundante stier. Eller vi kan la være å sjekke, som i trelikt søk, når redundante stier er umulige eller sjeldne, for eksempel når tilstandsrommet selv er et tre.

Når vi sammenligner søkealgoritmer, bruker vi fire kriterier. De to første er fullstendighet og kostnadsoptimalitet (completeness, cost optimality): algoritmen er fullstendig hvis den finner en løsning når det finnes én, og melder fra når det ikke finnes noen, og kostnadsoptimal hvis løsningen den finner, er den billigste. I tillegg ser vi på tidskompleksitet og minnekompleksitet, målt i hvor mange noder søket genererer og lagrer. I et uendelig tilstandsrom må et fullstendig søk være systematisk og før eller siden nå enhver tilstand som kan nås.

Et bredde-først-søk (breadth-first search, BFS) ekspanderer alltid den grunneste noden først: roten, så alle barna, så alle barnebarna. Frontier er en FIFO-kø, og nye barn legges bakerst.

Bykartet under har åtte kryss, og alle gatene tar like lang tid å sykle.

BFS tester mål allerede når en node genereres: måltest (goal test) skjer ved generering, ikke ved uttak. Det er trygt fordi alle noder på dybde $d-1$ er generert, og dermed måltestet, før noen node på dybde $d$ blir generert. Når et mål dukker opp på dybde $d$, finnes det derfor ikke noe grunnere mål. Tidlig måltest sparer arbeid: med sen måltest ville søket også ekspandert resten av nivå $d-1$ og nodene på dybde $d$ som står foran målet i køen.

Kompleksiteten uttrykkes med tre størrelser: forgreningsfaktor (branching factor) $b$, som er antall barn per node, dybden $d$ til den grunneste løsningen og den største dybden $m$ i tilstandsrommet. Ligger det grunneste målet på dybde $d$, genererer BFS i verste fall ƒnoder generert av BFS:

noder, og alle ligger i minnet samtidig, fordi nådd-mengden husker dem. Minnet er det store problemet. Med $b=8$ og $d=8$ er summen over 19 millioner noder, og med 500 byte per node trengs nesten 10 GB minne; ett nivå dypere ganger begge tallene med 8. BFS er fullstendig når $b$ er endelig, og optimal når alle handlinger koster det samme, siden den grunneste løsningen da også er den billigste. Med ulike kostnader kan en sti med flere, men billigere kanter slå den grunneste.

Når handlingene koster ulikt, er den grunneste stien ikke lenger den billigste. Et uniform-kostnad-søk (uniform-cost search, UCS) ekspanderer noden med lavest stikostnad $g(n)$, så frontier er en prioritetskø sortert på $g$. I informatikken er algoritmen kjent som Dijkstras algoritme. Vi skriver en frontier-post som C(3): noden C med $g=3$.

To regler gjør UCS riktig. Den første er at måltesten skjer når en node tas ut av frontier. Når målet genereres, kan det ha kommet via en dyr kant mens en billigere sti fortsatt venter. Når målet tas ut, har alle noder med lavere $g$ allerede vært ute, så ingen billigere sti finnes. Den andre regelen er at frontier oppdateres: finner søket en strengt billigere sti til en node som allerede ligger der, erstattes posten. Den gamle posten forsvinner, den ekspanderes aldri, og den skal ikke stå i et svar. Er den nye stien bare like dyr, beholdes den gamle posten og forelderen.

Veinettet under har kjøretid i minutter på kantene.

UCS er fullstendig og optimal så lenge hver handling koster minst en positiv konstant $ϵ$. Uten den grensen kan søket gå i det uendelige langs kanter som koster nesten ingenting. Kompleksiteten avhenger ikke av dybden, men av forholdet mellom den optimale kostnaden $C^{\ast }$ og $ϵ$, ƒkompleksitet for UCS:

Er alle kostnader like, blir uttrykket $O(b^{d+1})$, litt verre enn BFS, fordi UCS først stopper når målet tas ut.

UCS sprer seg i konturer av økende $g$: først alle noder som kan nås på under ett minutt, så alle under to minutter, og så videre, uavhengig av hvor målet ligger. Derfor er uinformert søk sløsende. Det leter like mye bort fra målet som mot det, og informert søk retter på det med et anslag på hvor langt det er igjen.

Et dybde-først-søk (depth-first search, DFS) ekspanderer alltid den dypeste noden i frontier. Frontier er en stakk: barna legges på i omvendt alfabetisk rekkefølge, slik at det alfabetisk første tas ut først, og måltesten skjer ved uttak.

Som trelikt søk kan DFS gå i ring på en graf med sykler, og da er det ikke fullstendig. Som grafsøk bruker vi DFS med minne: en utforsket-mengde som sjekkes når en node tas ut. Er noden allerede utforsket, hoppes den over. Barn legges på stakken selv om samme tilstand allerede ligger der, så en tilstand kan bli ekspandert fra en annen forelder enn den den først ble generert fra. På en endelig graf er denne varianten fullstendig. DFS er ikke garantert optimal: den returnerer den første løsningen den treffer, uansett hvor lang den er. Likevel er DFS nyttig i store tilstandsrom uten sykler, fordi den bruker lite minne og ofte finner en løsning raskt når det finnes mange av dem.

Fordelen er minnet. Trelikt DFS husker bare stien fra roten og de ikke-ekspanderte søsknene langs den, ƒminne for DFS: $O(bm)$, der $m$ er største dybde. Et ferdig utforsket deltre kan glemmes. Varianten tilbakesporingssøk (backtracking search) genererer bare ett barn om gangen og husker hvilket som er det neste, så den klarer seg med $O(m)$ minne og kan endre tilstanden på stedet i stedet for å kopiere den.

Grafen under har seks noder, og alle unntatt G ligger på samme sykel.

Et dybdebegrenset søk (depth-limited search, DLS) setter en grense $\ell$. Startnoden har dybde 0, og noder på dybde $\ell$ måltestes, men ekspanderes ikke. Søket kan da ende på tre måter: med en løsning, med cutoff (minst én node lå på grensen, så en løsning kan finnes dypere) eller med failure (hele treet er søkt uten mål, så det finnes ingen løsning). DLS bruker sykelsjekk langs stien: en tilstand som allerede står på stien fra roten, genereres ikke.

Grensen kan velges med kunnskap om problemet. Skal budet bare fra ett kryss til et annet i en by med 12 kryss, kan ethvert kryss nås på høyst 11 steg, så $\ell =11$ er nok til å finne en løsning hvis det finnes en. Det største antallet steg som trengs mellom to tilstander, kalles diameteren til tilstandsrommet. Kjenner vi ikke diameteren, prøver IDS alle grenser etter tur.

Ved iterativ fordypning (iterative deepening search, IDS) kjører vi DLS med $\ell =0,1,2,\dots$ til vi finner en løsning eller får failure. Metoden kombinerer det beste fra BFS og DFS: fullstendig, og optimal når alle handlinger koster det samme, men med minnebruk ƒminne for IDS på bare $O(bd)$.

IDS ser sløsende ut, fordi de øverste nivåene genereres på nytt i hver iterasjon. Men nesten alle nodene ligger på det nederste nivået. Nodene på dybde $d$ genereres én gang, de på dybde $d-1$ to ganger, og så videre, ƒnoder generert av IDS:

Et toveis søk (bidirectional search) kjører ett søk forover fra start og ett bakover fra målet og stopper når de møtes. To søk til dybde $d/2$ er langt billigere enn ett til dybde $d$, ƒtoveis søk: $O(b^{d/2})$. Med $b=10$ og $d=8$ er det omtrent 20 000 noder i stedet for 100 millioner. Prisen er at handlingene må kunne reverseres, at målet må være en konkret tilstand, og at det ene søket må holde frontier i minnet for å oppdage at de to møtes. Med UCS i begge retninger er det ikke nok å stoppe første gang søkene møtes: søket må fortsette til ingen sti gjennom de to frontierene kan bli billigere enn den beste som er funnet.

Valget av algoritme følger av tabellen. Er alle kostnader like og minnet stort nok, er BFS enkel og optimal. Varierer kostnadene, trengs UCS. Er tilstandsrommet stort og minnet knapt, er IDS standardvalget for uinformert søk når kostnadene er like. DFS passer når minnet er knapt og det finnes mange løsninger, men aldri når du trenger den billigste. Er tilstandsrommet lite nok til å få plass i minnet, kan BFS likevel være raskere enn IDS i praksis, fordi den ikke gjentar noe arbeid.