1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Grafos - Caminho mais seguro

Discussão em 'Programação' iniciada por No Fear, 9 de Fevereiro de 2013. (Respostas: 8; Visualizações: 785)

  1. No Fear

    No Fear Power Member

    Boa tarde,

    Tenho um determinado grafo pesado direccionado, onde um dos seus pesos corresponde a um atributo qualidade(valor inteiro entre 1 - 5, representando mau e muito bom respectivamento), visto isto, e tendo em conta que quanto mais próximo de 5 estiver maior será a sua qualidade(mais seguro), como é que determino o caminho mais seguro?

    O problema esta em perceber o que tenho que considerar como parâmetro de qualidade...


    Obrigado desde já pela vossa atenção.

    Melhores cumprimentos.
     
  2. manelis

    manelis Power Member

    Provavelmente o caminho que tiver o valor minimo mais baixo, ou a média ou algo do género, isso é uma questão de enunciado...
     
  3. Nemesis37

    Nemesis37 Power Member

    Acho que uma boa maneira, e mais simples, era depois de determinados os caminhos possíveis o melhor caminho era aquele que tivesse a soma dos pesos mais alta.
    Algo mais complicado de implementar era usares o algoritmo de djikstra modificado de acordo como teu problema.
     
  4. mauro1855

    mauro1855 I'm cool cuz I Fold

    Estudei 3 algoritmos de implementação simples para o teu problema.
    Dijkstra, Bellman-Ford e Floyd-Warshall.

    São todos algoritmos de descoberta de caminhos mais curtos em grafos, mas como no teu problema os caminhos com maior peso são os melhores (mais seguros), suponho que bastaria alterar as condições dos algoritmos para procurarem não os caminhos mais curtos mas os caminhos mais longos (ou seja, o caminho que por definição seria o mais seguro).

    Dos que disse, o algoritmo que termina mais rapidamente é o Dijkstra. Talvez queiras começar por aí.
    Consulta este pdf: https://dl.dropbox.com/u/2431102/ShortestPaths.pdf (aí tens os 3 algoritmos que falei, incluindo pseudo-código e considerações teóricas que podes ignorar)

    Cumps
     
    Última edição: 9 de Fevereiro de 2013
  5. No Fear

    No Fear Power Member

    Desde ja obrigado pelas vossas respostas, contudo sou obrigado a discordar de algumas sugestoes, pois o caminho mais longo nao e sinal de qualidade... Serviria para encontrar um caminho mais comprido sem duvida agora mais seguro penso que nao seja por aí, penso que terei que encontrar todos os caminhos possíveis e posteriormente aplicar um parâmetro de qualidade seja esse a média ou outro parâmetro qq, whatever, para isso será o BFS uma boa solução?
     
  6. Darien

    Darien Power Member

    Aquilo são algoritmos para procurar o caminho mais curto. Mas fora isso, as ideias parecem-me bem. Já começaste a tentar implementar? Estás a ter algum problema?
     
  7. Sl0w

    Sl0w Power Member

    Se só queres o caminho mais longo de um nó A a B, transforma o grafo G num grafo quase idêntico, onde o valor das arestas passam a ser 1 a dividir pelo valor original. Por exemplo, se A -> B tinha custo 4, passa a ter custo 1/4. Aplica o Dijkstra tens o problema resolvido de forma eficiente. A parte "complicada" fica ao teu encargo. Convém é que percebas porque razão dividimos 1 pelo valor original do caminho: Se X > Y então 1/X < 1/Y; com esta inversão a aplicação do Dijkstra é imediata. Não podias aplicar o Dijkstra diretamente porque este algoritmo apenas minimiza a soma da valoração de todas as arestas do caminho; mas através da nossa inversão, para minimizar esse valor, temos de passar pelos caminhos que maximizam o ranking de segurança.
     
  8. manelis

    manelis Power Member

    BFS é o caso mais lento possível. Se é por aí vai pelo http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search que também garante a optimalidade e é consideravelmente mais rápido.

    edit: o post em cima é melhor solução, mas o BFS nunca faz sentido.
     
    Última edição: 10 de Fevereiro de 2013
  9. No Fear

    No Fear Power Member

    Nao sei de onde saíste mas acabaste de me resolver o problema(e sim percebi a explicação), ja está implementado e funciona na perfeição. Contudo, deixo uma palavra de apreço aos restantes membros que contribuíram de alguma forma, muito obrigado pessoal. Abraço.
     

Partilhar esta Página