Skip to content

Astar

A* search traversal.

AStarTraversal dataclass 

AStarTraversal(
    heuristic: HeuristicFunction,
    cost: CostFunction | None = None,
)

Bases: TraversalStrategyABC

A* traversal policy.

search 

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/traversal/astar.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    _ = max_depth
    cost_fn: CostFunction = (
        self.cost if self.cost is not None else lambda node: float(node.depth)
    )
    frontier: list[PriorityEntry] = []
    root_f = cost_fn(tree.root) + self.heuristic(tree.root)
    heapq.heappush(frontier, PriorityEntry(root_f, tree.root))
    return run_frontier_search(
        tree=tree,
        generator=generator,
        goal=goal,
        pop_next=lambda: heapq.heappop(frontier).node if frontier else None,
        push_child=lambda child: heapq.heappush(
            frontier, PriorityEntry(cost_fn(child) + self.heuristic(child), child)
        ),
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=None,
        goal_on_pop=True,
    )

astar 

astar(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    heuristic: HeuristicFunction,
    cost: CostFunction | None = None,
    max_expansions: int | None = None,
) -> SearchResult

A* search.

Expands the node with the lowest cost(node) + heuristic(node) first. With an admissible heuristic (never overestimates), A* guarantees finding the optimal (lowest cost) solution.

Parameters:

Name Type Description Default
tree ConfigurationTree

The configuration tree to search.

 required
generator MoveGenerator

Move generator for producing candidates.

 required
goal GoalPredicate

Predicate that returns True for goal configurations.

 required
heuristic HeuristicFunction

Estimates cost to goal. Must be admissible for optimality. Lower is better.

 required
cost CostFunction | None

Accumulated cost function. Defaults to node depth if None.

 None
max_expansions int | None

Maximum nodes to expand. None means no limit.

 None

Returns:

Type Description
SearchResult

SearchResult with the goal node (or None if not found).
Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/traversal/astar.py 
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
def astar(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    heuristic: HeuristicFunction,
    cost: CostFunction | None = None,
    max_expansions: int | None = None,
) -> SearchResult:
    """A* search.

    Expands the node with the lowest `cost(node) + heuristic(node)`
    first. With an admissible heuristic (never overestimates), A*
    guarantees finding the optimal (lowest cost) solution.

    Args:
        tree: The configuration tree to search.
        generator: Move generator for producing candidates.
        goal: Predicate that returns True for goal configurations.
        heuristic: Estimates cost to goal. Must be admissible for
            optimality. Lower is better.
        cost: Accumulated cost function. Defaults to node depth if None.
        max_expansions: Maximum nodes to expand. None means no limit.

    Returns:
        SearchResult with the goal node (or None if not found).
    """
    return AStarTraversal(heuristic=heuristic, cost=cost).search(
        tree=tree,
        generator=generator,
        goal=goal,
        max_expansions=max_expansions,
    )