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

BlodyGrl

Jaula

23 mensagens neste tópico

Bem, meninos tenho mais um trabalho(2 aliás mas esta é a minha parte do grupo :D). Deixo aqui o enunciado e aquilo que já fiz, além dos problemas que o programa me está a dar e das  minhas ideias para o fazer.

Agradecia a ajuda de todos. *.*

Beijinhos *

Enunciado

Um animal vai ser transportado por via terrestre dum jardim zoológico para outro ao abrigo dum protocolo de intercâmbio de espécies raras. A viagem será efectuada numa jaula rectangular, cujas dimensões (comprimento, largura e altura) terão de estar dentro de certos intervalos. Essas dimensões estão ainda condicionadas quer pela infra-estrutura da rede de transportes quer pelo tipo de veículos que poderão assegurar o transporte em cada troço do trajecto. O problema foi analisado por uma equipa técnica que forneceu a capacidade de cada troço da rede, tendo já em conta o tipo de veículos disponíveis. Para reduzir o stress do animal, é fortemente recomendado que a base da jaula tenha comprimento máximo. Qual será esse valor?

Input

Na primeira linha tem cinco inteiros separados por um espaço: largura mínima e máxima, comprimento mínimo e máximo, e altura mínima da jaula. A segunda linha tem dois inteiros que identificam a origem e o destino. Cada uma das restantes linhas, com excepção da última, tem cinco inteiros separados por espaços: os dois primeiros identificam os extremos dum troço, e os seguintes os valores máximos para a largura, comprimento e altura da jaula, se o trajecto incluir esse troço. A última linha tem o valor -1. As dimensões encontram-se em decímetros. Qualquer ligação é bidireccional. Os locais (extremos de troços) são identificados por inteiros não necessariamente consecutivos.

Output

O comprimento da jaula que transportará o animal (expresso em decímetros) ou 0 se não for possível efectuar o transporte.

Exemplo

Input

20 30 25 40 15

4 3

1 6 25 30 50

4 6 30 27 20

6 3 15 35 25

50 7 29 20 35

1 50 30 25 20

3 7 23 25 15

4 50 22 30 15

1 3 20 30 23

7 4 30 40 16

-1

Output

27

Sem_titulo.jpg

Explicação do grafo:

Riscos vermelhos:esses caminhos não cabem nas medidas iniciais

Risco grosso:o unico caminho que dá

Outros riscos:não dão porque por exemplo o 40 do 4-7 não cabe no 25 do 7-3.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

import shlex

   def jaula():
   a=raw_input()
   definicoes=shlex.split(a)
   lmin=int(definicoes[0])
   lmax=int(definicoes[1])
   cmin=int(definicoes[2])
   cmax=int(definicoes[3])
   h=int(definicoes[4])
   b=raw_input()
   extremoscaminho=shlex.split(b)
   origem=int(extremoscaminho[0])
   chegada=int(extremoscaminho[1])
   dados={}
   caminho={}
   n=1
   while True:
       c=raw_input()
       if c!="-1":
           jaulas=shlex.split(c)
           origemtroco=int(jaulas[0])
           fimtroco=int(jaulas[1])
           largurajaula=int(jaulas[2])
           comprimentojaula=int(jaulas[3])
           alturajaula=int(jaulas[4])
           if largurajaula >= lmin and largurajaula <= lmax:
               if comprimentojaula >= cmin and comprimentojaula <= cmax:
                   if alturajaula >= h:
                       dados[n] = [origemtroco,fimtroco,comprimentojaula]       
           n=n+1
           if caminho.has_key(origemtroco)==False:
               caminho[origemtroco]=fimtroco
           else:
               if fimtroco not in [caminho[origemtroco]]:
                   print caminho
                   caminho[origemtroco].append(fimtroco)
           if caminho.has_key(fimtroco)==False:
               caminho[fimtroco]=origemtroco
           else:
               if origemtroco not in [caminho[fimtroco]]:
                   caminho[fimtroco].append(origemtroco)
       else:
           break
   print dados
   print caminho

