Ir para o conteúdo
BlodyGrl

Uma espécie de bfs...

Mensagens Recomendadas

BlodyGrl    0
BlodyGrl

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

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. ^^

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Tharis    3
Tharis

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

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! ^^

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Tharis    3
Tharis

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?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
BlodyGrl    0
BlodyGrl

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
fastio    0
fastio

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Tharis    3
Tharis

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
fastio    0
fastio

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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

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


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade