Spaces:
Sleeping
Sleeping
File size: 3,297 Bytes
e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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 53 54 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
"""Greedy Best-First Search algorithm."""
from typing import Tuple, Optional, List, Callable, TYPE_CHECKING
if TYPE_CHECKING:
from ..core.generic_search import GenericSearch
from ..core.node import SearchNode
from ..core.frontier import PriorityQueueFrontier
from ..models.state import PathResult, SearchStep
def greedy_search(
problem: "GenericSearch",
heuristic: Callable[[Tuple[int, int], Tuple[int, int]], float],
visualize: bool = False,
) -> Tuple[PathResult, Optional[List[SearchStep]]]:
"""
Greedy best-first search using heuristic only.
Expands node that appears closest to goal.
Not guaranteed to find optimal solution.
Not complete in general.
Args:
problem: The search problem to solve
heuristic: Function(state, goal) -> estimated cost to goal
visualize: If True, collect visualization steps
Returns:
Tuple of (PathResult, Optional[List[SearchStep]])
"""
frontier = PriorityQueueFrontier()
start = problem.initial_state()
# Get goal for heuristic calculation (assume single goal)
goal = getattr(problem, "goal", None)
h_value = heuristic(start, goal) if goal else 0
start_node = SearchNode(state=start, path_cost=0, depth=0, priority=h_value)
frontier.push(start_node)
explored: set = set()
nodes_expanded = 0
steps: List[SearchStep] = [] if visualize else None
while not frontier.is_empty():
node = frontier.pop()
# Record step for visualization
if visualize:
steps.append(
SearchStep(
step_number=nodes_expanded,
current_node=node.state,
action=node.action,
frontier=frontier.get_states(),
explored=list(explored),
current_path=node.get_path(),
path_cost=node.path_cost,
)
)
# Goal test
if problem.goal_test(node.state):
return (
PathResult(
plan=node.get_solution(),
cost=node.path_cost,
nodes_expanded=nodes_expanded,
path=node.get_path(),
),
steps,
)
# Skip if already explored
if node.state in explored:
continue
explored.add(node.state)
nodes_expanded += 1
# Expand node
for action in problem.actions(node.state):
child_state = problem.result(node.state, action)
if child_state not in explored:
step_cost = problem.step_cost(node.state, action, child_state)
h_value = heuristic(child_state, goal) if goal else 0
child = SearchNode(
state=child_state,
parent=node,
action=action,
path_cost=node.path_cost + step_cost,
depth=node.depth + 1,
priority=h_value, # Priority = h(n) only for Greedy
)
frontier.push(child)
# No solution found
return (
PathResult(plan="", cost=float("inf"), nodes_expanded=nodes_expanded, path=[]),
steps,
)
|