-
Notifications
You must be signed in to change notification settings - Fork 0
/
astar.py
62 lines (47 loc) · 1.7 KB
/
astar.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
from move import *
import heapq
from Nodo import Nodo
def astar(puzzle_str):
# return []
puzzle = puzzle_str #"104253876" #sol
# puzzle = "123406785" #no sol
destino = "123456780"
# f,g,h
abierto = [ Nodo(puzzle) ]
abierto_set = set ( abierto )
cerrado = set()
actual = puzzle
while len(abierto) != 0:
# print("Abiertos",len(abierto))
# print("Cerrados",len(cerrado))
actual = heapq.heappop(abierto)
abierto_set.discard(actual)
#print(actual.clave,"-.-.-.-")
cerrado.add( actual )
if actual.clave == destino:
# print("Fin")
respuesta = []
temp = actual
while temp.clave!=puzzle:
#print(temp.clave)
temp = temp.parent
respuesta.append(temp.clave)
respuesta.reverse()
respuesta.pop(0)
return respuesta
movs = get_mov(actual.clave)
for m in movs:
nuevo_nodo = Nodo ( movement(actual.clave,m) , actual)
# padres[nuevo_nodo]=actual[3]
if nuevo_nodo not in cerrado:
nuevo_nodo.g = actual.g + distancia(actual.clave,nuevo_nodo.clave)
nuevo_nodo.h = distancia(nuevo_nodo.clave,destino)
nuevo_nodo.f = nuevo_nodo.g+nuevo_nodo.h
if nuevo_nodo in abierto_set:
if all( nuevo_nodo.g > x.g for x in abierto ) :
# print("here")
continue
heapq.heappush(abierto, nuevo_nodo )
abierto_set.add(nuevo_nodo)
print ( "Ruta no encontrada")
return []