Spaces:
Sleeping
Sleeping
| """SearchNode class for the search tree.""" | |
| from dataclasses import dataclass, field | |
| from typing import Optional, List, Tuple, Any | |
| class SearchNode: | |
| """ | |
| Represents a node in the search tree. | |
| Attributes: | |
| state: Current position (x, y) on the grid | |
| parent: Parent node for path reconstruction | |
| action: Action taken to reach this node (up/down/left/right/tunnel) | |
| path_cost: g(n) - cost from start to this node | |
| depth: Depth in search tree | |
| """ | |
| state: Tuple[int, int] | |
| parent: Optional['SearchNode'] = None | |
| action: Optional[str] = None | |
| path_cost: float = 0.0 | |
| depth: int = 0 | |
| # For priority queue - lower is better | |
| priority: float = field(default=0.0, compare=False) | |
| def __lt__(self, other: 'SearchNode') -> bool: | |
| """Compare nodes by priority for priority queue.""" | |
| return self.priority < other.priority | |
| def __eq__(self, other: Any) -> bool: | |
| """Nodes are equal if they have the same state.""" | |
| if not isinstance(other, SearchNode): | |
| return False | |
| return self.state == other.state | |
| def __hash__(self) -> int: | |
| """Hash by state for set membership.""" | |
| return hash(self.state) | |
| def get_path(self) -> List[Tuple[int, int]]: | |
| """ | |
| Reconstruct the path from root to this node. | |
| Returns: | |
| List of positions from start to current node | |
| """ | |
| path = [] | |
| node: Optional[SearchNode] = self | |
| while node is not None: | |
| path.append(node.state) | |
| node = node.parent | |
| path.reverse() | |
| return path | |
| def get_actions(self) -> List[str]: | |
| """ | |
| Reconstruct the sequence of actions from root to this node. | |
| Returns: | |
| List of actions taken from start to current node | |
| """ | |
| actions = [] | |
| node: Optional[SearchNode] = self | |
| while node is not None and node.action is not None: | |
| actions.append(node.action) | |
| node = node.parent | |
| actions.reverse() | |
| return actions | |
| def get_solution(self) -> str: | |
| """ | |
| Get the solution as a comma-separated string of actions. | |
| Returns: | |
| String in format "action1,action2,action3,..." | |
| """ | |
| actions = self.get_actions() | |
| return ",".join(actions) if actions else "" | |
| def expand( | |
| self, | |
| actions_func, | |
| result_func, | |
| cost_func, | |
| heuristic_func=None | |
| ) -> List['SearchNode']: | |
| """ | |
| Expand this node by generating all child nodes. | |
| Args: | |
| actions_func: Function(state) -> List[str] of valid actions | |
| result_func: Function(state, action) -> new_state | |
| cost_func: Function(state, action, new_state) -> step_cost | |
| heuristic_func: Optional Function(state, goal) -> h(n) for A*/Greedy | |
| Returns: | |
| List of child SearchNode objects | |
| """ | |
| children = [] | |
| for action in actions_func(self.state): | |
| new_state = result_func(self.state, action) | |
| step_cost = cost_func(self.state, action, new_state) | |
| child = SearchNode( | |
| state=new_state, | |
| parent=self, | |
| action=action, | |
| path_cost=self.path_cost + step_cost, | |
| depth=self.depth + 1 | |
| ) | |
| # Set priority if heuristic is provided (for A*) | |
| if heuristic_func is not None: | |
| child.priority = child.path_cost + heuristic_func(new_state) | |
| else: | |
| child.priority = child.path_cost | |
| children.append(child) | |
| return children | |
| def __repr__(self) -> str: | |
| return f"SearchNode(state={self.state}, depth={self.depth}, cost={self.path_cost})" | |