Zoekalgoritmen: ongeïnformeerd en geïnformeerd zoeken

Een zoekprobleem beschrijft keuzes voordat een algoritme die begint te maken. De formulering bepaalt zowel wat een oplossing betekent als hoeveel mogelijkheden het algoritme moet overwegen.

Definieer het probleem

Er zijn zes onderdelen:

• Toestanden beschrijven de mogelijke situaties.
• De begintoestand is waar het zoeken begint.
• Acties zijn de beschikbare keuzes in een toestand.
• Het overgangsmodel, $\text{RESULTAAT}(s,a)$, geeft de toestand na actie $a$.
• De doeltest herkent een aanvaardbare toestand.
• De actiekostenfunctie, $c(s,a,s^{\mathrm{\prime }})$, kent kosten toe aan elke stap.

Alle actiekosten zijn hier positief. Een oplossing van een probleem waarin je een pad zoekt, is een actiereeks die naar een doel leidt. Tel de actiekosten op om de padkosten te krijgen. Een kostenoptimale oplossing minimaliseert die som. Alleen de bestemming noemen vertelt een agent niet hoe hij die moet bereiken.

Formuleer de 8-puzzel

Een bord bevat acht genummerde tegels en een lege plek. Leg alle negen posities vast als de toestand. De begintoestand is de gegeven indeling; het doel is “1 2 3 / 4 5 6 / 7 8 leeg”. Een actie verplaatst de lege plek naar links, rechts, boven of beneden als die zet binnen het bord blijft. De overgang verwisselt de lege plek met de aangrenzende tegel en elke zet kost 1. In een hoek zijn twee acties mogelijk; in het midden vier.

Een oplossing is een reeks zoals “Links, boven, rechts”, als die zetten zijn toegestaan en het doel bereiken. Omdat elke zet evenveel kost, betekent kosten minimaliseren dat je het aantal zetten minimaliseert.

Kies de toestandsruimte

Beschouw toestanden als hoekpunten in een gerichte graaf en acties als kanten met de kosten erbij. Een weg in beide richtingen levert twee gerichte kanten op. Bij het zoeken naar een route kan een toestand de huidige plaats zijn en kunnen de stapkosten de wegafstand in kilometers zijn.

Abstractie laat irrelevante details weg. De muziek in een auto hoeft geen onderdeel te zijn van een routetoestand. Een abstracte oplossing moet nog steeds uitvoerbaar zijn. Als je een detail weglaat dat verandert welke acties zijn toegestaan, verander je het probleem in plaats van alleen de beschrijving te vereenvoudigen.

De formulering kan meer werk besparen dan een snellere wachtrij. Acht dames op willekeurige lege velden plaatsen geeft $64\times 63\times \cdots \times 57\approx \mathrm{1,8}\times {10}^{14}$ mogelijke geordende plaatsingsreeksen. Als je elke volgende dame in de meest linkse lege kolom op een niet-aangevallen veld plaatst, blijven 2.057 bereikbare toestanden over. Dit zijn verschillende constructies met dezelfde doelvoorwaarde.

Genereer mogelijkheden wanneer nodig

De 8-puzzel heeft $9!\mathrm{/}2=181.440$ bereikbare toestanden vanuit een vaste begintoestand. De 15-puzzel heeft er $16!\mathrm{/}2\approx \mathrm{1,05}\times {10}^{13}$. Een volledige representatie van het 8-damesprobleem met één dame per kolom heeft $8^8=\mathrm{16.777.216}$ toestanden.

Zulke ruimten worden meestal impliciet aangeleverd: het zoekalgoritme krijgt een begintoestand en procedures voor acties en overgangen. Het genereert tijdens de uitvoering het relevante deel. Bewaar bij een padprobleem de actiereeks. Bij een optimalisatieprobleem zoals het plaatsen van dames kan de uiteindelijke opstelling zelf het antwoord zijn.

De toestandsruimte beschrijft wat mogelijk is. De zoekboom legt de paden vast die het algoritme heeft geprobeerd. Meerdere knopen kunnen dezelfde toestand beschrijven omdat ze die via verschillende paden hebben bereikt.

Bewaar een pad in een knoop

Een knoop bewaart een toestand, zijn ouderknoop, de actie vanuit die ouder en de padkosten $g(n)$. Ook de diepte kan worden opgeslagen. De wortel heeft geen ouder en heeft padkosten 0. Als je een knoop expandeert, pas je elke toegestane actie toe op zijn toestand en genereer je zijn kinderen.

Op een kaart met wegen in beide richtingen eindigen de paden “S, A” en “S, B, C, A” in dezelfde toestand, maar leveren ze verschillende knopen op. Zelfs een eindige kaart kan een oneindige zoekboom genereren: “S, A, S, A, …” blijft langere paden opleveren.

Het zoekfront, ook wel de grensverzameling genoemd, bevat gegenereerde knopen die op expansie wachten. De verzameling bereikte toestanden legt gegenereerde toestanden en de beste knoop die voor elk is gevonden vast. Ze bevat zowel toestanden die nog op het zoekfront staan als toestanden die al zijn geëxpandeerd. Een gesloten of onderzochte verzameling verwijst meestal alleen naar geëxpandeerde toestanden.

Voer de algemene beste-eerstprocedure uit

1. Plaats de wortel in het zoekfront en de tabel met bereikte toestanden.
2. Meld dat er geen oplossing is als het zoekfront leeg is.
3. Verwijder de knoop met de laagste evaluatiewaarde $f(n)$.
4. Geef die knoop terug als zijn toestand een doel is.
5. Expandeer hem. Voeg elke nieuwe toestand toe; vervang bij een eerder bereikte toestand de opgeslagen knoop alleen als het nieuwe pad goedkoper is.
6. Herhaal vanaf stap 2.

Een goedkoper pad naar een al geëxpandeerde toestand kan vereisen dat je die heropent. Terugkeer tegen gelijke kosten levert geen verbetering op. Bij een heap kan een oude invoer fysiek aanwezig blijven; die moet als verouderd worden herkend en bij verwijdering worden overgeslagen.

De regel voor het zoekfront bepaalt de strategie. Een FIFO-wachtrij selecteert knopen met een kleine diepte voor BFS. Een LIFO-stapel selecteert diepe knopen voor DFS. Prioriteitswachtrijen geordend op $g$, $h$ en $g+h$ geven zoeken op oplopende padkosten, gulzig beste-eerst zoeken en A*-zoeken.

Volg de knopen op de wegenkaart

Gebruik deze wegen in beide richtingen, met afstanden in kilometers: S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2. Begin bij S en zoek G. Handel gelijke waarden alfabetisch af.

Het expanderen van S genereert A met kosten 2, B met kosten 3 en D met kosten 9. Elk heeft ouder S. Het zoekfront bevat A, B en D; de tabel met bereikte toestanden bevat ook S. Later kan C via A worden bereikt tegen kosten 6 of via B tegen kosten 4. Dat zijn twee knopen voor één toestand en de goedkopere moet C vertegenwoordigen.

Om een oplossing te reconstrueren, volg je de ouderverwijzingen van de teruggegeven doelknoop achterwaarts en keer je de acties om. Als je de kosten bijwerkt zonder de ouder bij te werken, blijft een pad over dat niet overeenkomt met de vermelde kosten.

