alcinnz
A common task to which computers are put is to compute optimal routes through a transport network we or our data can travel.
A foundational technique is Dijkstra's Algorithm a.k.a. Uniform Cost Search! It traverses the network using a priority queue (I described these concepts recently, calling networks "graphs"), & upon visiting each node updates the weight of its neighbours which it found a shorter path to.
Once a we visit a node that's the shortest path! Once we visit the destination...
1/3
alcinnz
While Dijkstra's Algorithm is guaranteed to give us an optimal path (as long as no weights are negative), it considers obviously-wrong paths. As long as the path is shorter than its final answer its considered... Which suggests there's a faster way!
So A* routing adds a decent under-estimate (a road network would use the Euclidean Distance, as the crow flies) of the final cost to steer the routing algorithm in the right direction.
UIs will want to reformat the resulting answer.
2/2 Fin!
curtmack
@alcinnz A fun trick I learned from a blog post by a game dev (Factorio, I think) is that you can use Djikstra's algorithm over a coarser map, and then use that as your heuristic function for A* on the detailed map. If the coarse map is cheap to produce, or if it only needs to be updated rarely, then this can be a huge improvement over using Euclidean distance as your heuristic, as it quickly routes around lakes and other large barriers.
alcinnz
@curtmack Nice trick!
A large open space like a game map... I can see that causing routing performance problems...
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.