Olá. Sou um novato nestas andanças de programação. Ando a estudar algoritmos e foi-me colocado um problema sobre o qual terei de me debruçar nas próximas semanas. Trata-se de um labirinto de p.e. 10x10 onde se pode marcar o ponto I (início) e o ponto F (fim). Neste labirinto poderão também ser colocados obstáculos na tabela bidimensional. O algoritmo tem que achar o caminho correcto do ponto I ao ponto F. Será que me podem dar algumas luzes sobre como hei-de resolver este problema. Todas as dicas serão bem-vindas.

Boas programações

CNAD:x2:

Isso não tem muito que saber, penso que será algo do tipo:

Enquanto não chegares ao fim do labirinto:

Analizas todas as 7 posições à tua volta (não vale a pena analisares aquela de onde vens)

Se houver "saidas", escolhes uma e repetes o processo até chegares à posição fim

Se não houver "saidas" (com excepção daquela por onde vieste), voltas atrás até ao ponto onde tinhas pelo menos 2 saidas (mais uma vez, exceptuando a por onde vieste) e escolhes outra até esgotares as saidas todas nesse ponto, OU, chegares ao fim.

Espero ter ajudado qualquer coisita.:)

Edit: Uma coisa muito importante, se fores navegar pela tabela com um par de coordenadas (digamos x,y para linhas e colunas), não faz sentido teres indíces da matriz menores que 0 (ou o valor a que a linguagem que vais utilizar usa para o primeiro indíce), ou maiores que n (onde n é o número de linhas e colunas).

Se fores utilizar uma numeração sequencial, então não faz sentido indíces menores que 0 ou maiores que n*n-1 (a ultima posição). Porém, se este for o caso, então quando estás numa posição qualquer, para analisares as posições acima ou abaixo tens de subtrair ou adicionar n-1,n e n+1 para cada posição vizinha dessa célula. Confuso? :D

Boa tarde.

Desde já obrigado pela atenção. Tenho uma dúvida: No início, se se colocar o ponto I no meio da tabela terão de ser analisadas 8 posições. Como tal terei de começar o meu trabalho por aí, certo? E só depois então analisar as outras 7 posições seguintes como foi referido pelo Freelancer. Já agora o algoritmo a utilizar nestes casos é de algum tipo, i.e., há alguma referência para que eu possa pesquisar na net?

Todas as dicas são bem-vindas.

Boas programações

CNAD:x2:

Tenho o mesmo trabalho pa fazer...lol

Isso que procuras está directamente relacionado com Grafos.

Existem vários algoritmos para resolver o que pretendes.
A sua escolha terá que ser feita baseando-te nos seguintes factores: valorização do menor tempo de escolha do caminho ou preferência no caminho mais curto. Podem haver mais variações mas de momento não me recordo.

Tens aqui (http://w3.ualg.pt/~hshah/algoritmos/aula2bfs.html) um link que usei quando precisei de aprender isso e tem uma aplicação em para perceberes melhor.

Por exemplo, 2 algoritmos, são o BFS e o DFS. Mais n digo ;)