Algoritmo en python 3 para realizar la búsqueda A* (A estrella)

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#!/usr/bin/python -w
 
 
 
 
 
# Inicializamos las listas de abiertos y cerradas en vacio
 
 
# Inicializamos todos los estados como arreglos de clave y valor,
 
 
# con sus respectivos estados vecinos como clave y el costo como valor
 
 
# Establecemos la lista de estados, para luego accederla mediante el indice
 
 
# y tambien la lista de distancias entre cada par de estados.
 
 
opened = []
 
 
closed = []
 
 
q0 = {1:5, 2:4, 3:11}
 
 
q1 = {0:5, 3:6, 4:15}
 
 
q2 = {0:4, 3:5, 4:12}
 
 
q3 = {0:11, 1:6, 2:5, 4:5}
 
 
q4 = {1:15, 2:12, 3:5}
 
 
states = [q0, q1, q2, q3, q4]
 
 
distances = [[0, 5, 4, 11, 17], [5, 0, 5, 6, 15], [4, 5, 0, 5, 12], [11, 6, 5, 0, 5], [17, 15, 12, 5, 0]]
 
 
 
 
 
# Funcion para obtener el camino entre 2 estados, mediante el algoritmo de busqueda A*
 
 
def get_way(start, goal):
 
 
    actual = start
 
 
    # "Importamos" nuestra variable global para poderla modificar localmente
 
 
    global opened
 
 
    # Agregamos el estado actual a la lista de estados abiertos
 
 
    opened.append(actual)
 
 
    finalized = False
 
 
    # No terminaremos hasta que no hayamos llegado a el estado meta
 
 
    while not finalized:
 
 
        # Si el estado actual es igual a la meta, entonces agregamos al estado acual
 
 
        # a la lista de cerrados y devolvemos la lista la cual indica nuestro camino
 
 
        if actual == goal:
 
 
            closed.append(actual)
 
 
            return closed
 
 
        else:
 
 
            # Si no, tomamos todos los estados vecinos del estado actual que no se incluyen
 
 
            # en la lista de estados cerrados, y los agregamos a la lista de abiertos
 
 
            opened = [k for k in states[actual].keys() if k not in closed]
 
 
            # Cerramos el estado actual
 
 
            closed.append(actual)
 
 
            # Ahora tomamos como estado actual, aquel estado vecino con el menor costo
 
 
            # y distancia
 
 
            actual = less_f_score(actual, opened)
 
 
            # Limpiamos la lista de abiertos y realizamos una iteracion mas
 
 
            opened = []
 
 
 
 
 
# Funcion para determinar el estado vecino con el menor costo y distancia
 
 
def less_f_score(actual, opened):
 
 
    # Obtenemos la suma del costo y la distancia menor, para un conjunto de estados vecinos
 
 
    less = min([states[actual][state] + distances[state][goal] for state in opened])
 
 
    # Recorremos la lista de vecinos
 
 
    for state in opened:
 
 
        # Si la suma del costo y la distancia para un estado es igual a la menor
 
 
        # entonces devolvemos dicho estado
 
 
        if states[actual][state] + distances[state][goal] == less:
 
 
            return state
 
 
 
 
 
if __name__ == "__main__":
 
 
    # Ingresamos los valores para el estado inicial y el estado meta
 
 
    start = input("Input the start state: ")
 
 
    goal = input("Input the goal state: ")
 
 
    try:
 
 
        # Los convertimos a enteros
 
 
        start = int(start)
 
 
        goal = int(goal)
 
 
    except:
 
 
    print("Invalid number")
 
 
    # Obtenemos el camino el cual es una lista de estados
 
 
    way = get_way(start, goal)
 
 
    # Imprimimos la respuesta
 
 
    print("<", end = " ") 
 
 
    for state in way:
 
 
        print(state, end = " ")
 
 
    print(">")
 
 
    # Terminamos

 




Copyright(c) 2017 - PythonBlogs.com
By using this website, you signify your acceptance of Terms and Conditions and Privacy Policy
All rights reserved