Bepaal wat je onthoudt

Graafzoeken onthoudt bereikte toestanden om herhaald werk te voorkomen. Boomzoeken heeft geen globale tabel met bereikte toestanden; het wijst mogelijk alleen cycli op het huidige pad af. Het bespaart geheugen maar kan dezelfde toestand via veel paden genereren.

De algemene procedure test doelen bij verwijdering. BFS kan bij het genereren testen omdat het genereren de volgorde van diepte volgt. Zoeken op basis van kosten moet wachten tot verwijdering: het eerste gegenereerde doel kan een duurder pad hebben dan een later gevonden doel.

Een algoritme kan betrouwbaar zijn maar toch te duur om uit te voeren. Beoordeel de garanties afzonderlijk van het gebruik van tijd en geheugen en controleer vervolgens of die garanties passen bij het probleem dat je daadwerkelijk moet oplossen.

Stel vier verschillende vragen

Volledigheid betekent dat het algoritme een oplossing vindt wanneer die bestaat. In een eindige bereikbare ruimte kan het uitputten van alle mogelijkheden ook bewijzen dat er geen oplossing is. Een oneindige ruimte zonder oplossing kan eindeloos worden doorzocht, zelfs door een volledig algoritme.

Kostenoptimaliteit betekent dat het algoritme een oplossing met de laagste padkosten teruggeeft. Het zegt niets over hoe snel het algoritme werkt. Een methode kan betrouwbaar een oplossing vinden en toch een dure route teruggeven.

Tijdcomplexiteit telt gegenereerde of geëxpandeerde knopen. Vermeld bij het vergelijken van metingen welke telling wordt gebruikt. Ruimtecomplexiteit meet het maximale aantal knopen dat tegelijk wordt bewaard, inclusief het zoekfront en opgeslagen zoekinformatie.

Bepaal de parameters

Gebruik voor een impliciete zoekruimte:

Voor een expliciete graaf die al in het geheugen staat, zijn aantallen hoekpunten en kanten meestal nuttiger. Een grens voor een doorloop in $\mathrm{\mid }V\mathrm{\mid }$ en $\mathrm{\mid }E\mathrm{\mid }$ beantwoordt een andere vraag dan een grens voor het genereren van een nog onbekende boom.

Zie waarom diepte duur is

Een volledige boom tot en met diepte $d$ bevat

knopen voor $b\mathrm{\ne }1$. Met vertakkingsfactor 10 en diepte 5 zijn dat 111.111 knopen inclusief de wortel. Als je de diepte met één vergroot, voeg je een laag toe met tien keer zoveel knopen als de vorige laag.

Bij één miljoen knopen per seconde en 1 kilobyte per knoop verandert de schaal snel:

Dit zijn decimale opslageenheden: 1 GB is ${10}^9$ bytes. Het geheugen kan een zoekopdracht onmogelijk maken lang voordat de rekentijd onredelijk lijkt.

Lees garanties met hun voorwaarden

BFS bereikt uiteindelijk elke eindige diepte als de vertakking eindig is. DFS kan eindeloos op één oneindige tak blijven en nooit een nabijgelegen doel proberen. Dat verschil verklaart hun resultaten voor volledigheid.

BFS vindt een pad met de minste acties. Als een route van twee stappen 11 km kost en een route van drie stappen 9 km, is de route met de kleinste diepte niet kostenoptimaal. Bij gelijke stapkosten komen diepte en kosten overeen; bij verschillende kosten kunnen ze uiteenlopen.

Een grote-O-grens voor het slechtste geval voorspelt niet elke uitvoering. Twee methoden met dezelfde grens kunnen verschillen in constanten, de afhandeling van duplicaten en het aantal bruikbare takken. Een heuristiek kan een gebruikelijke uitvoering sterk verbeteren zonder het exponentiële slechtste geval weg te nemen.

Breedte-eerst zoeken onderzoekt de ruimte in lagen. De volgende expansie betreft de wachtende knoop met de kleinste diepte, zodat elk pad van één actie wordt overwogen voordat een pad van twee acties wordt geëxpandeerd.

Houd de wachtrij op volgorde

Het zoekfront werkt volgens wie het eerst komt, gaat het eerst: verwijder vooraan en voeg kinderen achteraan toe. Leg toestanden vast wanneer ze worden gegenereerd. Als een kindtoestand al is bereikt, sla je die over; anders zouden twee verschillende ouders dezelfde toestand in de wachtrij kunnen plaatsen.

Test de begintoestand vóór het zoeken. Voor latere knopen kan BFS een vroege doeltest gebruiken bij het genereren. Het eerste gegenereerde doel heeft de kleinste diepte omdat het algoritme kinderen laag voor laag genereert. De volgorde binnen een laag kan bepalen welke van even diepe oplossingen wordt gekozen, maar kan er niet voor zorgen dat een diepere oplossing als eerste verschijnt.

Doorloop de voorbeeldkaart

De wegen in beide richtingen zijn S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2 km. Begin bij S, zoek G en genereer buren alfabetisch. In de tabel staat de volgende te verwijderen knoop links.

Als B wordt geëxpandeerd, zijn C en D al bereikt. Ze krijgen geen nieuwe positie in de wachtrij. Als D G genereert, is de ouderketen G–D–S. Keer die om om S–D–G te reconstrueren, met twee wegen en een totale afstand van $9+2=11$ km.

C is al gegenereerd, maar nog niet geëxpandeerd. De route van C naar G zou drie wegen hebben. BFS kan stoppen zonder die te onderzoeken omdat drie wegen het aantal acties in een oplossing met twee wegen niet kunnen verbeteren.

Weet wat het resultaat minimaliseert

BFS is volledig bij eindige vertakking, zelfs als de ruimte oneindig is: elke eindige laag wordt vóór de volgende verwerkt. Het is kostenoptimaal als alle acties evenveel kosten. In een schuifpuzzel met kosten 1 per zet is een oplossing met de kleinste diepte ook een goedkoopste oplossing.

Op deze wegenkaart kost S–B–C–G $3+1+5=9$ km. BFS geeft de route van 11 km terug omdat afstand niet de ordeningsregel is. “Kortste pad” heeft daarom een eenheid nodig: het kleinste aantal wegen en het kleinste aantal kilometers zijn verschillende doelen.

Houd rekening met geheugen

Met een vroege doeltest gebruikt BFS $O(b^d)$ tijd en ruimte. Het kan vrijwel elke knoop tot en met de doeldiepte genereren en het zoekfront plus informatie over bereikte toestanden bewaren. Als doelen pas bij verwijdering worden getest, kan het expanderen van andere knopen op diepte $d$ knopen op diepte $d+1$ genereren. Dit geeft de gebruikelijke grens $O(b^{d+1})$ voor die versie.

Bij vertakkingsfactor 10 en 1 kilobyte per knoop kost het opslaan van een boom tot en met diepte 10 ongeveer 11 TB. BFS is bruikbaar voor problemen met oplossingen op kleine diepte en gelijke kosten als er genoeg geheugen beschikbaar is, zoals netwerkpaden met de minste verbindingen of puzzels met de minste zetten. Een FIFO-wachtrij gebruikt de numerieke kantkosten niet, zelfs niet als die op de graaf staan.

