• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

BlodyGrl

Uma espécie de bfs...

17 mensagens neste tópico

Pois bem, neste momento tenho um trabalho entre mãos no qual necessito de usar uma espécie de bfs, mais propriamente o find_all_paths()... Mas o que preciso é de o fazer SEM recursão e é isso que me está a dar o cabo dos trabalhos porque o programa em si funciona, e bem mas quando lhe ponho um input grande ele dá o berro... Penso que seja do uso de recursões, assim peço aos meus amigos do Portugal a progrmaar que me ajudem neste pequeno "problema". Deixo aqui o código, e como sempre, peço que me ajudem e não que me digam as coisas (tenho que aprender e não é a copiar que o consigo ^^).

def find_all_paths(mapa_grafo,partida,destino,caminho=[]):
    caminho=caminho+[partida]
    if partida==destino:
        return [caminho]
    if partida not in mapa_grafo.keys():
        return []
    caminhos=[]
    for i in mapa_grafo[partida]:
        if i not in caminho:
            outros_caminhos=find_all_paths(mapa_grafo,i,destino,caminho)
            for j in outros_caminhos:
                caminhos+=[j]
    return caminhos

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Convinha saber qual é a estrutura de mapa_grafo para ver o que estás a fazer dentro do "for i in mapa_grafo[partida]". :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sem recursão? Queres isso duma forma iterativa e não de forma recursiva, é isso?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim , é isso... O mapa_grafo é literalmente um grafo.

Do género:

{1:[2,3,4],2:[4,5],3:[4,6],4:[7],5:[7],6:[7]}...

Dei-te este porque é este que estou a usar como teste. ^^

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

def find_all_paths(mapa_grafo,partida,destino):
    if partida==destino:
        return [caminho]
    if partida not in mapa_grafo.keys():
        return []

    # Lista de listas que fica com as solucoes possiveis
    solucao=[]
    
    # O primeiro ponto e' adicionado
    caminhos=[partida]

    while True:
        try:
            # O caminho mais antigo que ainda nao foi testado
            path=caminhos[0]
            caminhos.remove(path) # Remover para nao repetir
        except:
            break # Todas as combinacoes de caminhos foram testadas

        if path%10==destino: # Se o ultimo digito (ultimo vertice) for o destino
             solucao.append(list(map(int,str(path)))) # adicionar a solucao
             # ^ o list(map(int,str(path))) e' para
             # ficar com a solucao em lista e nao em int

        # Como ainda nao e' o destino, vamos testar todas as conexoes
        # que o ultimo vertice tem
        for conn in mapa_grafo[path%10]:
            if str(path).count(str(conn))==0: # Se ainda nao o visita'mos
                 caminhos.append(path*10+conn) # visitar

    return solucao


grafo={1:[2,3,4],2:[4,5],3:[4,5,6],4:[1],5:[4],6:[3]}
print find_all_paths(grafo,1,5)

Tive de modificar o teu grafo porque tu tens 5:[7],6:[7] e não existe vértice 7. ;)

Se não percebeste alguma coisa, pergunta que eu respondo. :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois não existe porque isso são caminhos directos e eu queria chegar do 1 ao 7 por isso podia ir assim directamente. ;)

Agora vou tentar ver algoritmo! Obrigado! ^^

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não percebi porquê é que usaste o %10 e o *10... Calculo que tenha a ver com algum problema que tenha aparecido mas não vejo qual.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois não existe porque isso são caminhos directos e eu queria chegar do 1 ao 7 por isso podia ir assim directamente. ;)

Agora vou tentar ver algoritmo! Obrigado! ^^

Ah... Entao as arestas podem ser só de um sentido... Era só adiconar um 7 para uma linha vazia no mapa. (Não tinha entendido) :D

Não percebi porquê é que usaste o %10 e o *10... Calculo que tenha a ver com algum problema que tenha aparecido mas não vejo qual.

Não deve ser a melhor maneira, mas foi a que me lembrei.

o %10 é para veres o último dígito do número. Por exemplo: fizeste 1523 (do 1 para o 5 para o 2 para o 3) e o teu destino é 6. Ao fazeres 1523%10 vai-te dar 3 que é o último vértice onde estiveste. :)

Quanto ao *10 é a mesma coisa só que ao contrário. tens o caminho 1523 e queres adicionar as conexões do 3 que são: 2,6. Ao fazeres 1523*10 vai-te dar 15230 e depois fazes o + conn que é como quem diz 15230 + 6. :)

