Vizinhança de von Neumann

Em autômatos celulares, a vizinhança de von Neumann consiste de quatro células ortogonais ao redor de uma célula central em uma grade bidimensional.[1] O nome dessa vizinhança vem de John von Neumann, que usou-a para definir o autômato de Vonn Neumann e o Construtor universal de Von Neumann.[2] Ela é uma das formas mais usadas para vizinhança de autômatos celulares bidimensionais, juntamente com a vizinhança de Moore, e tem uma noção similar a uma conexão de 4 pixels em computação gráfica.[3]

Distância de Manhattan r = 1
Distância de Manhattan r = 2

O conceito pode ser estendido para dimensões maiores como uma vizinhança de 6 células no formato de octaedro para um autômato celular cúbico em três dimensões, por exemplo.[4]

A vizinhança de Von Neumann de um ponto é o conjunto dos pontos que estão à uma distancia de 1, utilizando a métrica da distância de Manhattan.

Vizinhança de Von Neumann de raio r

editar

Uma extensão da vizinhança de Von Neumann descrita anteriormente pega um conjunto de pontos que estão à uma distancia r > 1 de acordo com a distância de Manhattan. Isso resulta em uma região em formato de losango. Estas são as vizinhanças de Von Neumann de raio ou extensão r. O número de células em uma vizinhança de Von Neumann de dimensão d de raio r é o número de Delannoy D(d,r).[4]

Veja também

editar

Referências

  1. Toffoli, Tommaso; Margolus, Norman (1987), Cellular Automata Machines: A New Environment for Modeling, MIT Press, p. 60 .
  2. Ben-Menahem, Ari (2009), Historical Encyclopedia of Natural and Mathematical Sciences, Volume 1, ISBN 9783540688310, Springer, p. 4632 .
  3. Wilson, Joseph N.; Ritter, Gerhard X. (2000), Handbook of Computer Vision Algorithms in Image Algebra, ISBN 9781420042382 2nd ed. , CRC Press, p. 177 .
  4. a b Breukelaar, R.; Bäck, Th. (2005), «Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior», Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), ISBN 1-59593-010-8, New York, NY, USA: ACM, pp. 107–114, doi:10.1145/1068009.1068024 .

Ligações externas

editar