machine_learning.astar

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

Attributes

world

Classes

Cell

Class cell represents a cell in the world which have the properties:

Gridworld

Gridworld class represents the external world here a grid M*M

Functions

astar(world, start, goal)

Implementation of a start algorithm.

Module Contents

class machine_learning.astar.Cell

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.

__eq__(cell)
showcell()
f = 0
g = 0
h = 0
parent = None
position = (0, 0)
class machine_learning.astar.Gridworld(world_size=(5, 5))

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.

get_neighbours(cell)

Return the neighbours of cell

show()
w
world_x_limit = 5
world_y_limit = 5
machine_learning.astar.astar(world, start, goal)

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)]
machine_learning.astar.world