Repository navigation
Expand file tree
/
Copy pathproblem.py
More file actions
184 lines (144 loc) · 4.72 KB
/
Copy pathproblem.py
File metadata and controls
184 lines (144 loc) · 4.72 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
#!/usr/bin/python
# -*- coding: utf-8 -*-
"""Classes needed to model a search algorithm."""
import abc
class Problem(abc.ABC):
"""A problem to be solved."""
@abc.abstractmethod
def initial_state(self):
"""Return the initial state for the problem."""
raise NotImplementedError()
@abc.abstractmethod
def is_solution(self, state):
"""Check whether a given state is a solution to the problem."""
raise NotImplementedError()
@abc.abstractmethod
def actions(self, state):
"""Get all possible actions to be executed on a given state."""
raise NotImplementedError()
class Action(abc.ABC):
"""An action for a given problem."""
@abc.abstractmethod
def __call__(self, state):
"""Execute the action on a state."""
raise NotImplementedError()
def __str__(self):
"""The string representation of this action."""
return self.__class__.__name__
def __repr__(self):
"""The string representation of this action."""
return str(self)
class State(abc.ABC):
"""(Intermediate) State in the search for a solution."""
@abc.abstractmethod
def __hash__(self):
"""Get a unique hash for the state."""
raise NotImplementedError()
def __eq__(self, other):
"""Check whether the other object is equal."""
if isinstance(other, self.__class__):
return hash(self) == hash(other)
else:
return False
def __ne__(self, other):
"""Check whether the other object is not equal."""
return not self.__eq__(other)
class ShortestPathProblem(Problem):
"""Basic shortest path problem."""
def __init__(self, adjacency_matrix, node_start, node_end):
"""Initialize an instance of ShortestPathProblem."""
self.adjacency_matrix = adjacency_matrix
self.start = node_start
self.end = node_end
def initial_state(self):
"""
Return the initial state for the problem.
>>> spp = ShortestPathProblem([[0,1],[1,0]], 0, 1)
>>> spp.initial_state()
{index: 0, value: 0, path: [0]}
>>> spp = ShortestPathProblem([[0,1],[1,0]], 1, 0)
>>> spp.initial_state()
{index: 1, value: 0, path: [1]}
"""
return ShortestPathState(self.start, 0)
def is_solution(self, state):
"""
Check whether a given state is a solution to the problem.
>>> spp = ShortestPathProblem([[0,1],[1,0]], 0, 1)
>>> state0 = ShortestPathState(0, 0, [0])
>>> spp.is_solution(state0)
False
>>> state1 = ShortestPathState(1, 0, [0, 1])
>>> spp.is_solution(state1)
True
"""
return state.index == self.end
def actions(self, state):
"""Get all possible actions from the given state."""
index = state.index
valid_actions = [
ShortestPathNodeTraversal(index, other)
for other, valid in enumerate(self.adjacency_matrix[index])
if valid
]
return valid_actions
class ShortestPathNodeTraversal(Action):
"""Node Traversal action for the ShortestPath Problem."""
def __init__(self, start, end):
"""Initialize the node traversal action."""
self.start = start
self.end = end
def __call__(self, state):
"""Execute the node traversal on a given state."""
return ShortestPathState(
self.end,
state.value + 1,
state.path + [self.end]
)
class ShortestPathState(State):
"""(Intermediate) State in the search for a solution."""
def __init__(self, index, value, path=None):
"""
Initialize an instance of ShortestPathState.
>>> s = ShortestPathState(1, 2)
>>> s.index
1
>>> s.value
2
>>> s.path
[1]
"""
self.index = index
self.value = value
self.path = path or [index]
def __repr__(self):
"""
String representation of the state.
>>> s = ShortestPathState(1, 2)
>>> print(s)
{index: 1, value: 2, path: [1]}
>>> print([s])
[{index: 1, value: 2, path: [1]}]
"""
return "{index: %s, value: %s, path: %s}" % (
self.index, self.value, self.path)
def __hash__(self):
"""
Get a unique hash for the state.
>>> s1 = ShortestPathState(1, 2)
>>> hash(s1)
1
>>> s2 = ShortestPathState(1, 3)
>>> hash(s2)
1
>>> s = set([s1])
>>> s2 in s
True
"""
return self.index
def unit_test():
"""Test the module."""
import doctest
doctest.testmod()
if __name__ == '__main__':
unit_test()