heuristiek

Ik denk dat deze moeilijk te definiëren zijn, dus ik begin met de openingsregel van Wikipedia over het onderwerp:

in de informatica, kunstmatige intelligentie en wiskundige optimalisatie is een heuristische techniek (van het Griekse ερρίσκω “ik vind, ontdek”) een techniek die ontworpen is om een probleem sneller op te lossen wanneer klassieke methoden te traag zijn, of om een benaderende oplossing te vinden wanneer klassieke methoden geen exacte oplossing vinden. Dit wordt bereikt door de handel optimaliteit, volledigheid, nauwkeurigheid, of precisie voor snelheid. In zekere zin, het kan worden beschouwd als een kortere weg.

Is dat nuttig? Snap je het? Omdat ik het niet begrijp. Ik bedoel, ik snap het een beetje, en het is een accurate beschrijving, maar als dit de eerste was die je ooit hoorde over een heuristiek, Weet ik niet zeker of je het volledige beeld zou krijgen van wat heuristiek hiervan is. Misschien als ik je vertel over A* ‘ S pathfinding heuristic, krijg je een beter begrip.

met Dijkstra ‘ s algoritme lag de focus op één waarde: de kortste afstand van de startIndex. Wat, als je erover nadenkt, een beetje vreemd is. Dit algoritme probeert nieuwe, kortere paden naar een bepaalde bestemming te vinden, maar de focus ligt altijd op waar het begon. Stel je voor dat iemand boodschappen gaat doen, maar de hele weg achteruit loopt, probeert een oogje op hun huis te houden tot ze bij de winkel zijn. In het echte leven zou dit waarschijnlijk niet werken, maar misschien als je ze de tijd geeft om door de hele stad te gaan, zou het uiteindelijk kunnen werken.

uitgaande van deze goofy analogie, is A* anders dan Dijkstra ‘ s omdat het suggereert om te draaien en vooruit te lopen. A* houdt net als die van Dijkstra ook bij hoe ver het van huis is, maar het unieke is dat het ook bijhoudt hoe ver het van zijn bestemming is. Bij het maken van zijn volgende stap zal Dijkstra ‘ s kijken welk pad momenteel het kortst is, maar A* gaat een stap verder en gaat ook na of die stap dichter bij zijn doel komt. Simpeler, A* heeft een ruwe schatting van de resterende afstand tot zijn doel, en wanneer die schatting dichter bij nul komt, weet het dat het in de juiste richting beweegt. Dit is de heuristische die we zullen gebruiken in onze voorbeelden.

stap door het algoritme

Dit zal een vrij eenvoudig voorbeeld zijn, maar het zou je de basisstroom en herhaling van het algoritme moeten laten zien. Ik zal ervoor zorgen om links in mijn verwijzingen naar andere, meer gecompliceerde voorbeelden, maar dit moet een goede primer voor die. Ik zal een set-up gebruiken die vergelijkbaar is met hoe ik Dijkstra ‘ s heb gedemonstreerd.

nog een verschil tussen Dijkstra ’s en A* is dat Dijkstra’ s direct met looping kan beginnen, maar A* moet een kleine set-up doen voor zijn startpunt. Dus laten we dat nu doen, en een beetje een idee krijgen van hoe de tafel gaat werken.

eerst voegen we A toe aan de open set. Ten tweede, We zullen A ‘ S afstand vanaf het begin uitzoeken. Natuurlijk is de afstand van A tot A nul, dus dat wordt toegevoegd aan de tabel, en Ik zal dat het nummer in de linkerbovenhoek van het vierkant van A hebben. Ten derde bepalen we de heuristische afstand. We kunnen dit op verschillende manieren doen, het enige dat belangrijk is, is dat we deze afstand op dezelfde manier meten voor elk vierkant. Ik ga een “hemelsbreed” afstand gebruiken voor alle heuristische afstanden, wat betekent dat ik opnieuw gebruik kan maken van de Stelling van Pythagoras. In dit geval berekenen we √(202 + 302), en vinden dat A is een afstand van 36.0555127546… van L (Ik zal rond decimalen naar de dichtstbijzijnde tiende om ruimte te besparen). Ik voeg dit toe aan de tafel, en plaats het in de rechterbovenhoek van A ‘ S vierkant. Eindelijk, de som. Ik voeg de kortste afstand van het begin toe aan de heuristische afstand, voeg het toe aan de tafel en plaats het in het midden van het vierkant van A.

dat is ons uitgangspunt, en we kunnen nu naar de buren van A kijken, en hun waarden aan de tabel toevoegen.

eerst voegen we B, E en F toe aan de open set. Vervolgens kunnen we hun Kortste afstanden vanaf het begin vinden, en omdat alles één stap vanaf het begin is, zullen het gewoon 10 ‘ s zijn voor B en E, en 14 voor de diagonale beweging naar F. voor de heuristische afstand, zullen we de Stelling van Pythagoras gebruiken van elk vierkant tot het eindpunt. Tot slot krijgen we hun sommen, en voegen ” A ” toe aan elk van hun vorige vertex kolommen.

op dit punt hebben we alles gedaan wat we nodig hebben met A, dus het wordt verplaatst naar de gesloten set, en we hebben een nieuwe huidige vertex nodig. Om te bepalen welk hoekpunt de volgende keer onderzocht moet worden, kijken we naar de open verzameling, en vinden we het hoekpunt met de laagste Som. Op dit moment is dat F met een som van 36,1. Dus, we maken het de huidige vertex, en beginnen met het uitwerken van de waarden voor de buren.