Zoeken op oplopende padkosten ordent paden op de al gemaakte kosten. Het kan een nabijgelegen maar dure bestemming voorbijgaan terwijl het langere routes met goedkope stappen onderzoekt.

Verwijder het goedkoopste pad

Stel $f(n)=g(n)$ en gebruik een prioriteitswachtrij. Als een expansie een goedkoper pad naar een bereikte toestand vindt, werk je zowel de kosten als de ouder bij. Een pad met gelijke kosten verbetert de opgeslagen gegevens niet. UCS is de zoekvorm van het algoritme van Dijkstra en stopt als het een doel verwijdert.

De late doeltest is essentieel. Een doel genereren bewijst dat er een route bestaat. Dat doel als goedkoopste knoop uit het zoekfront verwijderen bewijst dat geen onvoltooide goedkopere route beter kan zijn, gegeven positieve actiekosten.

Doorloop de voorbeeldkaart

Gebruik de wegen in beide richtingen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2 km. Handel gelijke kosten alfabetisch af. De vermeldingen in het zoekfront hieronder tonen de toestand en de padkosten.

De vervanging van C is doorslaggevend: $3+1=4$ is beter dan $2+4=6$. De ouder van G is C, de ouder van C is B en de ouder van B is S. De teruggegeven route S–B–C–G kost 9 km. D wordt alleen vóór G verwijderd omdat de keuzeregel bij gelijke waarden alfabetisch is.

Als een directe weg S–G van 12 km werd toegevoegd, zou S meteen een doel genereren. Een vroege test zou 12 km teruggeven voordat de route van 9 km wordt ontdekt. De prioriteitswachtrij kan optimaliteit niet beschermen als de stopregel die omzeilt.

Leg de garantie uit

Bij eindige vertakking en actiekosten die allemaal minstens een bepaalde $ϵ>0$ bedragen, passen slechts eindig veel stappen van een pad onder een vaste kostengrens. UCS verwijdert daarom uiteindelijk een doel wanneer dat bestaat. Positieve kosten zorgen ervoor dat een pad niet goedkoper kan worden door het te verlengen, wat het optimaliteitsbewijs ondersteunt.

Kosten van nul vragen aandacht. Boomzoeken kan een cyclus met kosten nul blijven doorlopen. Graafzoeken wijst terugkeer naar dezelfde toestand tegen gelijke kosten af, maar een oneindige keten van verschillende toestanden met begrensde opgetelde kosten kan een doel nog steeds eindeloos uitstellen. Negatieve stapkosten ondermijnen het gebruikelijke optimaliteitsargument voor UCS.

Begrijp de kosten

De standaardgrens voor tijd en ruimte in het slechtste geval is $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. Op deze kaart zijn $C^{\ast }=9$ en $ϵ=1$, wat $O(b^{10})$ geeft. Dit is een ruime grens, niet het werkelijke aantal expansies op de kaart met zes toestanden.

Veel goedkope doodlopende paden kunnen UCS dwingen veel werk te doen voordat het één dure nuttige actie neemt. Als alle stapkosten gelijk zijn, geeft de late doeltest de bekende grens $O(b^{d+1})$. A* met $h=0$ maakt precies dezelfde prioriteitsvergelijkingen als UCS.

Diepte-eerst zoeken volgt eerst één tak voordat het alternatieven probeert. Die keuze kan veel geheugen besparen, maar een ongunstige tak kan alle andere mogelijkheden uitstellen.

Volg een diepe tak

DFS gebruikt een stapel volgens wat er als laatste in gaat, komt er als eerste uit. In een versie met boomzoeken wijs je toestanden af die al op het huidige pad liggen om te voorkomen dat je meteen een cyclus doorloopt. Bewaar het huidige pad en de niet-geëxpandeerde zusterknopen langs dat pad. Om opvolgers met een stapel alfabetisch te proberen, plaats je ze in omgekeerde alfabetische volgorde op de stapel.

Begin op de kaart met wegen in beide richtingen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2 km bij S en zoek G. Als je buren alfabetisch probeert en doelen bij verwijdering test, krijg je S, A, C, B, D, G. Bij C is B de eerste buur die nog niet op het pad ligt. De teruggegeven route S–A–C–B–D–G kost $2+4+1+6+2=15$ km.

DFS is niet kostenoptimaal. Het is volledig in een eindige ruimte met cycluscontrole op het pad, maar kan eindeloos een oneindige tak volgen. De tijdcomplexiteit in het slechtste geval is $O(b^m)$ en de opgeslagen paden en zusterknopen hebben $O(bm)$ ruimte nodig. Backtracking die steeds één kind genereert, vermindert de benodigde opslag tot $O(m)$. Bij vertakkingsfactor 10 en maximale diepte 12 kost opslag van het pad en de zusterknopen ongeveer 120 knopen, tegenover ongeveer een biljoen voor BFS tot en met diepte 12. Een globale tabel met bereikte toestanden zou extra geheugen gebruiken.

Begrens de diepte

Zoeken met een dieptelimiet stopt met expanderen op diepte $\mathrm{\ell }$. Een doel daar kan nog steeds worden herkend. Het onderscheidt drie uitkomsten:

• Er is een oplossing gevonden.
• Afbreking op de dieptelimiet: de dieptelimiet verhinderde een volledige zoekopdracht.
• Geen oplossing: de relevante mogelijkheden zijn uitgeput zonder doel of afbreking op de dieptelimiet.

Een afbreking op de dieptelimiet bewijst niet dat er geen oplossing bestaat. Als het doel met de kleinste diepte op diepte 7 ligt, kan een limiet van 5 het niet bereiken. Tijd en ruimte zijn in het slechtste geval $O(b^{\mathrm{\ell }})$ en $O(b\mathrm{\ell })$.

Verhoog de limiet geleidelijk

Zoeken met iteratieve verdieping, of IDS, voert zoekopdrachten met een dieptelimiet uit met limieten 0, 1, 2 enzovoort. Het vindt een oplossing met de kleinste diepte zonder een zoekfront voor breedte-eerst zoeken op te slaan. Bij eindige vertakking is het volledig; bij gelijke actiekosten is het kostenoptimaal. De tijdcomplexiteit is $O(b^d)$ en de ruimtecomplexiteit $O(bd)$.

De meeste knopen van een brede boom zitten in de laatste laag, dus het herhalen van de bovenste lagen is vaak goedkoop. Tel voor $b=10$ en $d=5$ de gegenereerde knopen onder de wortel:

BFS genereert 111.110 van zulke knopen tot en met diepte 5. IDS genereert ongeveer 11% meer, terwijl het alleen de opslag van diepte-eerst zoeken nodig heeft. De herhaalde bezoeken aan de wortel zijn in beide tellingen niet meegerekend.

Voor vertakkingsfactoren groter dan 1 nadert het extra werk bij een brede boom de factor $b\mathrm{/}(b-1)$. Dit voordeel is kleiner bij een smalle keten, waar herhaalde beginstukken overheersen. IDS is een bruikbare ongeïnformeerde keuze als de oplossingsdiepte onbekend is en een volledig zoekfront niet past. In ruimten met veel routes naar dezelfde toestand kan het ontbreken van een globale verzameling bereikte toestanden ertoe leiden dat veel opnieuw wordt gegenereerd.

