Spaces:
Sleeping
Sleeping
File size: 3,829 Bytes
e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 |
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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
"""SearchNode class for the search tree."""
from dataclasses import dataclass, field
from typing import Optional, List, Tuple, Any
@dataclass
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})"
)
|