Caminho aleatório sem repetição

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, 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. 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 * * * * * * * * *	$\rightarrow$	1º Caminho aleatório 8 2 1 9 6 5 4 3 7	2º Caminho aleatório 3 7 9 1 5 6 8 2 4	3º Caminho aleatório 5 9 7 6 1 2 3 8 4	4º Caminho aleatório 4 5 3 9 2 7 1 8 6

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:

$P_{n}=n!\rightarrow P_{9}=9!=362880$

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ório dando prioridade a certas localizações.

Ver também

• Simulação sequencial
• Simulação sequencial gaussiana
• Simulação sequencial directa