Een bruikbare strategie past bij het gewenste resultaat en de beschikbare middelen. Ongeïnformeerd zoeken gebruikt de probleemdefinitie zonder schatting van de resterende afstand. Het kan nog steeds systematisch en zorgvuldig geordend zijn.

Vergelijk dezelfde uitgangspunten

Ga uit van eindige vertakking en de voorwaarden voor positieve kosten bij UCS. De rij voor BFS gebruikt een vroege doeltest; de rij voor DFS gebruikt cycluscontrole op het pad en geen globale tabel met bereikte toestanden.

BFS en IDS minimaliseren ook de kosten als die een niet-dalende functie van alleen de diepte zijn. Het woord “alleen” is van belang: alle paden met een bepaalde diepte moeten dezelfde kosten hebben om aan deze ruimere voorwaarde te voldoen. Positieve kantkosten op zichzelf maken BFS niet kostenoptimaal.

Zoek vanaf beide uiteinden

Bidirectioneel zoeken werkt voorwaarts vanaf de start en achterwaarts vanaf het doel. Als de zoekopdrachten elkaar ongeveer in het midden ontmoeten, bereikt elk ongeveer diepte $d\mathrm{/}2$. Het werk is dan ongeveer $2b^{d\mathrm{/}2}$ in plaats van $b^d$. Bij vertakkingsfactor 10 en oplossingsdiepte 6 is de vergelijking van de grootste lagen ongeveer 2.000 tegenover 1.000.000 knopen.

Hiervoor zijn een expliciete doeltoestand en een manier om voorgangers te genereren nodig. Omkeerbare wegen in beide richtingen maken achterwaartse expansie eenvoudig. Een doeleigenschap zoals “alle dames staan veilig” kan te veel doeltoestanden beschrijven om een handig achterwaarts startpunt te bieden.

Met breedte-eerst zoeken of zoeken op basis van kosten kunnen geschikte regels voor ontmoeting en beëindiging volledigheid en optimaliteit behouden. Stop op een kaart met gewichten pas als geen goedkopere verbinding meer mogelijk is. De eerste overlap tussen de twee zoekopdrachten hoeft niet de goedkoopste verbinding te zijn.

Kies op basis van het probleem

Voor de minste zetten in een kleine schuifpuzzel maken gelijke zetkosten BFS geschikt als er voldoende geheugen is. Kies UCS voor de kortste reisafstand bij ongelijke weglengten en zonder heuristiek. Voor een enorme puzzel met gelijke kosten en onbekende oplossingsdiepte voorkomt IDS een enorm zoekfront. In een eindige ruimte met veel diepe doelen waarbij elke oplossing aanvaardbaar is, kan DFS praktisch zijn. Een bekende start en een bekend doel met omkeerbare acties maken bidirectioneel zoeken het overwegen waard.

Het geheugengebruik moet alles omvatten wat de gekozen versie opslaat. DFS met een globale tabel met bereikte toestanden heeft niet meer hetzelfde opslagprofiel als DFS met boomzoeken. Een uitwerking van BFS met een late doeltest mag je niet vergelijken met een complexiteitsgrens voor een vroege doeltest alsof de versies identiek zijn.

Zelfs de beste ongeïnformeerde keuze kan met exponentiële groei te maken krijgen. Als bruikbare domeinkennis beschikbaar is, kan een heuristiek onnodige exploratie verminderen. Als alleen een uiteindelijke configuratie van belang is, kan lokaal zoeken voorkomen dat een zoekboom moet worden bewaard.

Een heuristiek kent aan een toestand een schatting toe van de laagste resterende kosten naar een doel. Schrijf die als $h(n)$ voor de toestand in knoop $n$. Ze hangt af van de toestand, niet van het pad waarlangs die is bereikt, en is nul in een doel.

Schat wat resteert

De hemelsbrede afstand schat de resterende wegafstand. Op een rooster met horizontale en verticale stappen van één eenheid telt de Manhattanafstand de coördinaatverschillen op:

Van cel (1,1) naar (4,5) geeft dit $3+4=7$ stappen. De hemelsbrede afstand tussen dezelfde coördinaten is $\sqrt{3^2+4^2}=5$. De schattingen beantwoorden verschillende vragen over gerelaxeerde beweging. Een heuristiek moet passen bij de eenheden van de kosten die ze schat; kilometers schatten de reistijd niet rechtstreeks zonder een geschikt omzettingsmodel.

Geïnformeerd zoeken gebruikt een schatting om de expansie te sturen. De schatting hoeft het algoritme niet te vertellen welke actie het moet nemen. Ze beoordeelt de toestanden die de toegestane acties opleveren en de regel voor het zoekfront bepaalt welk wachtend pad vervolgens wordt onderzocht.

Volg de kleinste schatting

Gulzig beste-eerst zoeken stelt $f(n)=h(n)$. De prioriteitswachtrij verwijdert de toestand die het dichtst bij het doel lijkt en negeert de al gemaakte kosten.

Gebruik de wegen in beide richtingen S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2 km. De heuristische schattingen naar G zijn S 8, A 7, B 5, C 4, D 2 en G 0 km.

1. Expandeer S. Het zoekfront bevat A met schatting 7, B met 5 en D met 2.
2. Verwijder D omdat 2 het kleinst is. Expansie van D genereert G met schatting 0. De padkosten naar G zijn $9+2=11$ km.
3. Verwijder G en geef S–D–G terug.

Alleen S en D zijn geëxpandeerd. De route S–B–C–G van 9 km was beschikbaar, maar de schatting 5 voor B leek slechter dan de 2 voor D. Gulzig zoeken nam de 9 km die al was afgelegd om D te bereiken nooit mee in de vergelijking.

Onderscheid sturing van garanties

Zelfs een heuristiek die nooit overschat, maakt gulzig zoeken niet kostenoptimaal. De schattingen in het voorbeeld zijn toelaatbaar, maar toch is de teruggegeven route te duur. Gulzig zoeken gebruikt alleen de resterende schatting en kan dus te veel kosten maken voordat het een veelbelovende toestand bereikt.

Graafzoeken is volledig in een eindige toestandsruimte als het duplicaten goed afhandelt. Gulzig boomzoeken kan blijven rondgaan tussen aantrekkelijke herhaalde toestanden, en een oneindige ruimte kan steeds misleidende lage schattingen blijven bieden. Tijd en ruimte zijn in het slechtste geval $O(b^m)$, hoewel een bruikbare schatting een daadwerkelijke uitvoering kort kan maken.

Een plaats kan hemelsbreed dicht bij een bestemming liggen maar een lange omweg om een rivier vereisen. Kleine heuristische waarden garanderen geen goede totale routes. Het berekenen van de heuristiek kost ook tijd: minder expansies helpen alleen als het berekenen van die schattingen de besparing niet opslokt.

A* beoordeelt de hele voorgestelde reis: de al gemaakte kosten plus een schatting van wat resteert. De prioriteit is

Gebruik een prioriteitswachtrij, vervang duurdere paden en test een doel wanneer het wordt verwijderd. In een doel is $h=0$, dus is de prioriteit gelijk aan de werkelijke padkosten.

Doorloop de regel van kosten plus schatting

De wegen in beide richtingen zijn S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 en D–G 2 km. Heuristische schattingen naar G zijn S 8, A 7, B 5, C 4, D 2 en G 0. Handel gelijke waarden alfabetisch af.

