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 > > 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 � <[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]> >========================================================================= ========================================================================= 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]> =========================================================================
