Caminho aleatório sem repetição

Origem: Wikipédia, a enciclopédia livre.

O caminho aleatório sem repetição é um tipo de permutação no campo da análise combinatória. Embora o seu conceito já tenha sido estudado pelo menos desde 1150 por Baskara II,[1] só na década de 1990 começou a ser utilizado recorrentemente no campo da geoestatística com o aumento da capacidade de processamento dos computadores e implementação em métodos de simulação sequencial, como é o caso da simulação sequencial gaussiana.[2] Um caminho aleatório sem repetição é feito a partir de um conjunto de localizações pré-determinadas mas randomizando o caminho feito sobre elas garantindo que nunca voltará ao mesmo local. Isto implica que o único processo aleatório deste procedimento é o do instante em que se irá percorrer uma dada localização e não o da própria localização.


Definição[editar | editar código-fonte]

Assumindo que temos uma malha com nove localizações possíveis (nós) e tencionamos percorrer todas a cada momento que passa sendo os momentos [1,2,3,4,5,6,7,8,9] então quatro possíveis caminhos aleatórios são:

Malha com 9 locais
***
***
***
1º Caminho aleatório
821
965
437
2º Caminho aleatório
379
156
824
3º Caminho aleatório
597
612
384
4º Caminho aleatório
453
927
186

Embora seja um método tipicamente utilizado em ciências de modelação o conceito de permutação (de análise combinatória) está na sua génese dado que representa a possibilidade de objectos (neste caso uma lista de localizações) ter vários arranjos diferentes. Importa, no entanto, frisar que se tratam de arranjos em que cada um dos elementos é único e que o processo de arranjo provém de um procedimento baseado em números aleatórios (ou pseudo-aleatórios). Assim, pegando num exemplo semelhante ao anterior, se tivermos uma lista de 9 localizações [1,2,3,4,5,6,7,8,9] cada arranjo dos elementos desta lista seria um caminho aleatório sem repetição num total de:


Algoritmo do caminho aleatório sem repetição (Python)[editar | editar código-fonte]

A implementação bidimensional que se segue é feita na linguagem Python (versão 2.7.2) com recurso à biblioteca NumPy tendo por esse motivo o seguinte cabeçalho de importações:

import numpy as np

Em recurso à função shuffle do módulo numpy é possível criar facilmente uma função cujos argumentos são tamanho e semente e resultado um vector com um caminho aleatório:

def caminho_aleatorio(tamanho,semente):
    np.random.seed(semente)
    resultado = np.arange(tamanho)
    np.random.shuffle(resultado)
    return resultado

Dado que o caminho é gerado aleatóriamente é necessário a existência de uma semente que faça com o utilizador possa repetir o mesmo resultado desde que utilizando o mesmo número de semente. Veja-se a experiências seguinte onde foi lançada a função quatro vezes duas das quais (primeira e última) com a mesma semente:

print caminho_aleatorio(10,123)
print caminho_aleatorio(10,124)
print caminho_aleatorio(10,125)
print caminho_aleatorio(10,123)

O resultado é este:

[4 0 7 5 8 3 1 6 9 2]
[6 8 3 5 4 0 9 2 7 1]
[9 1 0 6 4 5 3 8 7 2]
[4 0 7 5 8 3 1 6 9 2]

De notar que foram gerados quatro vectores nos quais as posições indicam diferentes localizações dadas pelos valores que se encontram em cada vector. As funções utilizadas para conseguir este efeito são:

  • np.random.seed() - Força a semente dos processos aleatórios que se seguem a serem a de input, implicando um controlo sobre a geração pseudo-aleatório.
  • np.arange() - Cria um vector crescente de valores igualmente espaçados. Por defeito inteiros com espaçamento de 1 a começar em zero e terminando no argumento inserido.
  • np.shuffle() - Troca, por meio de processos aleatórios, a posição dos elementos de um vector.


Discussão[editar | editar código-fonte]

Este tipo de caminho aleatório é muito utilizado em geoestátistica nos algoritmos de simulação sequencial muito embora por vezes haja aplicações no qual ele não é totalmente aleatório[3] dando prioridade a certas localizações.

Ver também[editar | editar código-fonte]

Referências

  1. N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136
  2. Deustch, C.V. and A.G. Journel, 1992. "GSLIB, Geostastical Software Library and user's guide." Oxford Univ. Press, New York, pp. 340
  3. Yin Yanshu,Ding Hui,Shi Shuyuan, 2011, "A new study on the integrating of random walk process and multiple point geostatistics to model the fluvial reservoir", Computer Science & Education (ICCSE), 2011 6th International Conference