Skip to content

Greedy

Greedy best-first search traversal.

GreedyBestFirstTraversal dataclass 

GreedyBestFirstTraversal(heuristic: HeuristicFunction)

Bases: TraversalStrategyABC

Greedy best-first 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/greedy.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    _ = max_depth
    frontier: list[PriorityEntry] = []
    heapq.heappush(frontier, PriorityEntry(self.heuristic(tree.root), 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(self.heuristic(child), child)
        ),
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=None,
        goal_on_pop=False,
    )

greedy_best_first 

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

Greedy best-first search using heuristic only.

Expands the node with the lowest heuristic value first. Does not consider accumulated path cost — purely greedy. Fast but not guaranteed to find the optimal (shortest) 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. Lower is better.

 required
max_expansions int | None

Maximum number of nodes to expand before giving up. 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/greedy.py 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
def greedy_best_first(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    heuristic: HeuristicFunction,
    max_expansions: int | None = None,
) -> SearchResult:
    """Greedy best-first search using heuristic only.

    Expands the node with the lowest heuristic value first. Does not
    consider accumulated path cost — purely greedy. Fast but not
    guaranteed to find the optimal (shortest) 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. Lower is better.
        max_expansions: Maximum number of nodes to expand before
            giving up. None means no limit.

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