Percebeste?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Agora percebi... ^^ Não reparei que estavas a trabalhar com int's. xD

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Falando em recursões... Há alguma forma de fazer uma recursão (sem recursão, isto é com while's ou assim) que nos capte as linhas que estão antes do whiole. Exemplo:

Eu tinha:

Código

GeSHi (python):

variavel=[]

def guia_turistico():

    global variavel

    mapa=[int(i) for i in raw_input().split()]

    if sum(mapa)>0:

        bla bla bla

        guia_turistico()

    else:

        faz o output

Created by GeSHI 1.0.7.20

Isto porque quero que ele deixe de receber input's quando o input for "0 0". Mas tenho que pôr o "bla bla bla"  a funcionar para todos os casos mas não o posso fazer com recursão...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Esquece a dúvida... xD

Mas se eu lhe der um dicionário muito grande, com muitas partes que não sejam bidireccionais ele vai crashar à mesma e não adiantou d enada tirar a recursão. ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tharis, e se quisermos utilizar um grafo do mesmo género que a BlodyGrl  mencionou acima?

{1:[2,3,4],2:[4,5],3:[4,6],4:[7],5:[7],6:[7]}

Eu já estive a tentar modificar o teu código, mas não consegui nada...

O meu programa está a funcionar perfeito, mas quando o input é gigante (exemplos de 3 mil e tal linhas...) isso vai criar um grafo igualmente gigante!! E quando assim é, o programa utilizado para encontrar todos os caminhos de um ponto ao outro, por causa da recursão, demora mais tempo do que é permitido...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Respondam à nossa dúvida por favor! ;) Passar ou não à cadeira pode depnder disso... :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Respondam à nossa dúvida por favor! :) Passar ou não à cadeira pode depnder disso... :)

Peço desculpa, mas não tive acesso à Internet nestes últimos dois dias.

Esquece a dúvida... xD

Mas se eu lhe der um dicionário muito grande, com muitas partes que não sejam bidireccionais ele vai crashar à mesma e não adiantou d enada tirar a recursão. :)

Tharis, e se quisermos utilizar um grafo do mesmo género que a BlodyGrl  mencionou acima?

Eu já estive a tentar modificar o teu código, mas não consegui nada...

O meu programa está a funcionar perfeito, mas quando o input é gigante (exemplos de 3 mil e tal linhas...) isso vai criar um grafo igualmente gigante!! E quando assim é, o programa utilizado para encontrar todos os caminhos de um ponto ao outro, por causa da recursão, demora mais tempo do que é permitido...

Antes de mais gostaria de saber se o vosso crash significa que o programa pára e dá erro (Traceback), se fica parado a calcular ou outra coisa qualquer.

Para o 2o caso (mais provável) temos de estar cientes de que Python é das linguagens mais lentas que existem (grande parte por ser interpretado). Depois, em relação ao tamanho do Input, temos a Big-O Notation que nos dá uma noção da complexidade de tempo.

Para um BFS, a complexidade de tempo é O( | V | + | E | ) (em que o V são os Vértices e o E as Arestas (Edges em Inglês)). Podem ter uma noção do tempo com isto. Por exemplo: com o exemplo que tenho lá em cima vêem quanto tempo demorou e vêem qual a complexidade de tempo. Depois, fazem uma proporção (com o novo input) para verem se o programa pode correr o input em tempo possível.

Mais informação sobre um BFS.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obg pela resposta Tharis.

O que se passa é que o programa fica parado a calcular todos os caminhos possiveis entre 2 pontos.

Com exemplos relativamente pequenos, não nos preocupamos com o tempo de execução, pois até 4 segundos (que é o tempo limite de execução do programa) dá perfeitamente para grafos relativamente pequenos. Mas quando existem inputs com 99 vértices, e 3658 arestas, isto vai criar um grafo enorme.

No programa que deixaste, vou tentar modifica-lo para aceitar nós de 2 digitos, em vez de nós de valor unitário (a tal parte do %10 e *10 :)). Depois digo qq coisa em relação a isso...

A ideia do problema que temos em mão é encontrar o caminho em que seja possivel passar mais pessoas de um ponto ao outro. Claro está que cada aresta está associado um valor, que é o numero de pessoas que é possivel passar entre os pontos associados.

Se tiveres alguma ideia de como fazer isto, agradecia-te imenso.

Se quiseres, posso-te enviar o q tenho feito por PM para que possas entenderes melhor o que fiz, e quem sabe, dar alguma ideia para optimizar o que está feito.

Obg :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não costumo seguir esta secção, só vi o tópico agora. Um amigo meu tem essa cadeira e este problema pode ser encontrado aqui. Mas a prof puxou pelos inputs e uma solução O(N^3) não passava, era preciso melhor :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora