Caminho aleatório sem repetição - pt.LinkFang.org

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,[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.


Índice

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
***
***
***
\({\displaystyle \rightarrow }\)
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:

\({\displaystyle 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:


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[3] dando prioridade a certas localizações.

Ver também


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









Categorias: Geoestatística




Data da informação: 17.12.2020 03:21:35 CET

Fonte: Wikipedia (Autores [História])    Licença: CC-by-sa-3.0

Mudanças: Todas as imagens e a maioria dos elementos de design relacionados a essas foram removidos. Alguns ícones foram substituídos por FontAwesome-Icons. Alguns modelos foram removidos (como "o artigo precisa de expansão) ou atribuídos (como" notas de rodapé "). As classes CSS foram removidas ou harmonizadas.
Os links específicos da Wikipedia que não levam a um artigo ou categoria (como "Redlinks", "links para a página de edição", "links para portais") foram removidos. Todo link externo possui um FontAwesome-Icon adicional. Além de algumas pequenas mudanças de design, foram removidos os contêineres de mídia, mapas, caixas de navegação, versões faladas e microformatos geográficos.

Observe: Como o conteúdo fornecido é retirado automaticamente da Wikipedia no momento especificado, uma verificação manual foi e não é possível. Portanto, o LinkFang.org não garante a precisão e a atualidade do conteúdo adquirido. Se houver uma informação incorreta no momento ou com uma exibição imprecisa, sinta-se à vontade para Contate-Nos: email.
Veja também: Cunho & Política de Privacidade.