Spaces:
Sleeping
Sleeping
File size: 5,015 Bytes
e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 e067c2d 47bba68 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
"""Iterative Deepening Search algorithm."""
from typing import Tuple, Optional, List, TYPE_CHECKING
if TYPE_CHECKING:
from ..core.generic_search import GenericSearch
from ..core.node import SearchNode
from ..models.state import PathResult, SearchStep
# Sentinel values for DLS results
CUTOFF = "cutoff"
FAILURE = "failure"
def depth_limited_search(
problem: "GenericSearch",
limit: int,
visualize: bool = False,
steps: Optional[List[SearchStep]] = None,
base_expanded: int = 0,
) -> Tuple[Optional[PathResult], str, int, Optional[List[SearchStep]]]:
"""
Depth-limited search - DFS with depth limit.
Args:
problem: The search problem
limit: Maximum depth to search
visualize: If True, collect visualization steps
steps: Existing steps list to append to
base_expanded: Starting count for nodes expanded
Returns:
Tuple of (PathResult or None, status, nodes_expanded, steps)
status is CUTOFF if limit reached, FAILURE if no solution exists
"""
start = problem.initial_state()
start_node = SearchNode(state=start, path_cost=0, depth=0)
return _recursive_dls(
problem,
start_node,
limit,
set(),
visualize,
steps if steps is not None else ([] if visualize else None),
base_expanded,
)
def _recursive_dls(
problem: "GenericSearch",
node: SearchNode,
limit: int,
explored: set,
visualize: bool,
steps: Optional[List[SearchStep]],
nodes_expanded: int,
) -> Tuple[Optional[PathResult], str, int, Optional[List[SearchStep]]]:
"""Recursive helper for depth-limited search."""
# Record step for visualization
if visualize and steps is not None:
steps.append(
SearchStep(
step_number=nodes_expanded,
current_node=node.state,
action=node.action,
frontier=[], # DLS doesn't maintain explicit frontier
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(),
),
"success",
nodes_expanded,
steps,
)
# Depth limit reached
if node.depth >= limit:
return None, CUTOFF, nodes_expanded, steps
# Mark as explored for this path
explored.add(node.state)
nodes_expanded += 1
cutoff_occurred = False
# 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)
child = SearchNode(
state=child_state,
parent=node,
action=action,
path_cost=node.path_cost + step_cost,
depth=node.depth + 1,
)
result, status, nodes_expanded, steps = _recursive_dls(
problem, child, limit, explored.copy(), visualize, steps, nodes_expanded
)
if status == "success":
return result, status, nodes_expanded, steps
elif status == CUTOFF:
cutoff_occurred = True
if cutoff_occurred:
return None, CUTOFF, nodes_expanded, steps
else:
return None, FAILURE, nodes_expanded, steps
def ids_search(
problem: "GenericSearch", visualize: bool = False, max_depth: int = 1000
) -> Tuple[PathResult, Optional[List[SearchStep]]]:
"""
Iterative deepening search - repeated DLS with increasing depth.
Combines BFS's completeness and optimality (for unweighted)
with DFS's space efficiency.
Args:
problem: The search problem to solve
visualize: If True, collect visualization steps
max_depth: Maximum depth to search (prevents infinite loops)
Returns:
Tuple of (PathResult, Optional[List[SearchStep]])
"""
total_expanded = 0
all_steps: List[SearchStep] = [] if visualize else None
for depth in range(max_depth):
result, status, expanded, steps = depth_limited_search(
problem, depth, visualize, all_steps, total_expanded
)
total_expanded = expanded
if visualize and steps:
all_steps = steps
if status == "success" and result is not None:
result.nodes_expanded = total_expanded
return result, all_steps
elif status == FAILURE:
# No solution exists
break
# No solution found within max_depth
return (
PathResult(plan="", cost=float("inf"), nodes_expanded=total_expanded, path=[]),
all_steps,
)
|