Jump to content
Sign in to follow this  
cryteck

Grafos com vários pesos

Recommended Posts

cryteck

Boas.

Estou a desenvolver programa que tem como objectivo dar o caminho mínimo mas com critérios mistos.

Eu até agora tenho a dar o caminho mínimo mas só com um peso, ou seja calcula o caminho mínimo mas só com um peso em cada aresta.

O meu problema é que temos vários pesos, ou seja temos varias variáveis que são o comprimento, horas (horas de ponta, horas normais), tipo pavimento e podemos ter critérios mistos no calculo do trajeto.

Será que me podiam dar uma ajuda de como pensar como implementar o peso, pois temos vários pesos neste caso.

Cumps,

Luís Sousa

Share this post


Link to post
Share on other sites
HappyHippyHippo

com uma função que pega em todos esses parâmetros e converte num único valor a ser considerado como "peso" da ligação


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

Share this post


Link to post
Share on other sites
cryteck

Obrigado desde já pela tua resposta.

Mas não podemos tipo ter vários pesos?

O peso ser um objeto que contém aquelas variáveis todas?

Cumps,

Luís Sousa

Share this post


Link to post
Share on other sites
HappyHippyHippo

poder ter milhentos pesos, mas só consegues avaliar uma aresta em relação a outra se tiveres uma medida, e essa medida tem de ser uma ponderação de todos os parâmetros da aresta.


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

Share this post


Link to post
Share on other sites
HappyHippyHippo

com uma função que pega em todos esses parâmetros e converte num único valor a ser considerado como "peso" da ligação


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

Share this post


Link to post
Share on other sites
cryteck

Sim já percebi.

Mas por exemplo o peso de uma aresta entre dois vértices é definido logo ao inicio ao fazermos addEdge("N1","N2",1500);

Depois como alteramos o peso a meio do programa conforme o nosso critério?

O professor só quer um grafo e se alterarmos o peso a meio tamos a criar um novo grafo com pesos diferentes...

Edited by cryteck

Share this post


Link to post
Share on other sites
HappyHippyHippo

tu não alteras pesos !!!! calculas uma medida mediante os parâmetros da aresta !!

vou alterar o meu post inicial para ver se percebes melhor :

com uma função que pega em todos esses parâmetros e converte num único valor calcula uma medida a ser considerado como "peso" da ligação

Edited by HappyHippyHippo

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

Share this post


Link to post
Share on other sites
cryteck

Eu tou a perceber o que tu estás a dizer mas não tou a ver como fazer , tenho de alterar o peso conforme o critério de pesquisa.

Será que podias por alguns trachos de código ?

Será que tenho de ter várias matrizes de adjacências e vários iteradores cada um de acordo com o tipo de pesquisa do caminho?

Cumps

Edited by cryteck

Share this post


Link to post
Share on other sites
HappyHippyHippo
class Aresta
{
 protected dist;
 protected tempo;

 public int peso_criterio_1()
 {
   return dist * tempo;
 }

 public int peso_criterio_2()
 {
   return (dist * 7 + tempo * 3) / 10;
 }
}


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

Share this post


Link to post
Share on other sites
Warrior

Essa é a pior maneira de implementar.

Para este tipo de situações há tipicamente dois padrões de desenho aconselhados:

Strategy pattern: http://en.wikipedia.org/wiki/Strategy_pattern

Template method: http://en.wikipedia.org/wiki/Template_method_pattern

Há mais uma ou outra possibilidade, mas eu neste caso em particular eu escolhia um strategy: crias uma class abstracta "Pesos" e crias várias subclasses, uma para cada método de cálculo do peso.

Ou a class que tem o algoritmo (e.g. Dijkstra) ou a classe aresta possui depois um objecto do tipo Pesos que é inicializado com a subclasse apropriada. Desta forma é simples mudar o método de cálculo durante a execução, simplesmente substitui-se o objecto na variável.

Edited by Warrior

Share this post


Link to post
Share on other sites
HappyHippyHippo

o uso de um pattern é bom, mas é para quem já se encontra com traquejo na linguagem

em alguns casos ainda vai confundir mais a pessoa que se encontra a aprender uma matéria/problema/solução para interiorizar um novo conceito.

é claro que um strategy pattern seria melhor, mas a afirmação a ser feita deveria ser :

- @cryteck, se leste o artigo da wikipédia sobre Strategy pattern e percebeste, então faz isso porque facilita muito. se não percebeste, faz a martelada que o @happyhippyhippo apresentou


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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.