-
Notifications
You must be signed in to change notification settings - Fork 0
/
A_star_m.py
85 lines (72 loc) · 3.5 KB
/
A_star_m.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
import math
import time
from sys import getsizeof
from construir_grafo_m import *
def harvesine(lon1, lat1, lon2, lat2):
# haversine formula
a = math.sin(math.radians(lat2) - math.radians(lat1)/2)**2 + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(math.radians(lon2) - math.radians(lon1) /2)**2
c = 2 * math.asin(math.sqrt(a))
return c * 6371
def euclidean_distance(lat1, lon1, lat2, lon2):
# Calculando a distância euclidiana
return math.sqrt((math.radians(lat2) - math.radians(lat1))**2 + (math.radians(lon2) - math.radians(lon1))**2) * 6371.0
def A_star_harvesine(start_node, end_node, graph, coordinates, timeout=10):
runtime = time.time()
closed = []
opened = []
g_cost = {}
g_cost[start_node[0]] = 0
opened.append(start_node)
expanded_nodes = 0
sum_fator_ramificacao = 0
while len(opened) > 0:
used_memory = getsizeof(closed) + getsizeof(opened) + getsizeof(g_cost) + getsizeof(expanded_nodes)
f_cost_opened_list = [node[1] for node in opened]
min_f_cost = min(f_cost_opened_list)
chosen_index = f_cost_opened_list.index(min_f_cost)
node = opened[chosen_index][0]
closed.append(opened[chosen_index])
opened.pop(chosen_index)
if node == end_node[0]:
break
for item in graph[node]:
if item[0] in [closed_item[0] for closed_item in closed]:
continue
g_cost[item[0]] = g_cost[node] + item[1]
f_cost_node = g_cost[node] + harvesine(coordinates[item[0]][0][0],coordinates[item[0]][0][1], coordinates[end_node[0]][0][0], coordinates[end_node[0]][0][1]) + item[1]
opened.append([item[0], f_cost_node])
expanded_nodes = expanded_nodes + 1
sum_fator_ramificacao += len(graph[item[0]])
if (time.time() - runtime) > timeout:
break
return closed, expanded_nodes, used_memory, (sum_fator_ramificacao/len(closed)), (time.time() - runtime)
def A_star_euclidian_distance(start_node, end_node, graph, coordinates, timeout=10):
runtime = time.time()
closed = []
opened = []
g_cost = {}
g_cost[start_node[0]] = 0
opened.append(start_node)
expanded_nodes = 0
sum_fator_ramificacao = 0
while len(opened) > 0:
used_memory = getsizeof(closed) + getsizeof(opened) + getsizeof(g_cost) + getsizeof(expanded_nodes)
f_cost_opened_list = [node[1] for node in opened]
min_f_cost = min(f_cost_opened_list)
chosen_index = f_cost_opened_list.index(min_f_cost)
node = opened[chosen_index][0]
closed.append(opened[chosen_index])
opened.pop(chosen_index)
if node == end_node[0]:
break
for item in graph[node]:
if item[0] in [closed_item[0] for closed_item in closed]:
continue
g_cost[item[0]] = g_cost[node] + item[1]
f_cost_node = g_cost[node] + euclidean_distance(coordinates[item[0]][0][0],coordinates[item[0]][0][1], coordinates[end_node[0]][0][0], coordinates[end_node[0]][0][1]) + item[1]
opened.append([item[0], f_cost_node])
expanded_nodes = expanded_nodes + 1
sum_fator_ramificacao += len(graph[item[0]])
if (time.time() - runtime) > timeout:
break
return closed, expanded_nodes, used_memory, (sum_fator_ramificacao/len(closed)), (time.time() - runtime)