Spaces:
Sleeping
Sleeping
File size: 2,919 Bytes
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 |
"""Depth-First 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 ..core.frontier import StackFrontier
from ..models.state import PathResult, SearchStep
def dfs_search(
problem: "GenericSearch", visualize: bool = False
) -> Tuple[PathResult, Optional[List[SearchStep]]]:
"""
Depth-first search using LIFO stack.
Not guaranteed to find optimal solution.
Complete in finite state spaces with cycle detection.
Args:
problem: The search problem to solve
visualize: If True, collect visualization steps
Returns:
Tuple of (PathResult, Optional[List[SearchStep]])
"""
frontier = StackFrontier()
start = problem.initial_state()
start_node = SearchNode(state=start, path_cost=0, depth=0)
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 (reverse order so first action is processed last -> depth-first)
actions = problem.actions(node.state)
for action in reversed(actions):
child_state = problem.result(node.state, action)
if child_state not in explored and not frontier.contains_state(child_state):
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,
)
frontier.push(child)
# No solution found
return (
PathResult(plan="", cost=float("inf"), nodes_expanded=nodes_expanded, path=[]),
steps,
)
|