A wordt vóór G verwijderd vanwege de keuzeregel bij gelijke waarden. A* expandeert vier knopen die geen doel zijn en expandeert D nooit. UCS op dezelfde kaart expandeert D ook. Als je elke heuristische schatting op nul zet, valt deze sturing weg en krijg je UCS.

Leg uit waarom een optimistische schatting werkt

Een toelaatbare heuristiek is nooit groter dan de werkelijke resterende kosten $h^{\ast }(n)$. Voor A* met heropening garandeert toelaatbaarheid kostenoptimaliteit; A* als boomzoeken heeft dezelfde garantie onder de zoekvoorwaarden met positieve kosten.

Stel dat een slechter doel met kosten $C>C^{\ast }$ op het punt staat te worden verwijderd. Een knoop op een optimaal pad moet nog wachten. Voor het beginstuk van dat optimale pad geldt:

De wachtrij moet die knoop vóór het slechtere doel kiezen. Dit is in tegenspraak met het voorgestelde stoppunt. Heropening is van belang omdat een later ontdekt goedkoper beginstuk moet kunnen doorgaan via een toestand die al is geëxpandeerd.

Een consistente heuristiek maakt $f$ niet-dalend langs paden. Ze zorgt ervoor dat de eerste expansie van een toestand een goedkoopste pad ernaartoe gebruikt. A* kan geëxpandeerde toestanden dan permanent sluiten. Met alleen toelaatbaarheid kan een permanente gesloten verzameling een essentiële verbetering weggooien.

Begrijp snoeien en de beperkingen ervan

Bij consistentie expandeert A* elke relevante knoop waarvoor $f<C^{\ast }$, kan het knopen expanderen die gelijk zijn aan $C^{\ast }$ en expandeert het vóór het teruggeven geen knopen boven die waarde. De prioriteit 11 van D is groter dan de oplossingskosten 9, dus blijft D ongeëxpandeerd. Binnen de klasse van algoritmen die voorwaarts paden opbouwen met dezelfde heuristische informatie is A* optimaal efficiënt, afgezien van gelijke waarden. Dit is een vergelijking van noodzakelijke expansies, geen bewering dat de code altijd het snelst draait.

Overschatting kan het argument ondermijnen. Verander de schatting voor B in 9 hoewel de werkelijke resterende kosten 6 zijn. B heeft nu prioriteit 12. A* volgt S, A, C en D en geeft S–A–C–G terug tegen kosten 11 terwijl B nog wacht.

A* heeft in het slechtste geval nog steeds exponentiële complexiteit en slaat gegenereerde zoekinformatie op.

Als het zoekfront niet meer past of een antwoord te langzaam komt, kies je welke middelen of garantie je wilt inruilen. Varianten gericht op snelheid veranderen prioriteiten of gooien kandidaten weg. Varianten gericht op geheugen genereren paden opnieuw die ze niet konden bewaren.

Geef de schatting meer gewicht

Gewogen A* gebruikt $f=g+Wh$ met $W>1$. Het geeft meestal meer voorkeur aan voortgang naar een doel. Met een toelaatbare heuristiek en de bijwerkingen voor het beste pad en heropening uit de algemene procedure zijn de teruggegeven kosten maximaal $W{C}^{\ast }$. Die grens staat een slechtere oplossing toe, maar vereist die niet.

Gebruik op de voorbeeldwegenkaart de schattingen S 8, A 7, B 5, C 4, D 2 en G 0, en gewicht 2. Vanuit S zijn de prioriteiten B 13, D 13 en A 16. Bij gelijke waarden wordt alfabetisch B gekozen. Het kind C heeft $4+2(4)=12$; C genereert vervolgens G met prioriteit 9. De route met kosten 9 wordt teruggegeven na drie expansies van knopen die geen doel zijn. De garantie staat maximaal 18 km toe, hoewel deze uitvoering de optimale oplossing vindt.

In dezelfde formule geeft gewicht 0 UCS en gewicht 1 A*. Naarmate het gewicht groter wordt, gaat de schatting de vergelijkingen steeds meer overheersen en nadert het gedrag dat van gulzig zoeken.

Bundelzoeken bewaart alleen de beste $k$ wachtende knopen en gooit de rest weg. Het bewaarde zoekfront is begrensd, maar een weggegooide kandidaat kan de enige oplossing bevatten. De methode biedt daarom noch volledigheid noch een optimaliteitsgarantie.

Verdiep op basis van een grens voor geschatte kosten

IDA* voert diepte-eerst zoeken uit met een grens voor $f=g+h$. De eerste grens is de waarde van de wortel. Snoei elke knoop boven die grens weg en noteer de kleinste overschreden waarde. Die waarde wordt de volgende grens; die is niet noodzakelijk de oude grens plus 1. Gebruik cycluscontrole op het pad.

Voor de voorbeeldkaart is de eerste grens 8. A met 9 en D met 11 worden weggesnoeid; B en C met 8 worden onderzocht, maar G met 9 wordt weggesnoeid. De volgende grens is 9. In die iteratie levert het pad via A een C met 10 op en wordt het weggesnoeid. Het pad S–B–C–G blijft binnen 9 en slaagt.

Bij toelaatbaarheid behoudt IDA* kostenoptimaliteit en heeft het alleen de padopslag van diepte-eerst zoeken nodig. De herhaalde doorlopen kunnen duur zijn als de kosten veel verschillende grenswaarden opleveren. Kleine gehele kosten maken het aantal grenswaarden vaak beter beheersbaar.

Gebruik begrensd geheugen selectiever

Recursief beste-eerst zoeken (RBFS) slaat op elk niveau de beste alternatieve prioriteit op. Het volgt de meest veelbelovende tak totdat dat alternatief beter wordt en keert dan terug. Het gebruikt lineair geheugen maar kan vergeten takken opnieuw genereren.

SMA* gebruikt het beschikbare geheugen, verwijdert het slechtste blad van het zoekfront als het geheugen vol is en geeft de waarde terug aan de ouder. Met deze informatie kan het blad later opnieuw worden gegenereerd. Met een toelaatbare heuristiek is het kostenoptimaal als een optimaal oplossingspad in het geheugen past. Anders kan het een slechtere oplossing teruggeven of geen oplossing vinden als geen oplossingspad past.

Kies A* voor een optimaal antwoord als de opslagruimte volstaat. Kies IDA* of een geschikte variant met geheugenlimiet als optimaliteit van belang is maar het zoekfront niet past. Gewogen A* biedt een numerieke kwaliteitsgrens; bundelzoeken biedt sterke snoei zonder die grens.

Een heuristiek kan over het geheel genomen optimistisch zijn en toch te sterk veranderen tussen aangrenzende toestanden. Toelaatbaarheid en consistentie leggen deze verschillende controles vast en elk ondersteunt een andere versie van A*.

Vergelijk schattingen met werkelijke kosten

Een toelaatbare heuristiek voldoet in elke toestand aan $0\le h(n)\le h^{\ast }(n)$. In een doel zijn de werkelijke resterende kosten nul, dus moet ook de schatting nul zijn. Toelaatbaar betekent niet nauwkeurig: overal nul is veilig maar geeft geen richting.

Op de voorbeeldwegenkaart zijn de schattingen en exacte laagste resterende afstanden naar G:

