Re: [obm-l] Um Algoritmo Legal

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

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" <dudasta@terra.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: <obm-l@mat.puc-rio.br>
>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" <p_ssr@hotmail.com>
> > 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
> > 111121011011
> > 100111111101
> > 111110001111
> >
> > 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 é <nicolau@mat.puc-rio.br>
> > 
>=========================================================================
> >
> >
>
>=========================================================================
>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 é <nicolau@mat.puc-rio.br>
>=========================================================================





=========================================================================
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 é <nicolau@mat.puc-rio.br>
=========================================================================