fearz7 Posted February 7, 2013 at 02:26 PM Report #494470 Posted February 7, 2013 at 02:26 PM 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 Posted February 7, 2013 at 02:27 PM Report #494471 Posted February 7, 2013 at 02:27 PM usa um BFS onde o elemento avaliado é o valor de qualidade IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
fearz7 Posted February 7, 2013 at 03:24 PM Author Report #494480 Posted February 7, 2013 at 03:24 PM Podes ser mais especifico por favor?
HappyHippyHippo Posted February 7, 2013 at 03:34 PM Report #494481 Posted February 7, 2013 at 03:34 PM bfs : http://en.wikipedia.org/wiki/Breadth-first_search IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
fearz7 Posted February 7, 2013 at 03:48 PM Author Report #494485 Posted February 7, 2013 at 03:48 PM (edited) 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 Posted February 7, 2013 at 03:58 PM Report #494486 Posted February 7, 2013 at 03:58 PM 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 Portugol Plus
Rui Carlos Posted February 8, 2013 at 02:04 PM Report #494610 Posted February 8, 2013 at 02:04 PM 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. Rui Carlos Gonçalves
Warrior Posted February 8, 2013 at 03:34 PM Report #494619 Posted February 8, 2013 at 03:34 PM 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? 1 Report
Rui Carlos Posted February 8, 2013 at 04:51 PM Report #494625 Posted February 8, 2013 at 04:51 PM 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. Rui Carlos Gonçalves
fearz7 Posted February 9, 2013 at 01:52 PM Author Report #494679 Posted February 9, 2013 at 01:52 PM 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 Posted February 9, 2013 at 02:53 PM Report #494685 Posted February 9, 2013 at 02:53 PM 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. Rui Carlos Gonçalves
HappyHippyHippo Posted February 9, 2013 at 07:15 PM Report #494709 Posted February 9, 2013 at 07:15 PM (edited) 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 IRC : sim, é algo que ainda existe >> #p@p Portugol Plus
Warrior Posted February 9, 2013 at 07:24 PM Report #494710 Posted February 9, 2013 at 07:24 PM (edited) 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
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now