Skip to content
Navigation Menu
{{ message }}
forked from aimacode/aima-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSimpleProblemSolvingAgent.py
More file actions
309 lines (254 loc) · 10.6 KB
/
Copy pathSimpleProblemSolvingAgent.py
File metadata and controls
309 lines (254 loc) · 10.6 KB
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
"""
SimpleProblemSolvingAgent.py
This module implements a Simple Problem-Solving Agent (SPSA) that finds
the best path between any two cities in the Romania map using four
search algorithms: Greedy Best-First Search, A* Search, Hill Climbing,
and Simulated Annealing.
Author: Dennis Chavez Romero
Course: CS 534 - Artificial Intelligence
Date: 03/08/2026
"""
from search import *
import numpy as np
class RomaniaRouteProblem(Problem):
"""
A subclass of Problem that represents the Romania route-finding problem.
Uses the Romania map graph and city coordinates to find paths between cities.
"""
def __init__(self, initial, goal, graph, locations):
"""
Initialize the Romania route problem.
Args:
initial: The starting city name.
goal: The destination city name.
graph: An UndirectedGraph representing the Romania map.
locations: A dictionary mapping city names to (x, y) coordinates.
"""
super().__init__(initial, goal)
self.graph = graph
self.locations = locations
def actions(self, state):
"""Return a list of neighboring cities reachable from the given state."""
return list(self.graph.get(state).keys())
def result(self, state, action):
"""Return the city reached by taking the given action (moving to a neighbor)."""
return action
def path_cost(self, cost_so_far, A, action, B):
"""
Return the total cost of the path arriving at city B from city A,
given the cost so far to reach A.
"""
edge_cost = self.graph.get(A, B)
if edge_cost is None:
return cost_so_far + float('inf')
return cost_so_far + edge_cost
def goal_test(self, state):
"""Return True if the given state matches the goal city."""
return state == self.goal
def h(self, node):
"""
Heuristic function: returns the straight-line distance
from the node's state to the goal city.
"""
if self.locations and node.state in self.locations and self.goal in self.locations:
return int(distance(self.locations[node.state], self.locations[self.goal]))
return float('inf')
def value(self, state):
"""
Value function for local search algorithms.
Returns the negative straight-line distance to the goal,
so that states closer to the goal have higher values.
"""
if self.locations and state in self.locations and self.goal in self.locations:
return -distance(self.locations[state], self.locations[self.goal])
return -float('inf')
class SimpleProblemSolvingAgent:
"""
A Simple Problem-Solving Agent that searches for the best path
between two cities using four different search algorithms:
Greedy Best-First Search, A* Search, Hill Climbing, and Simulated Annealing.
Based on Section 3.1 and 3.2 of the AIMA textbook.
"""
ALGORITHMS = ['greedy', 'astar', 'hill_climbing', 'simulated_annealing']
def __init__(self, graph, locations, initial, goal):
"""
Initialize the agent with a graph, locations, and start/goal cities.
Args:
graph: An UndirectedGraph representing the Romania map.
locations: A dictionary mapping city names to (x, y) coordinates.
initial: The starting city name.
goal: The destination city name.
"""
self.graph = graph
self.locations = locations
self.initial = initial
self.goal = goal
def formulate_goal(self):
"""Return the goal city."""
return self.goal
def formulate_problem(self):
"""Create and return a RomaniaRouteProblem instance."""
return RomaniaRouteProblem(self.initial, self.goal,
self.graph, self.locations)
def search(self, problem, algorithm_key='astar'):
"""
Dispatch to the appropriate search algorithm based on the key.
Args:
problem: A RomaniaRouteProblem instance.
algorithm_key: One of 'greedy', 'astar', 'hill_climbing',
or 'simulated_annealing'.
Returns:
A Node representing the end of the found path.
"""
dispatch = {
'greedy': self.greedy_best_first_search,
'astar': self.a_star_search,
'hill_climbing': self.hill_climbing,
'simulated_annealing': self.simulated_annealing,
}
if algorithm_key not in dispatch:
raise ValueError(
f"Unknown algorithm '{algorithm_key}'. "
f"Choose from: {self.ALGORITHMS}"
)
return dispatch[algorithm_key](problem)
def solve(self, algorithm_key='astar'):
"""
Formulate the problem and solve it using the specified algorithm.
Args:
algorithm_key: The search algorithm to use.
Returns:
A dictionary containing the path, actions, total cost,
and whether the goal was reached.
"""
problem = self.formulate_problem()
node = self.search(problem, algorithm_key)
return self._extract_path_info(node, problem)
def greedy_best_first_search(self, problem, display=False):
"""
Greedy Best-First Search (Section 3.5.1).
Expands the node closest to the goal based on the heuristic h(n).
Uses best_first_graph_search with f(n) = h(n).
"""
h = memoize(problem.h, 'h')
return self._best_first_graph_search(problem, lambda n: h(n), display)
def a_star_search(self, problem, display=False):
"""
A* Search (Section 3.5.2).
Expands the node with the lowest f(n) = g(n) + h(n),
combining actual path cost and heuristic estimate.
"""
h = memoize(problem.h, 'h')
return self._best_first_graph_search(problem, lambda n: n.path_cost + h(n), display)
def _best_first_graph_search(self, problem, f, display=False):
"""
Best-First Graph Search (Figure 3.7).
Searches by expanding the node with the lowest f value.
Used as the foundation for both Greedy and A* search.
Args:
problem: The search problem.
f: The evaluation function to minimize.
display: If True, print search statistics.
Returns:
A Node representing the goal, or None if no solution is found.
"""
f = memoize(f, 'f')
node = Node(problem.initial)
frontier = PriorityQueue('min', f)
frontier.append(node)
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
if display:
print(len(explored), "paths have been expanded and",
len(frontier), "paths remain in the frontier")
return node
explored.add(node.state)
for child in node.expand(problem):
if child.state not in explored and child not in frontier:
frontier.append(child)
elif child in frontier:
if f(child) < frontier[child]:
del frontier[child]
frontier.append(child)
return None
def hill_climbing(self, problem):
"""
Hill Climbing Search (Figure 4.2).
A local search algorithm that keeps moving to the highest-valued
neighbor until no better neighbor exists. May get stuck at
local maxima and not always reach the goal.
"""
current = Node(problem.initial)
visited = {problem.initial}
while True:
if problem.goal_test(current.state):
return current
neighbors = current.expand(problem)
# Filter visited cities to ensure unique cities in path
unvisited = [n for n in neighbors if n.state not in visited]
if not unvisited:
break
neighbor = argmax_random_tie(unvisited,
key=lambda node: problem.value(node.state))
if problem.value(neighbor.state) <= problem.value(current.state):
break
visited.add(neighbor.state)
current = neighbor
return current
def simulated_annealing(self, problem, schedule=exp_schedule(k=20, lam=0.005, limit=1000)):
"""
Simulated Annealing Search (Figure 4.5).
A local search algorithm that allows downhill moves with decreasing
probability controlled by a temperature schedule. This enables
escaping local maxima, though the result is not guaranteed to be optimal.
"""
current = Node(problem.initial)
visited = {problem.initial}
for t in range(sys.maxsize):
T = schedule(t)
if T == 0:
return current
if problem.goal_test(current.state):
return current
neighbors = current.expand(problem)
# Filter visited cities to ensure unique cities in path
unvisited = [n for n in neighbors if n.state not in visited]
if not unvisited:
return current
next_choice = random.choice(unvisited)
delta_e = problem.value(next_choice.state) - problem.value(current.state)
if delta_e > 0 or probability(np.exp(delta_e / T)):
visited.add(next_choice.state)
current = next_choice
elif probability(np.exp(-delta_e / T)):
visited.add(next_choice.state)
current = next_choice
return current
@staticmethod
def _extract_path_info(node, problem):
"""
Extract path information from a search result node.
Args:
node: The final Node returned by a search algorithm.
problem: The problem that was solved.
Returns:
A dictionary with keys:
- path: List of city names from start to end.
- actions: List of actions taken.
- total_cost: Total path cost.
- reached_goal: Whether the goal was reached.
"""
if node is None:
return {
'path': [], 'actions': [],
'total_cost': float('inf'), 'reached_goal': False
}
path_nodes = node.path()
return {
'path': [n.state for n in path_nodes],
'actions': node.solution(),
'total_cost': node.path_cost,
'reached_goal': problem.goal_test(node.state)
}
You can’t perform that action at this time.