Fala galera eu to com um trabalho da universidade pra fazer de grafos e to querendo umas dicas de como
implementar um metodo que me recolva o seguinte problema conhecido como problema da distribuiçao de
passagens vai ai uma descriçao de como ele eh: Dados os bom resultados obtidos no final do ano passado, a empresa de turismo Vemque Talimpo resolveu distribuir um lote de passagens (presente das companhias aéreas) entre seus funcionários. Com as passagens destinam-se a lugares específicos, o diretor da empresa viu-se diante de um dilema, pois não gostaria de presentear um funcionário com uma passagem para um lugar que não fosse de seu agrado. Sendo assim, ele resolveu fazer uma consulta aos funcionários solicitando que eles indicassem locais de sua preferência, dentre aqueles para os quais havia passagens. Como ele poderia, agora, obter uma distribuição de passagens que agradasse a todos os funcionários?
Eu jah tenho implementada as classes que fazem o grafo da pra ver pelo exeplo que eo grafo eh bipartite com algumas restriçoes que jah foram implementadas sendo assim eu so queria uma luz de como implementar o metodo que realiza o quefoi descrito acima!!
Nao sei argentinaluiz nao conheço esse algoritmo vou procurar a respeito!
Abrigado!!
A
argentinaluiz
eu conheço um pouquinho de grafos e eu ACHO QUE PODE SER O ALGORITMO DE EULLER!
R
Rafael_Mathias
Pesquisei e o algoritmo proposto nao resolve o problema nao os grafos de Euler sao ditos grafos eulerianos tais grafos devem possuir um caminho euleriano ou seja passar por todas as arestas uma unica vez porem para que isso seja possivel os vertices do grafo devem ser de grau par o que ira restringir a minha aplicaçao pois eu posso muito bem ter um funcionario que tenha tres lugares que lhe agradem da mesma forma como eu posso ter um lugar que apenas 1 funcionario goste etc…!!
Mas valeu a tentativa!!
ABraço!!
A
argentinaluiz
e como será o desempate se dois funcionarios quiserem ir para o mesmo lugar?
R
rodrigo.bossini
Tá mal explicado o problema. Qual problema o método deve resolver afinal? O ponto de partida de todos os funcionários é o mesmo?Uma vez escolhido um destino, o método tem que escolher o menor caminho do ponto de partida até o destino? Ou o quê?
R
Rafael_Mathias
bom Respondendo primeiro argentinaluiz bom ha essa possibilidade tambem porem eu vou levar em consideraçao que sempre sera possivel distribuir as passagens
agora respondendo o rod.attack vc entendeu errado o problema o dono da empresa tem ums passagens disponiveis e quer das aos seus funcionarios porem ele quer que os funcionarios estejam em lugares que lhe agradem pra isso ele vai falar para os funcionarios escolherem um lugar que lhe agrada dessa forma o algoritmo deve distribuir as passagens entre os funcionarios de forma que agrade todos vo colocar um grafo aqui pra exemplificar
nesse grafo ai uma possivel soluçao seria
renato->natal
danilo->salvador
luiz->rio de janeiro
paulo->sao paulo
porem outras soluçoes sao possiveis como
renato->gramado
danilo->salvador
luiz->rio de janeiro
paulo->sao paulo
ou ate mesmo
renato->natal
danilo->sao paulo
luiz->rio de janeiro
paulo->salvador
entao o meu metodo deve me retornar os lugares pra onde os funcionarios irao de forma que todos sejam agradados
problemas como o que foi falado por argentinaluiz sao possiveis porem vamos levar em consideraçao que sempre sera possivel distribuir as passagens!!
Falowss!!
Abraçoss!!!
R
rodrigo.bossini
Bom, o problema consiste então em, uma vez que você tenha o par de vértices (funcionário,destino), criar uma aresta orientada de funcionário a destino. É isso?
E pelo que entendi cada funcionário pode escolher mais de um destino…
Sendo assim, você precisa ordenar os funcionários de forma que os que escolheram menos destinos sejam escolhidos primeiro.
Então, os critérios para criar as arestas seriam dois: o funcionário ter escolhido aquele destino; e aquele destino ainda não ter sido dado para outro funcionário.
A
argentinaluiz
acho que entao é o algoritmo da matriz de alcancibilidade!