f heeft acht buren, maar slechts vijf worden hier gewijzigd. Ten eerste, A is nu in de gesloten set, dus het kan nu niet worden veranderd. Voor de overige zeven voegen we ze toe aan de open set (tenzij ze er al deel van uitmaken), en laten we dan vanaf het begin aan hun afstanden werken. Dit gaat veel werken zoals Dijikstra ‘ s algoritme, en we zullen de afstand van F vanaf het begin toevoegen aan de afstand van elk van de buren tot F. Op onze tafel is de afstand van F vanaf het begin 14, dus we zullen 14+10=24 of 14+14=28 invullen voor deze. B en E hebben echter al kortere afstanden tot de start, dus hun tabelrecords worden niet bijgewerkt. Dat laat vijf hoekpunten die worden bijgewerkt, met C, I, en K krijgen 28, en G en J krijgen 24 voor hun afstand vanaf het begin. Gebruik vervolgens de Stelling van Pythagoras voor de heuristische afstanden van elk van deze hoekpunten, bereken dan hun sommen, en voeg ten slotte “F” toe aan de vorige vertex kolom voor de hoekpunten die werden bijgewerkt.

F is voltooid en zal worden verplaatst naar de gesloten verzameling, en een nieuw huidige hoekpunt zal worden gekozen op basis van welk hoekpunt in de Open verzameling de laagste Som heeft. Het is heel dichtbij, maar K is een tiende kleiner (en ja, dit komt door een afrondingsverschil, maar in dit geval blijkt het een goede tie breaker te zijn). K zal het nieuwe hoekpunt zijn om te onderzoeken, Dus laten we beginnen door naar de buren te kijken.

k heeft zes buren, waarvan er drie al in de open verzameling staan, dus de laatste twee h en L zullen ook aan de open verzameling worden toegevoegd. We berekenen hun afstanden vanaf het begin. K ‘ S afstand vanaf het begin is 28, dus we zullen werken met 28 + 10 = 38 voor G, J En L, en 28+14=42 voor H. echter, G en J hebben al kleinere afstanden om te starten, dus ze zullen niet worden bijgewerkt. We vinden de heuristische afstanden voor elk, berekenen hun sommen, en voegen “K” toe aan elke vorige vertex die werd bijgewerkt.

K is voltooid en verplaatst naar de gesloten verzameling, en het volgende hoekpunt in de Open met de kleinste som is L, onze bestemming!

Nu, dat L de huidige vertex, het algoritme eindigt, en kunnen we gebruik maken van onze tafel te sporen het pad terug naar het begin:

• L de eerdere vertex is K
• K ’s eerdere vertex is F
• F’ eerdere vertex is Een, het starten van vertex.

dus, dit betekent dat de kortste weg een > F > K > L.

het analyseren van de resultaten

vergeleken met Dijkstra ‘ s algoritme, heeft A* nogal een puinhoop achtergelaten. Laten we eens kijken naar een paar vreemde punten. Vanaf het begin, kijk naar vertex C en de afstand tot de start: 28. Dat lijkt vreemd omdat A en C slechts twee horizontale bewegingen van elkaar verwijderd zijn, dus de Kortste Afstand zou 20 moeten zijn. Op dit moment lijkt C te denken dat zijn kortste pad naar A twee diagonale bewegingen is door F.

wanneer Dijkstra ‘ s algoritme klaar is, zou het een zeer complete tabel van afstanden vanaf het beginpunt moeten geven. Omgekeerd heeft een * ‘S tabel verkeerde waarden, en mist volledig vertex D. Maar het kreeg hetzelfde antwoord dat Dijkstra’ s zou hebben, en het deed veel sneller. Dijkstra ‘ s zouden naar alle 12 hoekpunten willen kijken alvorens te verklaren dat het de kortste weg heeft gevonden; A* hoefde alleen maar naar 4 te kijken voordat het de juiste weg had gevonden. Deze verandering in snelheid is te wijten aan de heuristische die we gebruikten: zo vaak als we konden, wilden we de afstand met onze bestemming te sluiten. Als we teruggaan naar Wikipedia ‘ s definitie voor heuristiek, heeft A* volledigheid geruild voor snelheid.

laten we een ander klein voorbeeld proberen, maar met een obstructie op weg naar de bestemming.

startpunt is de linkerbovenhoek, en A* probeert de kortste weg naar de rechterbovenhoek te vinden. De zwarte vierkanten vertegenwoordigen een gat in de grafiek en kunnen niet worden doorkruist. Als A* zijn heuristische van “altijd dichter bij de bestemming” volgt, zullen die zwarte vierkanten het naar een doodlopende weg leiden.

Op dit punt, A* zoekt naar de kleinste sommen, dat zijn de vierkantjes net onder en rechts van het startpunt. A * zal beide paden verkennen, maar het neerwaartse pad zal in een ander doodlopende pad lopen, en rechts pad zal een weg vinden rond de zwarte vierkanten. Het zou kunnen spelen een beetje anders dan dit, maar laten we aannemen dat dit is hoe A* behandeld dit scenario. Zelfs wanneer het werd getrokken in doodlopende wegen, was het in staat om terug te gaan en een ander pad te vinden, en het hoefde niet naar elk hoekpunt te kijken (de top rechts hoekpunt werd opnieuw overgeslagen). Dit betekent dat wanneer een * ster op zijn slechtst loopt, hij in principe net zo snel is als Dijkstra ‘ s normale prestaties. Elk algoritme heeft perfect geldige use cases, maar in termen van pathfinding en het vinden van de kortste paden, een* is de betere keuze.