-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.py
173 lines (139 loc) · 5.16 KB
/
search.py
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
# search.py
# ---------
# Licensing Information: You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
#
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# ([email protected]) and Dan Klein ([email protected]).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel ([email protected]).
"""
In search.py, you will implement generic search algorithms which are called by
Pacman agents (in searchAgents.py).
"""
import util
import sys
import copy
class SearchProblem:
"""
This class outlines the structure of a search problem, but doesn't implement
any of the methods (in object-oriented terminology: an abstract class).
You do not need to change anything in this class, ever.
"""
def getStartState(self):
"""
Returns the start state for the search problem.
"""
util.raiseNotDefined()
def goalTest(self, state):
"""
state: Search state
Returns True if and only if the state is a valid goal state.
"""
util.raiseNotDefined()
def getActions(self, state):
"""
Given a state, returns available actions.
Returns a list of actions
"""
util.raiseNotDefined()
def getResult(self, state, action):
"""
Given a state and an action, returns resulting state.
"""
util.raiseNotDefined()
def getCost(self, state, action):
"""
Given a state and an action, returns step cost, which is the incremental cost
of moving to that successor.
"""
util.raiseNotDefined()
def getCostOfActions(self, actions):
"""
actions: A list of actions to take
This method returns the total cost of a particular sequence of actions.
The sequence must be composed of legal moves.
"""
util.raiseNotDefined()
class Node:
"""
Search node object for your convenience.
This object uses the state of the node to compare equality and for its hash function,
so you can use it in things like sets and priority queues if you want those structures
to use the state for comparison.
Example usage:
>>> S = Node("Start", None, None, 0)
>>> A1 = Node("A", S, "Up", 4)
>>> B1 = Node("B", S, "Down", 3)
>>> B2 = Node("B", A1, "Left", 6)
>>> B1 == B2
True
>>> A1 == B2
False
>>> node_list1 = [B1, B2]
>>> B1 in node_list1
True
>>> A1 in node_list1
False
"""
def __init__(self, state, parent, action, path_cost):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def __hash__(self):
return hash(self.state)
def __eq__(self, other):
return self.state == other.state
def __ne__(self, other):
return self.state != other.state
def tinyMazeSearch(problem):
"""
Returns a sequence of moves that solves tinyMaze. For any other maze, the
sequence of moves will be incorrect, so only use this for tinyMaze.
"""
from game import Directions
s = Directions.SOUTH
w = Directions.WEST
return [s, s, w, s, w, w, s, w]
def breadthFirstSearch(problem):
"""
Search the shallowest nodes in the search tree first.
You are not required to implement this, but you may find it useful for Q5.
"""
"*** YOUR CODE HERE ***"
util.raiseNotDefined()
def nullHeuristic(state, problem=None):
"""
A heuristic function estimates the cost from the current state to the nearest
goal in the provided SearchProblem. This heuristic is trivial.
"""
return 0
def iterativeDeepeningSearch(problem: SearchProblem):
"""
Perform DFS with increasingly larger depth. Begin with a depth of 1 and increment depth by 1 at every step.
Your search algorithm needs to return a list of actions that reaches the
goal. Make sure to implement a graph search algorithm.
To get started, you might want to try some of these simple commands to
understand the search problem that is being passed in:
print("Start:", problem.getStartState())
print("Is the start a goal?", problem.goalTest(problem.getStartState()))
print("Actions from start state:", problem.getActions(problem.getStartState()))
Then try to print the resulting state for one of those actions
by calling problem.getResult(problem.getStartState(), one_of_the_actions)
or the resulting cost for one of these actions
by calling problem.getCost(problem.getStartState(), one_of_the_actions)
"""
"*** YOUR CODE HERE ***"
util.raiseNotDefined()
def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
"*** YOUR CODE HERE ***"
util.raiseNotDefined()
# Abbreviations
bfs = breadthFirstSearch
astar = aStarSearch
ids = iterativeDeepeningSearch