-
Notifications
You must be signed in to change notification settings - Fork 0
/
4-25.py
122 lines (105 loc) · 3.86 KB
/
4-25.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
# -----------------
# User Instructions
#
# Write a function, shortest_path_search, that generalizes the search algorithm
# that we have been using. This function should have three inputs, a start state,
# a successors function, and an is_goal function.
#
# You can use the solution to mc_problem as a template for constructing your
# shortest_path_search. You can also see the example is_goal and successors
# functions for a simple test problem below.
def shortest_path_search(start, successors, is_goal):
"""Find the shortest path from start state to a state
such that is_goal(state) is true."""
# your code here
if (is_goal(start)): return start;
explored = set()
frontier = [[start]]
while frontier:
path = frontier.pop(0)
s = path[-1]
#print (path)
print (frontier)
print (explored)
for (state, action) in successors(s).items():
if state not in explored:
explored.add(state)
nextPath = path+[action, state]
if is_goal(state):
print ('the end: '+str(nextPath))
return nextPath
else:
frontier.append(nextPath)
return Fail
def mc_problem1(start=(3, 3, 1, 0, 0, 0), goal=None):
"""Solve the missionaries and cannibals problem.
State is 6 ints: (M1, C1, B1, M2, C2, B2) on the start (1) and other (2) sides.
Find a path that goes from the initial state to the goal state (which, if
not specified, is the state with no people or boats on the start side."""
if goal is None:
goal = (0, 0, 0) + start[:3]
if start == goal:
return [start]
explored = set() # set of states we have visited
frontier = [ [start] ] # ordered list of paths we have blazed
while frontier:
path = frontier.pop(0)
s = path[-1]
for (state, action) in csuccessors(s).items():
if state not in explored:
explored.add(state)
path2 = path + [action, state]
if state == goal:
return path2
else:
frontier.append(path2)
return Fail
Fail = []
def csuccessors(state):
"""Find successors (including those that result in dining) to this
state. But a state where the cannibals can dine has no successors."""
M1, C1, B1, M2, C2, B2 = state
## Check for state with no successors
if C1 > M1 > 0 or C2 > M2 > 0:
return {}
items = []
if B1 > 0:
items += [(sub(state, delta), a + '->')
for delta, a in deltas.items()]
if B2 > 0:
items += [(add(state, delta), '<-' + a)
for delta, a in deltas.items()]
return dict(items)
def add(X, Y):
"add two vectors, X and Y."
return tuple(x+y for x,y in zip(X, Y))
def sub(X, Y):
"subtract vector Y from X."
return tuple(x-y for x,y in zip(X, Y))
deltas = {(2, 0, 1, -2, 0, -1): 'MM',
(0, 2, 1, 0, -2, -1): 'CC',
(1, 1, 1, -1, -1, -1): 'MC',
(1, 0, 1, -1, 0, -1): 'M',
(0, 1, 1, 0, -1, -1): 'C'}
Fail = []
# --------------
# Example problem
#
# Let's say the states in an optimization problem are given by integers.
# From a state, i, the only possible successors are i+1 and i-1. Given
# a starting integer, find the shortest path to the integer 8.
#
# This is an overly simple example of when we can use the
# shortest_path_search function. We just need to define the appropriate
# is_goal and successors functions.
def is_goal(state):
if state == 8:
return True
else:
return False
def successors(state):
successors = {state + 1: '->',
state - 1: '<-'}
return successors
#test
assert shortest_path_search(5, successors, is_goal) == [5, '->', 6, '->', 7, '->', 8]