graphs.greedy_best_first

https://en.wikipedia.org/wiki/Best-first_search#Greedy_BFS

Attributes

Path
TEST_GRIDS
delta
init

Classes

GreedyBestFirst
Node

Module Contents

class graphs.greedy_best_first.GreedyBestFirst(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int])

>>> grid = TEST_GRIDS[2]
>>> gbf = GreedyBestFirst(grid, (0, 0), (len(grid) - 1, len(grid[0]) - 1))
>>> [x.pos for x in gbf.get_successors(gbf.start)]
[(1, 0), (0, 1)]
>>> (gbf.start.pos_y + delta[3][0], gbf.start.pos_x + delta[3][1])
(0, 1)
>>> (gbf.start.pos_y + delta[2][0], gbf.start.pos_x + delta[2][1])
(1, 0)
>>> gbf.retrace_path(gbf.start)
[(0, 0)]
>>> gbf.search()  
[(0, 0), (1, 0), (2, 0), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3),
 (4, 4)]

get_successors(parent: Node) → list[Node]

Returns a list of successors (both in the grid and free spaces)

retrace_path(node: Node | None) → Path

Retrace the path from parents to parents until start node

search() → Path | None

Search for the path, if a path is not found, only the starting position is returned

closed_nodes: list[Node] = []

grid

open_nodes

reached = False

start

target

class graphs.greedy_best_first.Node(pos_x: int, pos_y: int, goal_x: int, goal_y: int, g_cost: float, parent: Node | None)

>>> k = Node(0, 0, 4, 5, 0, None)
>>> k.calculate_heuristic()
9
>>> n = Node(1, 4, 3, 4, 2, None)
>>> n.calculate_heuristic()
2
>>> l = [k, n]
>>> n == l[0]
False
>>> l.sort()
>>> n == l[0]
True

__eq__(other) → bool

__lt__(other) → bool

calculate_heuristic() → float

The heuristic here is the Manhattan Distance Could elaborate to offer more than one choice

f_cost

g_cost

goal_x

goal_y

parent

pos

pos_x

pos_y

graphs.greedy_best_first.Path

graphs.greedy_best_first.TEST_GRIDS = [[[0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0],...

graphs.greedy_best_first.delta

graphs.greedy_best_first.init = (0, 0)