Skip to content

pietv/astar

Repository files navigation

A* GoDoc Build status

Implementation of the A* Search algorithm.

Install

$ go get github.com/pietv/astar

Overview

A* Search is one of the intelligent exhaustive search algorithms which gets from Start to Finish by exploring successor states.

A* Steps It's intelligent because it uses a special guidance in selecting the states that are going to be explored next. The algorithm uses a minimum value of a sum of the next successor cost and the heuristic estimate (distance, for example) of how close that next successor is to Finish. These values are named Cost and Estimate in this implementation.

Without any guidance (that is when both Cost and Estimate values are constant), it explores all successor states, making it essentially the Breadth First Search algorithm (Go's container/heap implementation behaves like a queue if keys are equal).

Depending on whether Cost and Estimate are constant or not, A* Search behaves like other well-known algorithms:

Cost Estimate Behavior
const const Breadth First Search
variable const [Dijkstra's Shortest Path] (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) / Uniform-Cost Search
const variable Greedy Best First Search
variable variable A*

It is not necessary to use a graph data structure. Crawling the internet and feeding harvested links as successors would do or, as another example, the provided maze demo uses a rectangular matrix and uses surrounding cells as successors.

Maze Demo Install the demo:

$ go get github.com/pietv/astar/cmd/maze

About

Implementation of the A* Search algorithm

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages