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

gadelhas

Duvida na construção de algoritmo

Mensagens Recomendadas

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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

Partilhar esta mensagem


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

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.

Partilhar esta mensagem


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

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.