Elke schatting is hoogstens gelijk aan de werkelijke kosten. Bij een groot probleem kan het berekenen van deze exacte kosten even moeilijk zijn als de oorspronkelijke zoekopdracht. Een bewijs op basis van de structuur van het probleem is dan nuttiger dan een uitputtende tabel.

Controleer elke actie

Consistentie, ook wel monotoniciteit genoemd, vereist $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ voor elke actie, en nul in doelen. De huidige schatting mag niet groter zijn dan de kosten van één stap plus de schatting van de opvolger.

Op de wegenkaart geeft A→C $7\le 4+4$, C→B geeft $4\le 1+5$ en D→G geeft $2\le 2+0$. Wegen in beide richtingen vereisen controle van beide richtingen. Alle 16 gerichte controles slagen voor deze schattingen.

Als je de ongelijkheden langs een pad naar een doel optelt, vallen de tussengelegen schattingen weg. Op een optimaal pad geeft dit $h(n)\le h^{\ast }(n)$, dus impliceert consistentie toelaatbaarheid. Het geeft ook

Prioriteiten kunnen niet dalen langs een pad. De eerste expansie van een toestand vindt daarom plaats via een goedkoopste pad, ook als die toestand eerst via een duurder pad werd gegenereerd.

Zie waarom alleen toelaatbaarheid heropening vereist

Bekijk de wegen in beide richtingen S–A 1, A–C 1, S–B 1, B–C 2 en C–G 3. Laat de schattingen S 0, A 4, B 1, C 1 en G 0 zijn. Ze zijn niet groter dan de werkelijke kosten S 5, A 4, B 5, C 3 en G 0, dus zijn ze toelaatbaar. Maar A→C schendt de consistentie: $4>1+1$.

A* expandeert S, dan B met prioriteit 2, dan C bereikt tegen kosten 3 met prioriteit 4. Daarna expandeert het A met prioriteit 5 en ontdekt het een goedkoper pad naar C met kosten 2. Als C permanent wordt afgewezen omdat die gesloten is, blijft een doel met kosten 6 over. Heropening van C geeft de verbetering door en levert de optimale oplossing met kosten 5 op.

Stem af op het bewegingsmodel

De Manhattanafstand is toelaatbaar en consistent voor horizontale en verticale stappen van één eenheid. Als diagonale stappen ook 1 kosten, zijn voor de reis van (0,0) naar (3,3) slechts drie stappen nodig, terwijl de Manhattanafstand 6 aangeeft. Voor dat bewegingsmodel geeft $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ de afstand zonder obstakels. De garantie van een heuristiek hoort bij een bepaald actiemodel.

Los een eenvoudigere versie van het probleem op om een veilige schatting te ontwerpen. Een gerelaxeerd probleem neemt beperkingen op acties weg, zodat elke oorspronkelijke oplossing beschikbaar blijft. De laagste kosten ervan kunnen niet hoger zijn dan de oorspronkelijke laagste kosten.

Neem gericht beperkingen weg

Exacte gerelaxeerde kosten vormen een toelaatbare heuristiek. Die is ook consistent als de oorspronkelijke acties met hun kosten beschikbaar blijven: een oorspronkelijke stap nemen en daarna een optimale gerelaxeerde route volgen is één mogelijke gerelaxeerde route, dus het gerelaxeerde optimum kan niet meer kosten.

In de 8-puzzel kan een tegel alleen naar een aangrenzend veld bewegen als dat veld leeg is. Neem de eis van een leeg veld weg en tegels mogen door bezette velden bewegen. Elke genummerde tegel heeft dan minstens zijn horizontale plus verticale afstand tot het doel nodig. Optellen geeft de Manhattanafstand, $h_2$.

Neem ook de eis van aangrenzende velden weg en elke verkeerd geplaatste tegel kan in één zet rechtstreeks naar zijn doel springen. De resulterende kosten zijn het aantal verkeerd geplaatste tegels, $h_1$. Beide zijn eenvoudig te berekenen zonder de oorspronkelijke puzzel te doorzoeken.

Werk beide schattingen uit

Bekijk voor doel “1 2 3 / 4 5 6 / 7 8 leeg” de toestand “5 1 3 / 4 leeg 2 / 7 8 6”. Nummer rijen en kolommen vanaf 1.

De andere genummerde tegels liggen al goed. Vier liggen verkeerd, dus $h_1=4$. Hun afstanden tellen op tot $2+1+2+1=6$, dus $h_2=6$. De optimale oplossing kost 12 zetten; de relaxaties negeren interacties die extra werk veroorzaken.

Tel de lege plek niet mee. Op één zet van het doel zijn een genummerde tegel en de lege plek allebei verplaatst. Beide meetellen zou 2 geven terwijl de werkelijke kosten 1 zijn. De lege plek maakt zetten mogelijk; het is geen extra tegel waarvoor je kosten rekent.

Sla opgeloste deelproblemen op

Een patroondatabase legt exacte kosten vast voor een gekozen deelprobleem, zoals tegels 1 tot en met 4 goed plaatsen terwijl de andere tegels als onderling uitwisselbaar worden behandeld. Bouw de tabel één keer op door achterwaarts vanaf het doel te zoeken. Gebruik tijdens een nieuwe zoekopdracht een opzoeking in plaats van het deelprobleem opnieuw op te lossen.

Het deelprobleem heeft niet meer werk nodig dan het volledige probleem en geeft daarmee een ondergrens. Maar als je twee gewone patroonkosten optelt, kun je dezelfde werkelijke zet tweemaal in rekening brengen. Optellen is veilig voor disjuncte patronen als elke database alleen zetten van de eigen tegels telt. Verschillende tegelbenamingen op zichzelf leggen die regel voor kostentoerekening niet vast.

Combineer veilige schattingen

Het maximum van toelaatbare schattingen is toelaatbaar:

Elke kandidaat blijft onder de werkelijke resterende kosten, dus hun maximum ook. Het is minstens zo informatief als elke afzonderlijke schatting. Een gewone som heeft deze bescherming niet.

Een heuristiek die uit opgeloste voorbeelden is geleerd, kan de resterende kosten gemiddeld goed voorspellen. Gemiddelde nauwkeurigheid bewijst geen ondergrens voor elke toestand. De heuristiek behoudt de garantie van A* voor een toelaatbare heuristiek alleen als wordt aangetoond dat haar schattingen nooit overschatten.

Een schatting die dichter bij de werkelijke waarde ligt, kan exploratie verminderen, maar een dure schatting kan het zoeken toch vertragen. Vergelijk zowel de geboden informatie als de totale benodigde berekening.

Stel dominantie vast voor elke toestand

Een toelaatbare heuristiek $h_2$ domineert de toelaatbare $h_1$ als overal $h_2(n)\ge h_1(n)$ geldt. Eén gunstig bord is niet genoeg om deze verhouding te bewijzen.

De Manhattanafstand domineert het aantal verkeerd geplaatste tegels in de 8-puzzel. Elke verkeerd geplaatste tegel moet minstens één veld afleggen, dus is zijn bijdrage aan de Manhattanafstand minstens de 1 die de zwakkere heuristiek telt. Een goed geplaatste tegel draagt bij beide nul bij.

