Ik lees dit:
http://en.wikipedia.org/wiki/A*_search_algorithm
Er staat dat A* sneller is dan dijkstra en best-first-search gebruikt om dingen te versnellen.
Als ik het algoritme nodig heb om in milliseconden te werken, wanneer wordt A* dan de meest prominente keuze.
Voor zover ik heb begrepen levert dit niet noodzakelijk de beste resultaten op.
Als ik snelle resultaten nodig heb, is het dan beter om de paden vooraf te berekenen? Het kan megabytes aan ruimte in beslag nemen om ze op te slaan.
Antwoord 1, autoriteit 100%
Er staat dat A* sneller is dan dijkstra en gebruikt best-first-search om
dingen versnellen.
A* is in feite een geïnformeerde variant van Dijkstra.
A* wordt beschouwd als een “beste eerste zoekopdracht” omdat het gretig kiest welk hoekpunt als volgende wordt onderzocht, volgens de waarde van f(v)[f(v) = h(v) + g(v)] – waarbij hde heuristiek is en gde kosten tot nu toe.
Merk op dat als u een niet-informatieve heuristische functie gebruikt: h(v) = 0voor elke v: u krijgt dat A* kiest welk hoekpunt als volgende wordt ontwikkeld alleen de “tot dusverre kosten” (g(v)), hetzelfde als Dijkstra’s algoritme – dus als h(v) = 0, wordt A* standaard ingesteld op Dijkstra’s algoritme.
Als ik het algoritme nodig heb om in milliseconden te werken, wanneer wordt A* dan
de meest prominente keuze.
Niet helemaal, het hangt van veel dingen af. Als je een afdalingsheuristische functie hebt – uit mijn persoonlijke ervaring, hebzuchtig best eerst (kiezen op basis van de heuristische functie alleen) – is meestal aanzienlijk sneller dan A* (maar is niet eens in de buurt van optimaal).
Voor zover ik heb begrepen levert dit niet per se de beste op
resultaten.
A* is zowel compleet (vindt een pad als dat bestaat) en optimaal (vindt altijd het kortste pad) als je een Toelaatbare heuristische functie. Als uw functie niet ontvankelijk is, zijn alle weddenschappen uitgeschakeld.
Als ik snelle resultaten nodig heb, is het dan beter om de paden vooraf te berekenen? Het kan
nemen megabytes aan ruimte in om ze op te slaan.
Dit is een veelvoorkomende optimalisatie voor sommige problemen, bijvoorbeeld voor het 15-puzzelprobleem, maar het is geavanceerder. Een pad van punt A naar punt B wordt een macro genoemd. Sommige paden zijn erg handig en moeten onthouden worden. Er is een Machine Learning-component aan het algoritme toegevoegd om dingen te versnellen door deze macro’s te onthouden.
Merk op dat het pad van punt A naar punt B hier meestal niet in de toestandsgrafiek ligt, maar in het probleem zelf (bijvoorbeeld hoe een vierkant van de laagste lijn naar de bovenste lijn te verplaatsen…)
Om dingen te versnellen:
Als je een heuristiek hebt en je vindt deze te traag, en je wilt een snellere oplossing, zelfs als deze niet optimaal is – A* Epsilonis meestal sneller dan A*, terwijl het je een grens geeft aan de optimaliteit van het pad (hoe dicht het bij optimaal is).
Antwoord 2, autoriteit 26%
Dijkstra is een speciaal geval voor A* (wanneer de heuristiek nul is).
Een* zoekopdracht:
Het heeft twee kostenfuncties.
g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.
De totale kosten van elk knooppunt worden berekend door f (n) = g (n) + h (n)
Dijkstra’s:
Het heeft één kostenfunctie, die reële kostenwaarde is van bron naar elk knooppunt: F (n) = g (n)
Het vindt het kortste pad van de bron naar elk ander knooppunt door alleen echte kosten te overwegen.
Antwoord 3, Autoriteit 20%
A * is net als Dijkstra , het enige verschil is dat a * probeert op zoek naar een beter pad door een heuristische functie te gebruiken die prioriteit geeft aan knooppunten die zijn verondersteld beter te zijn dan anderen terwijl Dijkstra gewoon alle mogelijke paden verkent.
De optimaliteit is afhankelijk van de gebruikte heuristische functie, dus ja, het kan hierdoor een niet-optimaal resultaat retourneren en tegelijkertijd beter de heuristiek voor uw specifieke lay-out, en beter de resultaten (en mogelijk de snelheid) zijn.
Het is bedoeld om sneller te zijn dan Dijkstra, zelfs als het meer geheugen en meer operaties per knooppunt nodig heeft, omdat het een stuk minder knooppunten verkent en de winst in elk geval goed is.
PrecoComputing De paden kunnen de enige manier zijn als u realtime-resultaten nodig heeft en de grafiek vrij groot is, maar meestal wilt u de route minder vaak pathfind (ik neem aan dat u het vaak wilt berekenen).
Antwoord 4, Autoriteit 8%
Deze algoritheems kunnen worden gebruikt in pathfinding en grafiektraversal, het proces van het plotten van een efficiënt gerichte pad tussen meerdere punten, genaamd knooppunten.
Formule voor a* is f =g + h., g: werkelijke kosten en H betekent heuristische kosten.
formule voor Dijktras is f = g. er zijn geen heuristische kosten. wanneer we a*gebruiken en als de heuristische kosten 0zijn, dan is deze gelijk aan het Dijktras-algoritme.
Antwoord 5, autoriteit 5%
Kort antwoord:
A* gebruikt heuristieken om de zoekopdracht te optimaliseren. Dat wil zeggen dat u een functie kunt definiëren die tot op zekere hoogte de kosten van het ene knooppunt tot het doel kan schatten. Dit is met name handig wanneer u een pad zoekt op een geografische weergave (kaart) waar u bijvoorbeeld de afstand tot het doel vanaf een bepaald grafiekknooppunt kunt raden. Daarom wordt meestal A* gebruikt voor het vinden van paden in games enz. Waar Djikstra in meer algemene gevallen wordt gebruikt.
Nee, A* geeft niet altijd het beste pad.
Als heuristiek de “geografische” afstand is, kan het volgende voorbeeld het niet-optimale pad geven.
[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
|----------------------------------------------------------------|