[Resolvido] Grafos - Caminho mais seguro

[fearz7]

Boa tarde,

Tenho um determinado grafo pesado direccionado, onde um dos seus pesos corresponde a um atributo qualidade(valor inteiro entre 1 - 5), 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?

Recorro a um algoritmo onde tenho que encontrar o caminho mais longo? Se sim, qual o algoritmo a seguir?

Obrigado desde já pela vossa atenção.

Melhores cumprimentos.

[HappyHippyHippo]

usa um BFS onde o elemento avaliado é o valor de qualidade

[fearz7]

Podes ser mais especifico por favor?

[HappyHippyHippo]

bfs : http://en.wikipedia.org/wiki/Breadth-first_search

[fearz7]

Isso eu sei, mas o que me estas a dizer e para escolher a aresta sempre com maior qualidade? Pois eu tenho um determinado vertice como destino.

Edited February 7, 2013 at 03:49 PM by fearz7

[HappyHippyHippo]

não estou a perceber a duvida ...

onde está o problema em implementar o BFS usando o parâmetro de qualidade ?

[Rui Carlos]

Queres o caminho mais seguro entre dois pontos dados?

Se for isso, eu começava para converter os pesos para uma escala em que menor significasse mais seguro (e.g., fazendo novo_peso = 5 - antigo_peso). E depois era só usar o habitual algoritmo para encontrar o caminho mais curto.

[Warrior]

Dados 2 caminhos, como é que defines qual é o mais seguro?

Imagina o seguinte exemplo de caminhos entre dois pontos:

5 - 3

4 - 4 - 4

Qual deles é mais seguro?

[Rui Carlos]

Dados 2 caminhos, como é que defines qual é o mais seguro?

Imagina o seguinte exemplo de caminhos entre dois pontos:

5 - 3

4 - 4 - 4

Qual deles é mais seguro?

É uma boa pergunta.

Aliás, nem me tinha apercebido que na sugestão que eu dei (novo_peso = 5 - antigo_peso), mudando o 5 por outro valor (à partida, mais elevado), podia levar a resultados diferentes.

E se calhar até faz mais sentido considerar a segurança de um caminho igual ao peso do arco com menor peso do caminho.

[fearz7]

E se calhar até faz mais sentido considerar a segurança de um caminho igual ao peso do arco com menor peso do caminho.

Desta mesma forma, e se ambos os caminhos tiverem o peso do menor arco igual? O que considero como o caminho mais seguro?

[Rui Carlos]

Desta mesma forma, e se ambos os caminhos tiverem o peso do menor arco igual? O que considero como o caminho mais seguro?

Regra geral, há sempre a possibilidade de num grafo específico todos os caminhos terem o mesmo "peso". Aquilo que normalmente se faz nesse caso, é escolher um caminho qualquer.

[HappyHippyHippo]

Desta mesma forma, e se ambos os caminhos tiverem o peso do menor arco igual? O que considero como o caminho mais seguro?

qual é o mais seguro ?

4-1-4-5

1-4-1-5

eu considero que seria aquele que na, sua totalidade, envolve menos problemas. logo terás sempre de contabilizar todos os arcos.

Edited February 9, 2013 at 07:17 PM by HappyHippyHippo

[Warrior]

Tens 3 critérios, tens que os ordenar pela ordem que preferes; isto não é algo que alguém possa decidir por ti/pelo enunciado.

a) maximizar a aresta mais pequena

b) minimizar o número de arestas

c) maximizar o peso das arestas

Tenta ordenar estes caminhos todos para perceberes o que de facto queres:

4-5-1-4

1-5-1

2-5-5-5-5-5-5-5-5

2-3-3-3-3

Edited February 9, 2013 at 07:25 PM by Warrior