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,N. L. Biggs, The roots of combinatorics, Historia Math. 6 (1979) 109−136 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.Deustch, C.V. and A.G. Journel, 1992. "GSLIB, Geostastical Software Library and user's guide." Oxford Univ. Press, New York, pp. 340 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 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)
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 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órioYin 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 dando prioridade a certas localizações.
Ver também Simulação sequencial Simulação sequencial gaussiana Simulação sequencial directa
Categoria:Geoestatística