-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy pathsolver.py
117 lines (92 loc) · 5.21 KB
/
solver.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
from queue import PriorityQueue, Queue
from game_state import GameState
import numpy as np
import time
class Solver():
def __init__(self, init_state, goal_state, heuristic_func = "manhattan", max_iter = 2500):
self.__init_state = init_state
self.__goal_state = goal_state
self.__heuristic_func = heuristic_func
self.__MAX = 100000
self.__max_iter = max_iter
self.__path = []
self.__number_of_steps = 0
self.__summary = ""
def set_max_iter(self, max_iter):
self.__max_iter = max_iter
def get_path(self):
return self.__path
def get_summary(self):
return self.__summary
def solve_a_star(self):
x_axis = [1, 0, -1, 0]
y_axis = [0, 1, 0, -1]
level = 0
visited_nodes = set()
start_time = time.clock()
nodes = PriorityQueue(self.__MAX)
init_node = GameState(self.__init_state.flatten().tolist(), self.__goal_state.flatten().tolist(), level, parent = None, heuristic_func = self.__heuristic_func)
nodes.put(init_node)
epochs = 0
while nodes.qsize() and epochs <= self.__max_iter:
epochs += 1
cur_node = nodes.get()
cur_state = cur_node.get_state()
if str(cur_state) in visited_nodes:
continue
visited_nodes.add(str(cur_state))
if cur_state == self.__goal_state.flatten().tolist():
self.__summary = str("A* took " + str(cur_node.get_level()) + " steps to get from initial state to the desired goal, visited total of " + str(epochs) + " nodes, and took around " + str(np.round(time.clock() - start_time, 4)) + " seconds to reach the desired solution.")
while cur_node.get_parent():
self.__path.append(cur_node)
cur_node = cur_node.get_parent()
break
empty_tile = cur_state.index(0)
i, j = empty_tile // self.__goal_state.shape[0], empty_tile % self.__goal_state.shape[0]
cur_state = np.array(cur_state).reshape(self.__goal_state.shape[0], self.__goal_state.shape[0])
for x, y in zip(x_axis, y_axis):
new_state = np.array(cur_state)
if i + x >= 0 and i + x < self.__goal_state.shape[0] and j + y >= 0 and j + y < self.__goal_state.shape[0]:
new_state[i, j], new_state[i+x, j+y] = new_state[i+x, j+y], new_state[i, j]
game_state = GameState(new_state.flatten().tolist(), self.__goal_state.flatten().tolist(), cur_node.get_level() + 1, cur_node, self.__heuristic_func)
if str(game_state.get_state()) not in visited_nodes:
nodes.put(game_state)
if epochs > self.__max_iter:
print('This grid setting is not solvable')
return self.__path
def solve_bfs(self):
x_axis = [1, 0, -1, 0]
y_axis = [0, 1, 0, -1]
level = 0
visited_nodes = set()
start_time = time.clock()
nodes = Queue(self.__MAX)
init_node = GameState(self.__init_state.flatten().tolist(), self.__goal_state.flatten().tolist(), level, parent = None, heuristic_func = self.__heuristic_func)
nodes.put(init_node)
epochs = 0
while nodes.qsize() and epochs <= self.__max_iter:
epochs += 1
cur_node = nodes.get()
cur_state = cur_node.get_state()
if str(cur_state) in visited_nodes:
continue
visited_nodes.add(str(cur_state))
if cur_state == self.__goal_state.flatten().tolist():
self.__summary = str("BFS took " + str(cur_node.get_level()) + " steps to get from initial state to the desired goal, visited total of " + str(epochs) + " nodes, and took around " + str(np.round(time.clock() - start_time, 4)) + " seconds to reach the desired solution.")
while cur_node.get_parent():
self.__path.append(cur_node)
cur_node = cur_node.get_parent()
break
empty_tile = cur_state.index(0)
i, j = empty_tile // self.__goal_state.shape[0], empty_tile % self.__goal_state.shape[0]
cur_state = np.array(cur_state).reshape(self.__goal_state.shape[0], self.__goal_state.shape[0])
for x, y in zip(x_axis, y_axis):
new_state = np.array(cur_state)
if i + x >= 0 and i + x < self.__goal_state.shape[0] and j + y >= 0 and j + y < self.__goal_state.shape[0]:
new_state[i, j], new_state[i+x, j+y] = new_state[i+x, j+y], new_state[i, j]
game_state = GameState(new_state.flatten().tolist(), self.__goal_state.flatten().tolist(), cur_node.get_level() + 1, cur_node, self.__heuristic_func)
if str(game_state.get_state()) not in visited_nodes:
nodes.put(game_state)
if epochs > self.__max_iter:
print('This grid setting is not solvable')
return self.__path