Met consistente schattingen moet A* paden expanderen waarvoor $g+h<C^{\ast }$. Als je een veilige schatting verhoogt, vallen sommige paden buiten dit verplichte gebied. Een dominerende consistente heuristiek expandeert niet meer knopen, afgezien van verschillen bij gelijke waarden. Een ontoelaatbare schatting kan nog groter zijn, maar verliest de optimaliteitsgarantie en komt niet in aanmerking voor deze vergelijking op dominantie.

Vat de zoekinspanning samen

De effectieve vertakkingsfactor, $b^{\ast }$, beschrijft de breedte van een equivalente uniforme boom. Tel $N$ gegenereerde knopen onder de wortel en laat de oplossingsdiepte $d$ zijn. Los op:

De extra 1 staat voor de wortel. Consistent tellen is belangrijk: als een meting de wortel al omvat, tel die dan niet tweemaal mee.

Voor 52 gegenereerde knopen onder de wortel en oplossingsdiepte 5 is het totaal 53 en $b^{\ast }\approx \mathrm{1,92}$. Voor 1.000 gegenereerde knopen en diepte 8 is $b^{\ast }\approx \mathrm{2,20}$. Bepaal deze waarden numeriek door een proefwaarde te verhogen of te verlagen totdat de meetkundige som overeenkomt met het totale aantal knopen.

Een waarde dicht bij 1 wijst op een smalle zoekopdracht. Vergelijk resultaten voor representatieve instanties met dezelfde telregel en vergelijkbare oplossingsdiepten. De effectieve vertakkingsfactor kan helpen de schaalbaarheid te schatten, maar een ongewoon eenvoudige instantie is geen betrouwbare voorspelling voor een hele probleemfamilie.

Meet de tijd van de hele berekening

Stel dat een knoop 10 microseconden kost, inclusief 1 microseconde om de oude heuristiek te berekenen. Een vervanger halveert het aantal knopen maar kost 100 microseconden per berekening. Het werk buiten de heuristiek kost nog steeds 9 microseconden, dus zijn de nieuwe totale kosten per knoop 109. De verhouding tussen de totale tijden is

Het zoeken is ongeveer 5,5 keer zo langzaam ondanks het kleinere aantal bezochte knopen. Als de nieuwe berekening slechts 2 microseconden kost, worden de totale kosten per knoop 11 en is de tijdverhouding $\mathrm{0,5}\times 11\mathrm{/}10=\mathrm{0,55}$. Dat is ongeveer 1,8 keer zo snel.

Een patroondatabase heeft ook opbouwkosten. Veel zoekopdrachten met hetzelfde doel kunnen die investering delen; één kleine zoekopdracht verdient die mogelijk niet terug. Meet voorbewerking, opzoektijd, gegenereerde knopen en geheugen afzonderlijk, zodat je minder expansies niet verwart met een automatische snelheidsverbetering.

Lokaal zoeken verandert herhaaldelijk een volledig kandidaatantwoord. Het past bij taken waarbij de uiteindelijke configuratie van belang is en de reeks stappen om die te vinden kan worden weggegooid.

Geef een volledige kandidaat weer

Plaats voor het 8-damesprobleem één dame in elke kolom. Geef de toestand weer met de acht rijnummers, waarbij je de kolommen van links naar rechts leest. Elke toestand bevat alle acht dames, ook toestanden met conflicten. Bij een stap naar een buurtoestand gaat één dame naar een andere rij in haar eigen kolom.

Er zijn $8^8=\mathrm{16.777.216}$ toestanden en $8\times 7=56$ buurtoestanden per toestand. Een vast aantal huidige toestanden vervangt het grote zoekfront en de oudergegevens van zoeken naar een pad. De benodigde opslag hangt nog steeds af van de omvang van een toestand; één tuple met acht elementen bewaren kost minder ruimte dan één enorm rooster bewaren.

Roosters maken, chips ontwerpen en een volledige rondreis langs steden kiezen hebben hetzelfde algemene patroon: elke toestand is een volledig voorstel. Een rondreis is zelf een kandidaatopstelling, ook al beschrijft de inhoud een reis. Lokaal zoeken hoeft de reeks wijzigingen waarmee die rondreis is verbeterd niet te bewaren.

Bepaal wat beter betekent

Een doelfunctie geeft elke toestand een score die je wilt maximaliseren. Je kunt ook kosten definiëren die je wilt minimaliseren. Laat voor het n-damesprobleem $h$ paren dames tellen die elkaar aanvallen. Tel elk paar één keer, inclusief aanvallen langs rijen of diagonalen wanneer er een andere dame tussen staat. Een oplossing heeft $h=0$.

Voor vier kolommen plaatst de tuple (1,2,3,4) alle dames op één diagonaal. Alle $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ paren vallen elkaar aan. De tuple (2,1,3,4) heeft twee aanvallende paren, terwijl (2,4,1,3) er geen heeft. Hier zijn lagere waarden beter; de letter $h$ staat voor de te minimaliseren kosten, niet voor een schatting van de resterende padkosten zoals bij A*.

Lees het landschap

Stel je de kwaliteit van een toestand voor als hoogte. Bij maximalisatie geldt:

• Een globaal maximum heeft de beste waarde in de hele ruimte.
• Een lokaal maximum is beter dan zijn buurtoestanden maar kan slechter zijn dan een verder gelegen toestand.
• Een plateau is een aaneengesloten vlak gebied. Het kan een vlak lokaal maximum zonder uitgang omhoog zijn, of een schouder vanwaar zijwaartse stappen een uitgang omhoog kunnen bereiken.
• Een bergkam kan stijgen in een richting die de beschikbare afzonderlijke stappen niet kunnen volgen. Elke onmiddellijke keuze kan slechter lijken.

Bij het minimaliseren van kosten keer je de hoogte om: het zoeken richt zich op minima en dalen. Een lokaal minimum bewijst niet dat elders geen toestand met lagere kosten bestaat. De buurt bepaalt welke toestanden in één stap kunnen worden vergeleken, dus een andere toegestane wijziging kan veranderen waar het zoeken vastloopt.

Controleer of je het pad kunt negeren

Een agent die een route zoekt, moet toegestane acties teruggeven vanaf zijn werkelijke start. Een goede bestemming alleen is onvoldoende. Lokaal zoeken geeft meestal alleen de kandidaattoestand terug, zonder ouderketen langs alle eerdere wijzigingen.

Een volledige lokale zoekmethode zou een doel vinden wanneer dat bestaat; een optimale methode zou het globale beste vinden. Elementaire lokale methoden bieden geen van beide garanties in het algemeen. Hun aantrekkingskracht is dat ze snel goede kandidaten kunnen bereiken wanneer het opslaan van een systematische zoekboom onpraktisch is.

Heuvelklimmen maakt de beste onmiddellijke verbetering die het kan vinden. Voor een te maximaliseren score kiest de steilste stijging de buurtoestand met de hoogste score. Voor te minimaliseren kosten kiest de methode de buurtoestand met de laagste kosten. Ze stopt als er geen strikte verbetering bestaat.

Volg een uitvoering voor vier dames

Laat een toestand de rij van de dame in elke kolom vermelden en laat $h$ aanvallende paren tellen. Begin met (1,2,3,4), met kosten 6.

1. Beoordeel de zetten met één dame. Een beste buurtoestand is (2,2,3,4), met kosten 4.
2. Van daaruit is een beste buurtoestand (2,1,3,4), met kosten 2.
3. Geen buurtoestand door een zet met één dame heeft kosten onder 2. Strikt heuvelklimmen stopt.

