Spaces:
Sleeping
Sleeping
File size: 5,315 Bytes
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 172 173 174 175 176 177 178 179 180 181 182 183 184 |
"""Frontier data structures for search algorithms."""
from abc import ABC, abstractmethod
from collections import deque
import heapq
from typing import List, Optional, Set, Dict
from .node import SearchNode
class Frontier(ABC):
"""Abstract base class for frontier data structures."""
@abstractmethod
def push(self, node: SearchNode) -> None:
"""Add a node to the frontier."""
pass
@abstractmethod
def pop(self) -> SearchNode:
"""Remove and return the next node from the frontier."""
pass
@abstractmethod
def is_empty(self) -> bool:
"""Check if the frontier is empty."""
pass
@abstractmethod
def __len__(self) -> int:
"""Return the number of nodes in the frontier."""
pass
@abstractmethod
def contains_state(self, state) -> bool:
"""Check if a state is in the frontier."""
pass
def get_states(self) -> List:
"""Get all states in the frontier (for visualization)."""
return []
class QueueFrontier(Frontier):
"""FIFO queue frontier for Breadth-First Search."""
def __init__(self):
self._queue: deque[SearchNode] = deque()
self._states: Set = set()
def push(self, node: SearchNode) -> None:
self._queue.append(node)
self._states.add(node.state)
def pop(self) -> SearchNode:
node = self._queue.popleft()
self._states.discard(node.state)
return node
def is_empty(self) -> bool:
return len(self._queue) == 0
def __len__(self) -> int:
return len(self._queue)
def contains_state(self, state) -> bool:
return state in self._states
def get_states(self) -> List:
return [node.state for node in self._queue]
class StackFrontier(Frontier):
"""LIFO stack frontier for Depth-First Search."""
def __init__(self):
self._stack: List[SearchNode] = []
self._states: Set = set()
def push(self, node: SearchNode) -> None:
self._stack.append(node)
self._states.add(node.state)
def pop(self) -> SearchNode:
node = self._stack.pop()
self._states.discard(node.state)
return node
def is_empty(self) -> bool:
return len(self._stack) == 0
def __len__(self) -> int:
return len(self._stack)
def contains_state(self, state) -> bool:
return state in self._states
def get_states(self) -> List:
return [node.state for node in self._stack]
class PriorityQueueFrontier(Frontier):
"""
Priority queue frontier for UCS, Greedy, and A* search.
Uses heapq with a counter to break ties and ensure FIFO ordering for nodes with equal priority.
"""
def __init__(self):
self._heap: List[tuple] = [] # (priority, counter, node)
self._counter: int = 0
self._states: Dict = {} # state -> (priority, node) for updates
self._removed: Set = set() # Track removed entries
def push(self, node: SearchNode) -> None:
"""
Add a node to the priority queue.
If a node with the same state already exists with higher priority, it will be updated.
"""
state = node.state
priority = node.priority
# If state exists with higher or equal priority, skip
if state in self._states:
existing_priority, _ = self._states[state]
if existing_priority <= priority:
return
# Mark old entry as removed
self._removed.add((existing_priority, state))
# Add new entry
entry = (priority, self._counter, node)
heapq.heappush(self._heap, entry)
self._states[state] = (priority, node)
self._counter += 1
def pop(self) -> SearchNode:
"""Remove and return the node with lowest priority."""
while self._heap:
priority, _, node = heapq.heappop(self._heap)
# Skip removed entries
if (priority, node.state) in self._removed:
self._removed.discard((priority, node.state))
continue
# Skip if this is not the current entry for this state
if node.state in self._states:
current_priority, current_node = self._states[node.state]
if current_priority != priority:
continue
del self._states[node.state]
return node
raise IndexError("Pop from empty frontier")
def is_empty(self) -> bool:
# Account for lazy deletions
return len(self._states) == 0
def __len__(self) -> int:
return len(self._states)
def contains_state(self, state) -> bool:
return state in self._states
def get_node(self, state) -> Optional[SearchNode]:
"""Get the node for a given state if it exists."""
if state in self._states:
_, node = self._states[state]
return node
return None
def get_states(self) -> List:
return list(self._states.keys())
def get_priority(self, state) -> Optional[float]:
"""Get the priority of a state if it exists."""
if state in self._states:
priority, _ = self._states[state]
return priority
return None
|