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

cryteck

Grafos com vários pesos

Mensagens Recomendadas

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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Editado por cryteck

Partilhar esta mensagem


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

Editado por HappyHippyHippo

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

Partilhar esta mensagem


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

Editado por cryteck

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Editado por Warrior

Partilhar esta mensagem


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

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.