Boa noite, estou a desenvolver em python um programa capaz de procurar um caminho entre duas cidades de Portugal.
Para isso tenho que utilizar métodos de procura cega e de procura heurística.
Neste momento estou a fazer o de Custo Uniforme, mas o resultado nem a nulo. Será que alguém é capaz de me ajudar a encontrar onde estou a errar?
from queue import Queue, PriorityQueue
def ucs_weight(start, end, weights):
return weights.get((start, end), 10e100) if weights else 1
def ucs(graph, start, end, weights):
frontier = PriorityQueue()
frontier.put((0, start))
explored = []
while frontier:
ucs_w, current_node = frontier.get()
explored.append(current_node)
for node in graph[current_node]:
if node not in explored:
if current_node == end:
return
total_cost = ucs_w + ucs_weight(current_node, node, weights), node
return frontier.put(total_cost)
if __name__ == "__main__":
ucs_test_graph = {
'Viana do Castelo': ['Braga', 'Porto'],
'Braga': ['Porto','Vila Real', 'Viana do Castelo'],
'Vila Real': ['Braga', 'Porto', 'Viseu', 'Guarda', 'Bragança'],
'Bragança': ['Vila Real', 'Guarda'],
'Porto': ['Viana do Castelo', 'Braga','Vila Real', 'Viseu', 'Aveiro'],
'Aveiro': ['Porto', 'Viseu', 'Coimbra', 'Leiria'],
'Viseu': ['Porto','Vila Real', 'Aveiro', 'Guarda', 'Coimbra'],
'Guarda': ['Bragança', 'Viseu', 'Vila Real', 'Castelo Branco'],
'Coimbra': ['Viseu','Castelo Branco', 'Aveiro', 'Leiria'],
'Castelo Branco': ['Portalegre', 'Guarda', 'Coimbra', 'Évora'],
'Leiria': ['Santarém', 'Aveiro', 'Lisboa', 'Coimbra'],
'Santarém': ['Leiria', 'Lisboa', 'Évora'],
'Portalegre': ['Castelo Branco', 'Évora'],
'Lisboa': ['Setúbal','Évora', 'Santarém', 'Leiria'],
'Évora': ['Portalegre','Castelo Branco', 'Santarém', 'Lisboa', 'Setúbal', 'Beja'],
'Setúbal': ['Évora','Lisboa', 'Beja', 'Faro'],
'Beja': ['Évora', 'Setúbal', 'Faro'],
'Faro': ['Setúbal', 'Beja']
}
ucs_test_weight = {
('Viana do Castelo', 'Braga'): 48,
('Viana do Castelo', 'Porto'): 71,
('Braga', 'Porto'): 53,
('Braga', 'Vila Real'): 106,
('Braga', 'Viana do Castelo'): 48,
('Vila Real', 'Braga'): 106,
('Vila Real', 'Porto'): 116,
('Vila Real', 'Viseu'): 110,
('Vila Real', 'Guarda'): 157,
('Vila Real', 'Bragança'): 137,
('Bragança', 'Guarda'): 202,
('Bragança', 'Vila Real'): 137,
('Porto', 'Viana do Castelo'): 71,
('Porto', 'Braga'): 53,
('Porto', 'Vila Real'): 116,
('Porto', 'Viseu'): 133,
('Porto', 'Aveiro'): 68,
('Aveiro', 'Viseu'): 95,
('Aveiro', 'Porto'): 68,
('Aveiro', 'Coimbra'): 68,
('Aveiro', 'Leiria'): 115,
('Viseu', 'Porto'): 133,
('Viseu', 'Vila Real'): 110,
('Viseu', 'Aveiro'): 95,
('Viseu', 'Guarda'): 85,
('Viseu', 'Coimbra'): 96,
('Guarda', 'Bragança'): 202,
('Guarda', 'Vila Real'): 157,
('Guarda', 'Viseu'): 85,
('Guarda', 'Castelo Branco'): 106,
('Coimbra', 'Viseu'): 96,
('Coimbra', 'Castelo Branco'): 159,
('Coimbra', 'Aveiro'): 68,
('Coimbra', 'Leiria'): 67,
('Castelo Branco', 'Portalegre'): 80,
('Castelo Branco', 'Coimbra'): 159,
('Castelo Branco', 'Guarda'): 106,
('Castelo Branco', 'Évora'): 203,
('Leiria', 'Santarém'): 70,
('Leiria', 'Aveiro'): 115,
('Leiria', 'Lisboa'): 129,
('Leiria', 'Coimbra'): 67,
('Santarém', 'Leiria'): 70,
('Santarém', 'Lisboa'): 78,
('Santarém', 'Évora'): 117,
('Portalegre', 'Castelo Branco'): 80,
('Portalegre', 'Évora'): 131,
('Lisboa', 'Setúbal'): 50,
('Lisboa', 'Évora'): 150,
('Lisboa', 'Santarém'): 78,
('Lisboa', 'Leiria'): 129,
('Évora', 'Portalegre'): 131,
('Évora', 'Castelo Branco'): 203,
('Évora', 'Santarém'): 117,
('Évora', 'Lisboa'): 150,
('Évora', 'Setúbal'): 103,
('Évora', 'Beja'): 78,
('Setúbal', 'Évora'): 103,
('Setúbal', 'Lisboa'): 50,
('Setúbal', 'Beja'): 142,
('Setúbal', 'Faro'): 249,
('Beja', 'Évora'): 78,
('Beja', 'Setúbal'): 142,
('Beja', 'Faro'): 152,
('Faro', 'Setúbal'): 249,
('Faro', 'Beja'): 152
}
print(ucs(ucs_test_graph, 'Coimbra', 'Faro', ucs_test_weight))
Muito obrigada