De opstelling (2,4,1,3) met kosten nul bestaat, maar kan vanuit de toestand waarin het zoeken stopte niet met één onmiddellijk verbeterende stap worden bereikt. Dit is een gevolg van de lokale regel, geen bewijs dat het programma conflicten verkeerd heeft geteld.

Sta nuttige zijwaartse beweging toe

Een zijwaartse stap behoudt dezelfde score. Die kan een schouder oversteken naar een uitgang die verbetering oplevert, maar kan ook rondzwerven op een vlak lokaal optimum. Beperk opeenvolgende zijwaartse stappen om eindeloze cycli te voorkomen.

In het door Russell en Norvig beschreven experiment met het 8-damesprobleem slaagt de steilste stijging vanuit willekeurige begintoestanden ongeveer 14% van de keren, met ongeveer 4 stappen bij succes en 3 bij vastlopen. Als maximaal 100 opeenvolgende zijwaartse stappen worden toegestaan, stijgt het gemelde succes naar ongeveer 94%, met ongeveer 21 stappen per succes en 64 per mislukking. Dit zijn resultaten van dat experiment, geen universele slagingspercentages voor heuvelklimmen.

Verander hoe een buurtoestand wordt gekozen

Stochastisch heuvelklimmen kiest willekeurig een verbeterende buurtoestand, eventueel met een voorkeur voor grotere verbeteringen. Heuvelklimmen met de eerste verbetering trekt steeds één buurtoestand en neemt de eerste verbetering. Zo hoeft de methode niet vóór elke stap een enorme buurt te beoordelen. Beide wijzen slechtere stappen nog steeds af.

Heuvelklimmen met willekeurige herstarts begint na een mislukte poging een nieuwe poging vanuit een nieuw getrokken toestand. Bij onafhankelijke pogingen met slagingskans $p$ is het verwachte aantal pogingen tot en met het eerste succes $1\mathrm{/}p$. Voor $p=\mathrm{0,14}$ zijn dat ongeveer 7 pogingen. Met de gemelde aantallen stappen is het verwachte totale aantal stappen

De mislukte pogingen leveren ook werk op. Bij een positieve slagingskans en onafhankelijke herstarts nadert de kans om uiteindelijk te slagen 1 naarmate het aantal pogingen groeit.

Laat meerdere kandidaten ontdekkingen delen

Lokaal bundelzoeken bewaart $k$ toestanden, genereert hun buurtoestanden gezamenlijk en behoudt de beste $k$ uit die samengevoegde verzameling. Een veelbelovende ouder kan meerdere overblijvende toestanden leveren, terwijl een andere er geen levert. Dit delen onderscheidt de methode van onafhankelijke herstarts.

Samenvoegen kan er ook voor zorgen dat alle kandidaten zich in één gebied concentreren. Stochastisch bundelzoeken trekt overblijvende toestanden met een kans die toeneemt met de kwaliteit om meer variatie te behouden. De keuze tussen zijwaartse stappen, herstarts en variatie in de populatie hangt af van de reden waarom de voortgang stokt: een nabijgelegen brug van gelijke waarden, een slecht begingebied of te veel kandidaten die hetzelfde gebied verkennen.

In sommige landschappen is tijdelijk verlies nodig voordat een betere toestand bereikbaar wordt. Gesimuleerd afkoelen staat zulke stappen toe met een beheerste kans. Genetische algoritmen verkennen de ruimte door volledige kandidaten te selecteren en te combineren.

Accepteer soms een slechtere stap

Gesimuleerd afkoelen trekt één willekeurige buurtoestand. Accepteer een verbeterende stap. Schrijf voor een te maximaliseren doelfunctie de verandering als $\mathrm{\Delta }E$. Als $\mathrm{\Delta }E<0$, accepteer je de slechtere stap met kans

Laat bij het minimaliseren van kosten $\mathrm{\Delta }$ de toename van de kosten zijn. Een slechtere stap heeft dan $\mathrm{\Delta }>0$ en acceptatiekans $e^{-\mathrm{\Delta }\mathrm{/}T}$. Stappen met gelijke waarde hebben volgens beide formules kans 1. Temperatuur en veranderingen in de doelfunctie moeten een passende numerieke schaal gebruiken.

Een scoredaling van 2 wordt geaccepteerd met kans ongeveer 0,819 bij temperatuur 10, 0,135 bij temperatuur 1 en 0,018 bij temperatuur 0,5. Bij temperatuur 10 heeft een grotere daling van 5 een kans van ongeveer 0,607. De temperatuur bepaalt dus de tolerantie, terwijl de omvang van het verlies bij dezelfde temperatuur van belang blijft.

Verlaag de temperatuur

Een afkoelschema bepaalt de temperatuur in de loop van de tijd. Meetkundig afkoelen gebruikt $T_{k+1}=\alpha T_k$ met een factor dicht bij 1, zoals 0,95. Bij hoge temperatuur worden veel slechtere stappen geaccepteerd en lijkt de exploratie op een willekeurige wandeling. Dicht bij nul worden slechtere stappen zeldzaam en lijkt het gedrag op heuvelklimmen.

Te snel afkoelen kan het zoeken laten vastlopen voordat het een slecht gebied heeft verlaten. Zeer langzaam afkoelen vergroot de hoeveelheid rekenwerk. Het asymptotische resultaat voor het globale optimum vereist voldoende langzaam afkoelen en de gebruikelijke mogelijkheid om toestanden via de buurt te bereiken; een gewone eindige meetkundige uitvoering biedt geen zekerheid op globaal succes. De methode wordt sinds de jaren 1980 gebruikt voor chipontwerp en planning en ontleent haar naam aan het verhitten en langzaam afkoelen van metaal, zodat het een structuur met lagere energie aanneemt.

Bouw een nieuwe populatie op

Een genetisch algoritme geeft kandidaten weer als tekenreeksen. Elke generatie beoordeelt het hun fitness, selecteert het ouders met een voorkeur voor hogere fitness, maakt het kinderen door kruising en past het af en toe mutaties toe.

Voor het 8-damesprobleem beschrijven acht rijcijfers één dame per kolom. Fitness kan paren tellen die elkaar niet aanvallen, met 28 als maximum. Splits de ouderreeksen “64751517” en “64278273” na het vierde cijfer. Het combineren van tegenoverliggende helften geeft “64758273” en “64271517”.

De ouders hebben fitness 23 en 24; de kinderen hebben fitness 27 en 21. Eén kind is beter dan beide ouders, terwijl het andere slechter is. Kruising biedt nieuwe combinaties, geen garantie op verbetering. Ze is nuttig als goede bouwstenen bij combinatie meestal hun waarde behouden. Mutatie verandert af en toe een positie en helpt variatie toe te voegen buiten die combinaties.

Selectie, kruising en mutatie hebben verschillende rollen: selectie geeft voorkeur aan bruikbare kandidaten, kruising combineert ze opnieuw en mutatie verandert afzonderlijke posities. Net als stochastisch bundelzoeken houdt de methode een populatie bij, maar nieuwe kandidaten kunnen materiaal uit twee ouders putten. Noch een ouder met hoge fitness, noch een lage eindtemperatuur bewijst op zichzelf dat het globale optimum is gevonden.