← Desenvolvimento

[Ajuda] python

Lida 1342 vezes

Offline

OrquideaCampos 
Membro
Mensagens 1 Gostos 0
Troféus totais: 7
Trófeus: (Ver todos)
Topic Starter Level 2 First Post Windows User Level 1 Second year Anniversary One year Anniversary

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?

Código: [Seleccione]
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
Offline

tomasantunes 
Membro
Mensagens 5 Gostos 3
Troféus totais: 13
Trófeus: (Ver todos)
Linux User Level 3 Windows User Combination Topic Starter Level 2 Level 1 First Post Signature Webmaster

Este artigo tem uma explicação. https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/

Tem que passar uma lista com as cidades percorridas.

Código: [Seleccione]
from queue import Queue, PriorityQueue
import sys

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.qsize() > 0):
ucs_w, current_node = frontier.get()
if current_node[-1] == end:
print(frontier.qsize())
return "Points: " + str(ucs_w) + " Cities: " + str(current_node)
else:
for item in graph[current_node[-1]]:
if item not in explored:
total_cost = ucs_w + ucs_weight(current_node[-1], item, weights)
next_node = (total_cost, current_node + [item])
frontier.put(next_node)
explored.append(item)


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))