Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

fearz7

[Resolvido] Grafos - Caminho mais seguro

Mensagens Recomendadas

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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.

Editado por fearz7

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não estou a perceber a duvida ...

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


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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?

  • Voto 1

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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

Editado por Warrior

Partilhar esta mensagem


Ligação 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. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.