A minha ideia era fazer um dicionario com os caminhos possiveis (ja estao eliminados aqueles que não cabem nas medidas iniciais) e depois de substitui-los pelos valores dos comprimentos (para isso é criei o dicionario com os extremos dos troços e os comprimentos) e ver novamente quais são os possíveis (quando a 1ª medida da chave fosse a mais pequena) e no fim ver qual era a maior delas. :P Mas acho que comecei a confundir as coisas aqui ao fim... O erro que me está a dar neste momento é que o dicionario dos caminhos so apresenta o ultimo valor. Exemplo:

1 4

1 7

{1:4,4:1,7:1}

Uma pergunta:Como é que se adiciona mais que um elemento a uma chave de um dicionário? (É que sempre que adiciono um elemento o último "passa por cima" do anterior. :( )

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O shlex.split(a) é o mesmo que fazer a.split() só que este computador é manhoso e tive que o pôr assim... -_-'

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em relaçao à tua pergunta do dicionario, tens que criar uma lista de elementos em vez de um só :D

dict[chave] = [elemento1, elemento2, ... ]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim mas eu quero inserir os elementos um a um porque cada input vai ter um valor para adicionar ao dicionário e não posso tratá-los todos ao mesmo tempo.  :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois mas eu já tentei e dá erro.  :P

E quanto ao meu programa? Alguem me da conselhos para o resolver?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É um problema de grafos, não te posso mesmo ajudar :P Mas quanto ao dicionário, qual é o erro que te dá?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens a certeza quanto a essa explicação do output? (Foste tu que a acrescentaste ou já estava no enunciado?)

Segundo a minha interpretação do problema (aquela que me parece fazer mais sentido), o 4 - 7 é um percurso que ele poderia fazer, só não o faz por não pertencer à solução óptima. (teríamos comprimento de 25 no final, em vez de 27, porque ele teria que passar no 3-7)

Ou seja, aquele 40 do comprimento do 4-7 não é um mínimo, mas sim um máximo. Uma jaula de comprimento 25 poderia passar ali.

Começas por eliminar todos os caminhos que não respeitem as condições inicias da caixa (ou seja, que tamanho o um comprimento ou largura que não pertencem aos intervalos dados, ou uma altura menor do que a exigida) - basicamente são os caminhos a vermelho.

A partir daí, podes ignorar a altura e a largura, e ficas simplesmente com um grafo pesado em que o peso de cada aresta é o comprimento possível da caixa naquela aresta. O que tu queres achar é: qual o caminho entre a origem e a chegada que me maximiza o arco menor.

Isto pode ser feito de várias maneiras, posso-te explicar uma solução possível:

1º passo: achas um caminho qualquer entre a origem e a chegada, e vês qual é o seu valor mínimo para o comprimento.

2º passo: removes todos os arcos cujo peso seja menor ou igual a esse valor minimo.

3º passo: repetes o passo 1. Quando deixar de existir um caminho entre a chegada e a origem (ou seja, ficar um grafo disconexo), terminas, e sabes que o peso do arco menor do caminho entre a chegada e a origem é aquele que removeste em último lugar.

Demonstrar que isto funciona também é simples: começas por encontrar um caminho qualquer, e agora vais sempre melhora-lo. Para melhorar um caminho, basta garantir que não percorres arcos de comprimento menor, logo remove-los é a solução mais prática. Outra hipótese seria guardar o melhor valor até agora, e em vez de remover os arcos não deixar o programa os percorrer na fase de procurar o caminho -> era só acrescentar um if para verificar o comprimento do arco.

Já agora, tenho quase a certeza que existe uma solução qualquer standard, mas assim de repente esta foi a primeira que me lembrei e funciona na pior das hipóteses em O(m* n) sendo m o número de arestas e n o número de vértices. Mas isto é um caso raro em que irias remover um arco de cada vez, muito pouco provável.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Engraçado, hoje de manhã um amigo meu colocou-me o mesmo problema, também és da FCUP ? Podias postar o outro problema na secção dos desafios, gostei bastante :D Já o resolveste?

Acho que esta dúvida se insere mais na Algoritmia e Lógica.

Isto pode ser feito de várias maneiras, posso-te explicar uma solução possível:

1º passo: achas um caminho qualquer entre a origem e a chegada, e vês qual é o seu valor mínimo para o comprimento.

2º passo: removes todos os arcos cujo peso seja menor ou igual a esse valor minimo.

3º passo: repetes o passo 1. Quando deixar de existir um caminho entre a chegada e a origem (ou seja, ficar um grafo disconexo), terminas, e sabes que o peso do arco menor do caminho entre a chegada e a origem é aquele que removeste em último lugar.

Demonstrar que isto funciona também é simples: começas por encontrar um caminho qualquer, e agora vais sempre melhora-lo. Para melhorar um caminho, basta garantir que não percorres arcos de comprimento menor, logo remove-los é a solução mais prática. Outra hipótese seria guardar o melhor valor até agora, e em vez de remover os arcos não deixar o programa os percorrer na fase de procurar o caminho -> era só acrescentar um if para verificar o comprimento do arco.

Já agora, tenho quase a certeza que existe uma solução qualquer standard, mas assim de repente esta foi a primeira que me lembrei e funciona na pior das hipóteses em O(m* n) sendo m o número de arestas e n o número de vértices. Mas isto é um caso raro em que irias remover um arco de cada vez, muito pouco provável.

Não pensei assim, mas acho que funciona. Por outro lado, se for implementado como sugeriste, acho que o worst case é O( m * (n+m) ) porque se removeres uma aresta de cada vez, no 2º passo precisas de O(n+m) para percorrer os edges todos. Mas também, não é grande diferença e o meu amigo disse-me que os testes não eram muito puxados. Mas de qualquer forma, a prof devia por os limites no enunciado.

O que eu pensei foi fazer uma pesquisa em largura com estado (vértice, comprimento máximo possivel neste caminho)  parecido ao problema B da MIUP 2008.

Ou talvez ainda melhor, um dijkstra com o mesmo estado.

Podes ver explicações disto nas revistas Programar ou em http://www.portugal-a-programar.pt/index.php?showtopic=16357

edit: no que sugeri é como o Warrior disse, antes remove-se os edges que assinalaste a vermelho e considera-se só os comprimentos nas ligações.

PS: Pessoal que vai concorrer às ONI, era bom vocês também resolverem isto :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens a certeza quanto a essa explicação do output? (Foste tu que a acrescentaste ou já estava no enunciado?)

Segundo a minha interpretação do problema (aquela que me parece fazer mais sentido), o 4 - 7 é um percurso que ele poderia fazer, só não o faz por não pertencer à solução óptima. (teríamos comprimento de 25 no final, em vez de 27, porque ele teria que passar no 3-7)

Ou seja, aquele 40 do comprimento do 4-7 não é um mínimo, mas sim um máximo. Uma jaula de comprimento 25 poderia passar ali.

Fui eu que acrescentei a explicação mas foi o que a professora me disse... Quanto ao máximo seria 25 porque 25 podia passar num caminho de 40 mas não podia passar nesse mesmo caminho de 25, percebeste? :P

Engraçado, hoje de manhã um amigo meu colocou-me o mesmo problema, também és da FCUP ? Podias postar o outro problema na secção dos desafios, gostei bastante :D Já o resolveste?

Acho que esta dúvida se insere mais na Algoritmia e Lógica.

Sim, sou da FCUP. *.* Não, não resolvi. Estou a tentar o outro mas como não encontro algoritmos de Tarjan bons ando com alguns probelmas mas quanto a este também já pensei em usar a pesquisa em largura, só não sei é se vai ter pequenos problemas... Pronto, vou tentar postar o outro e fazer o mesmo que fiz a este.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mas quanto a este também já pensei em usar a pesquisa em largura, só não sei é se vai ter pequenos problemas... Pronto, vou tentar postar o outro e fazer o mesmo que fiz a este.

Tens de guardar para cada nó o comprimento máximo possivel com que já o visitaste - considera isto comp[ v ]. Assim, só voltas a visitar um vértice na pesquisa em largura se o comprimento máximo actual, comp[ v_actual ] é maior do que comp[ v_adjacente ]. Não é uma bfs normal, mas este tipo de uso, é útil.

Ou seja, comp[ start = 4 ] = Infinito. No fim, comp[3] vai ser igual a 27.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fui eu que acrescentei a explicação mas foi o que a professora me disse... Quanto ao máximo seria 25 porque 25 podia passar num caminho de 40 mas não podia passar nesse mesmo caminho de 25, percebeste? :cheesygrin:

O enunciado discorda.. Não há qualquer problema em passar 25 num caminho 25, não excedeu o máximo.

Se isso fosse verdade, não podia passar 27 no caminho 4-6

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim mas 27 é maior que 25... xD Expliquei-me mal desculpa. :vergonha:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pessoal, agradecia que aqui discutissem apenas a parte da implementação do algoritmo em Python :D Para a discussão "algorítmica" em si, têm (acho eu) já uma thread no quadro "Algoritmia".

Se preferirem, eu movo para lá o que está aqui de discussão :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Continuando em algoritmia (mas não mudes porque posso vir a ter outro tipo de dúvidas...), alguém sabe de algum algoritmo que dado o início e o fim de um grafo (e o respectivo grafo) me dê todos os caminhos possíveis? Eu estava a pensar no Dijkstra mas não encontro nenhum Dijkstra na Internet minimamente bom (pequeno  :(-ou sem ser em pseudo código (e digamos que eu sou péssima a usar o pseudo código)).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

BlodyGrl, este quadro é de Python, não é de algoritmia. Para alguma coisa existe o outro quadro. Se vais insistir em usar este tópico para discutir algoritmia, ele vai mudar de sítio :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Continuando em algoritmia (mas não mudes porque posso vir a ter outro tipo de dúvidas...), alguém sabe de algum algoritmo que dado o início e o fim de um grafo (e o respectivo grafo) me dê todos os caminhos possíveis?

Parece-me que queres um A*. http://en.wikipedia.org/wiki/A_star
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O A* é um dijkstra mas usando uma função heuristica para melhorar a performance, neste caso não é necessário.

Para gerar todos os caminhos pode usar uma pesquisa em largura ou em profundidade, mas como disse, não é boa ideia porque é um número gigantesco de caminhos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A minha ideia não era a mais eficiente, mas era simples de implementar e chegava para passar nos testes. Acredito que a prof quisesse com dijkstra.

def readint(): return int(raw_input())
def readarray(type): return map(type, raw_input().split())

def addEdge( grafo , src , dst , comp ):
    if grafo.has_key(src) :     grafo[src].append( [dst,comp] )
    else :                      grafo[src] = [ [dst,comp] ]
        
def b():
    (lmin,lmax,cmin,cmax,amin) = readarray(int)
    (origem,destino) = readarray(int)
    
    grafo = {}
    ok = True
    while ok :
        v = readarray(int)
        if (v[0] == -1 ):
            ok = False
        else:
            [ src , dst , larg , comp , alt ] = v
            if larg >= lmin and comp >= cmin and alt >= amin :
                addEdge( grafo , src , dst , comp )
                addEdge( grafo , dst , src , comp )
    visited = {}
    visited[destino] = 0
    for key in grafo.keys():
        visited[key] = 0

    q = [ [origem,cmax] ]   # pesquisa em largura
    visited[origem] = cmax
    for [v,c] in q :
        if visited[v] == c and grafo.has_key(v) :
            for [next,comp] in grafo[v] :
                comp = min( c , comp )
                if ( comp > visited[next] ):
                    visited[next] = comp
                    q.append( [next,comp] )
    print visited[destino]
b()

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ela não quer com ou sem Dijktra desde que o problema estivesse feito. E nós fizemos...  :) Meia hora depois do tempo acabar.  :-[

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