Ola Duda,
Tudo Legal ?
A sua solucao e um otimo PRANAYAMA. Todavia, antes do otimo PRANAYAMA e
necessario que se faca corretamente o ASANA ...
Quero dizer que quanto voce diz :
Construa uma outra matriz X NxP com um 1 na mesma posição onde a minhoca
está e 0 em todas as outras posições, e uma matriz Y NxP toda zerada.
Voce esta implicitamente pressupondo que a posicao da minhoca e um dos dados
de entrada, o que nao esta correto. Em verdade, na lista italiana onde o
problema foi originalmente proposto, o enfoque era justamente descobrir uma
forma diferente e inteligente de encontrar a minhoca, pois partindo-se da
posicao dela ha algoritmos inteligentes e otimos de se encontrar o menor
caminho de saida.
Assim, a parte de maior interesse e justamente o que voce nao fez : Encontre
uma forma inteligente - tao rapida quanto possivel - de encontrar a posicao
inicial da minhoca.
A imensa maioria das solucoes usavam grafos e pesquisa em largura, dando
pouca atencao ao problema de se encontrar a posicao da minhoca. Era
previsivel. Todavia, o autor do problema escreve claramente : O algoritmo e
de IA.
Pelo pouco que conheco de IA, nao ha uma unica padronizacao nesta area ...
vigoram aqui a criatividade e a imaginacao. Essa area e a Teoria da
Computacao sao realmente bonitas e acredito que devem despertar o interesse
de qualquer Matematico.
Um abraco
Paulo Santa Rita
6,1239,050702
From: Eduardo Casagrande Stabel [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Um Algoritmo Legal
Date: Thu, 4 Jul 2002 19:57:14 -0300
Oi Paulo,
talvez não seja o melhor algoritmo, mas uma idéia simples é a seguinte:
*
Construa uma outra matriz X NxP com um 1 na mesma posição onde a minhoca
está e 0 em todas as outras posições, e uma matriz Y NxP toda zerada.
INICIO
Para cada 1 presente na matriz X verifique na vizinhança dos elementos de
LAB onde existe 1 e marque esses elementos na matriz Y (NxP).
(A matriz Y marca todos os movimentos possíveis, sem morte, da minhoca
nesta
rodada)
Acrescente à X os elementos de Y que são 1 e que em X eram 0.
Se as matrizes X e Y forem iguais o programa terminha e devolve 0.
Se a matriz X tiver algum elemento em sua borda igual a 1 então o programa
termina e devolve o número de vezes que executou INICIO.
Zere a matriz Y e repita o procedimento desde INICIO.
*
Por que o programa funciona? No caso de Y e X serem iguais, é claro que
todo
movimento a partir das casas com 1 em X só levam a casas que já eram 1 em
X,
portanto não se pode fugir das casas de X, e portanto se está preso no
labirinto.
No caso de haver uma saída do labirinto, na vez K que passamos em INICIO Y
mostra todas as possibilidades de a minhoca estar após o K movimentos,
TODAS
as possibilidades, inclusive os K primeiros movimentos do caminho ideal
(que
faz sair do labirinto na quantidade mínima de movimentos). Segue que se for
possível sair do labirinto em K movimentos, na K-ésima vez que passamos por
INICIO a matriz vai incluir um 1 na borda.
Está bom?
Eduardo Casagrande Stabel.
Porto Alegre, RS.
From: Paulo Santa Rita [EMAIL PROTECTED]
Ola Pessoal,
Segue abaixo a traducao de um problema de computacao que recebi de outra
lista e que achei interessante e digno de figurar nesta nostra lista
OBM-L.
O Algoritmo e de IA.
Uma minhoca esta em uma celula de um labirinto quadriculado NxP ( N
linhas,
P colunas ). Ela almeja sair do labirinto. Todavia, sabe-se que nalgumas
celulas ha brasa, noutras, terra. A minhoca se movimenta como o rei em
um
tabuleiro de xadrex.
Os dados de entrada sao : N ,P e LAB(N,P).
LAB(N,P) uma matriz da forma :
0 (zero) - casa com brasa
1 (um) - casa com terra
2 (dois) - a minhoca
Exemplo :
101010101010
001100110001
21011011
10011101
1000
O programa ( function ) deve devolver :
1) 0 ( zero ) se nao houver um caminho de saida
2) N ( numero inteiro positivo ) se houver. Neste caso N e o menor
numero
de
passos que a minhoca deve dar para sair do labirinto sem se queimar.
O programa pode estar em qualquer linguagem padrao ou em pseudo-codigo.
OBS : O tempo de resposta ( inteligencia do algoritmo ) sera o principal
fator na classifucacao final dos algoritmos.
Um Abraco a Todos
Paulo Santa Rita
5,1709,040702
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED]
=
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é [EMAIL PROTECTED
