-
Notifications
You must be signed in to change notification settings - Fork 0
/
puzzle.py
160 lines (119 loc) · 4.88 KB
/
puzzle.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
from node import Node
import random
goal = [['1', '2', '3'],
['4', '5', '6'],
['7', '8', '_']]
def generate_puzzle():
""" Gera um novo puzzle """
new_puzzle = [['1', '2', '3'],
['4', '5', '6'],
['7', '8', '_']]
x_pos, y_pos = 2, 2
for i in range(random.randint(30, 90)):
move_coords = [[x_pos, y_pos - 1], [x_pos, y_pos + 1], [x_pos - 1, y_pos], [x_pos + 1, y_pos]]
target_x, target_y = move_coords[random.randint(0, 3)]
if 0 <= target_x < len(new_puzzle) and 0 <= target_y < len(new_puzzle):
new_puzzle[x_pos][y_pos], new_puzzle[target_x][target_y] = \
new_puzzle[target_x][target_y], new_puzzle[x_pos][y_pos]
x_pos, y_pos = target_x, target_y
return new_puzzle
def calculate_simple_heuristic_value(start):
""" Calcula a quantidade de posições do estado que estão errados """
temp = 0
for row_index, row in enumerate(start):
for column_index, column in enumerate(row):
if start[row_index][column_index] != goal[row_index][column_index]:
temp += 1
return temp
def calculate_complex_heuristic_value(start):
""" Calcula o quão longe cada elemento está de sua posição final
Formula: v = |(x1 + y1) - (x2 + y2)| para cada elemento
:returns soma de todos os v """
temp = 0
temp_start = group_list_by_index(start)
temp_goal = {
'1': 0,
'2': 1,
'3': 2,
'4': 1,
'5': 2,
'6': 3,
'7': 2,
'8': 3,
'_': 4,
}
for key, value in temp_start.items():
temp += abs(value - temp_goal.get(key))
return temp
def group_list_by_index(board_state):
""" Agrupa o estado pela soma de suas coordenadas
:returns dicionário chave = elemento, valor = coordenadas do elemento"""
temp_dict = {}
for row_index, row in enumerate(board_state):
for column_index, column in enumerate(row):
temp_dict[str(column)] = row_index + column_index
return temp_dict
class Puzzle:
def __init__(self):
""" Initialize puzzle """
self.open_nodes = []
self.closed_nodes = []
self.max_open_nodes = 1
def solve_puzzle(self, complexity=0):
"""
:param complexity
0 - Custo Uniforme;
1 - Heurística Simples
2 - Heurística um pouco mais complexa
:return:
"""
self.open_nodes = []
self.closed_nodes = []
self.max_open_nodes = 1
start = generate_puzzle()
heuristic_value = 0
if complexity == 1:
heuristic_value = calculate_simple_heuristic_value(start)
elif complexity == 2:
heuristic_value = calculate_complex_heuristic_value(start)
start_node = Node(start, None, heuristic_value)
self.open_nodes.append(start_node)
while self.open_nodes:
current_node = self.open_nodes.pop(0)
""" Se o valor for 0, isso quer dizer chegou no estado final """
if calculate_simple_heuristic_value(current_node.board_data) == 0:
self.closed_nodes.append(current_node)
break
for child_node in current_node.generate_child(self.closed_nodes, self.open_nodes):
if complexity == 0:
child_node.heuristic_value = child_node.cost
elif complexity == 1:
child_node.heuristic_value = calculate_simple_heuristic_value(
child_node.board_data) + child_node.cost
elif complexity == 2:
child_node.heuristic_value = calculate_complex_heuristic_value(
child_node.board_data) + child_node.cost
self.open_nodes.append(child_node)
self.closed_nodes.append(current_node)
self.max_open_nodes = max(self.max_open_nodes, len(self.open_nodes))
self.open_nodes.sort(key=lambda x: x.heuristic_value, reverse=False)
self.print_outcome()
def print_outcome(self):
temp_node = self.closed_nodes.pop()
node_path = [temp_node.board_data]
while temp_node.parent_node:
temp_node = temp_node.parent_node
node_path.append(temp_node.board_data)
for board in reversed(node_path):
print("")
print(" | ")
print(" \\\'/ \n")
for row in board:
for column in row:
print(column, end=" ")
print("")
print("O total de nodos visitados: {}".format(len(self.closed_nodes)))
print("O total de nodos expandidos / criados: {}".format(
len(self.closed_nodes) + len(self.open_nodes) - 1))
print("O maior tamanho da fronteira durante a busca: {}".format(self.max_open_nodes))
print("\nO tamanho do caminho: {}".format(len(node_path)))