Given a network of nodes, with connections between them, were each connection has a "cost" of moving from one node to the next, the A* algorithm efficiently finds the lowest cost route from a starting node to a goal node. It does this by following the lowest cost path from the starting node, and increasing the length of that path until it is no longer the lowest cost path. A* moves from path to path, extending only the lowest cost option, and adding the additional cost into the total cost of the path. If that causes the path to no longer be the lowest cost, it is abandoned (for now) and the new lowest cost path is extended next instead.
Pseudocode:
push startNode onto openList while(openList is not empty) { currentNode = find lowest f in openList if currentNode is final, return the successful path push currentNode onto closedList and remove from openList foreach neighbor of currentNode { if neighbor is not in openList { save g, h, and f then save the current parent add neighbor to openList } if neighbor is in openList but the current g is better than previous g { save g and f, then save the current parent } }
A* was written in 1968 at SRI as part of the Shakey Robot project.
See also:
See also:
file: /Techref/method/a-star.htm, 2KB, , updated: 2023/10/8 18:23, local time: 2024/11/12 13:21,
owner: JMN-EFP-786,
18.117.8.62:LOG IN
|
©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://sxlist.com/Techref/method/a-star.htm"> A * Search</A> |
Did you find what you needed? |
Welcome to sxlist.com!sales, advertizing, & kind contributors just like you! Please don't rip/copy (here's why Copies of the site on CD are available at minimal cost. |
Welcome to sxlist.com! |
.