Grafos - Caminho mais seguro

[No Fear]

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.

 

[manelis]

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

 

[Nemesis37]

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.

 

[mauro1855]

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

 

[No Fear]

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?

 

[Darien]

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?

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?

 

[Sl0w]

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.

 

[manelis]

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?

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.

 

[No Fear]

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.

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.