Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
gadelhas

Duvida na construção de algoritmo

Recommended Posts

gadelhas

Viva;

Necessito de fazer um programa em java que consiste no seguinte;

O mesmo está ligado a uma base de dados, em que a mesma possui apenas dois campos, "X" e "Y", depois a primeira linha são as cordenadas do ponto de saída, a segunda linha as do ponto de destino, e as restantes linhas as coordenadas dos obstáculos.

O algoritmo deverá ir da origem ao destino, pelo caminho mais curto, sem bater nos obstáculos.

A parte de acesso à base de dados e afins está feita, a minha dúvida prende-se mesmo em efectuar um algoritmo que me faça o descrito na frase acima.

Já tive a ver o vosso tópico de Grafos que se encontra aqui, contudo, como nunca dei grafos, não consigo perceber muito bem aquilo.

Alguém me dá uma ajuda como implemetar este algoritmo?

O meu obrigado desde já!


Abraço Gadelhas

Share this post


Link to post
Share on other sites
Cynary

Aconselho-te a pesquisar sobre o algoritmo de dijkstra, que é provavelmente o mais indicado.

Share this post


Link to post
Share on other sites
Warrior

Como os pesos são unitários também podes resolver o problema com uma pesquisa em largura.

O que me faz alguma confusão é a "base de dados", qual o seu objectivo ao certo? Deve-se tentar minimizar o número de registos consultados?

Share this post


Link to post
Share on other sites
gadelhas

Viva,

Obrigado pelas respostas ao Tópico.

Cynary:

Já consultei o algoritmo de dijkstra, mas com o mesmo só consigo obter o caminho mais curto, mas e se nesse caminho mais curto tiver um obstáculo?

Warrior:

A base de dados é onde estão as cordenadas com o ponto de origem, ponto de destino e obstaculos, em "x" e "y".

Explica-me se puderes isso da pesquisa em largura?


Abraço Gadelhas

Share this post


Link to post
Share on other sites
Cynary

Podes à mesma usar o algoritmo de dijkstra.

Tens apenas de arranjar alguma maneira de inserir caminhos diferentes, de forma a contornares os obstáculos. Podes fazer uma pré-computação, em que crias todos os caminhos possíveis, contornando os obstáculos, e depois com o algoritmo de dijkstra, descobre qual o caminho mais curto.

Share this post


Link to post
Share on other sites
Warrior

Podes à mesma usar o algoritmo de dijkstra.

Tens apenas de arranjar alguma maneira de inserir caminhos diferentes, de forma a contornares os obstáculos. Podes fazer uma pré-computação, em que crias todos os caminhos possíveis, contornando os obstáculos, e depois com o algoritmo de dijkstra, descobre qual o caminho mais curto.

Alto, que asneira tão grande! Gerar todos os caminhos faz com que a tua solução não seja polinomial!

Podes usar o algoritmo de dijkstra se não considerares os nós onde estão os obstáculos, simplesmente ignoras esses.

Proponho que leias este tópico que criei há uns tempos:

http://www.portugal-a-programar.pt/index.php?showtopic=16357

Share this post


Link to post
Share on other sites
mjamado

Alto, que asneira tão grande! Gerar todos os caminhos faz com que a tua solução não seja polinomial!

Ia dizer o mesmo, mas com uma fundamentação diferente...  :cheesygrin:

Podes fazer uma pré-computação, em que crias todos os caminhos possíveis, contornando os obstáculos, e depois com o algoritmo de dijkstra, descobre qual o caminho mais curto.

Se fosse mesmo preciso gerar todos os caminhos possíveis - que não é - era só ir verificando e guardando qual o mais curto a cada momento; não era preciso mais nada...


"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Share this post


Link to post
Share on other sites
gadelhas

Viva;

Warrior:

Já li esse post, estou a começar a perceber mais ou menso grafos, mas como é obvio tou no inicio.

Parece-me que se fizer uma matriz, colocar no local dos obstaculos por exemplo o valor 1, e nos restantes locais o valor 0, poderei aplicar o algoritmo de dijkstra, ignorando os locais da matriz com os "1", certo? Ou tou a fazer confusão

Obrigado.


Abraço Gadelhas

Share this post


Link to post
Share on other sites

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 account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

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.