The A* algorithm combines features of uniform-cost search and pure heuristic search to efficiently compute optimal solutions.
The A* algorithm is a best-first search algorithm in which the cost associated with a node is f(n) = g(n) + h(n), where g(n) is the cost of the path from the initial state to node n and h(n) is the heuristic estimate or the cost or a path from node n to a goal.
The A* algorithm introduces a heuristic into a regular graph-searching algorithm, essentially planning ahead at each step so a more optimal decision is made. For this reason, A* is known as an algorithm with brains.
https://en.wikipedia.org/wiki/A*_search_algorithm
Class cell represents a cell in the world which have the properties: |
|
Gridworld class represents the external world here a grid M*M |
|
Implementation of a start algorithm. |
Class cell represents a cell in the world which have the properties: position: represented by tuple of x and y coordinates initially set to (0,0). parent: Contains the parent cell object visited before we arrived at this cell. g, h, f: Parameters used when calling our heuristic function.
Gridworld class represents the external world here a grid M*M matrix. world_size: create a numpy array with the given world_size default is 5.
Return the neighbours of cell
Implementation of a start algorithm. world : Object of the world object. start : Object of the cell as start position. stop : Object of the cell as goal position.
>>> p = Gridworld()
>>> start = Cell()
>>> start.position = (0,0)
>>> goal = Cell()
>>> goal.position = (4,4)
>>> astar(p, start, goal)
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]