Окрестность фон Неймана

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Соседство фон Неймана»)
Перейти к: навигация, поиск
(Двумерная) окрестность фон Неймана порядка 1.
(Двумерная) окрестность фон Неймана порядка 2.

Окре́стность фон Не́ймана клетки (англ. von Neumann neighborhood) — совокупность четырёх клеток на квадратном паркете, имеющих общую сторону с данной клеткой. Окрестность получила своё название в честь Джона фон Неймана, использовавшего её в своих клеточных автоматах, включая универсальный конструктор[1]. Окрестность фон Неймана и окрестность Мура являются наиболее часто используемыми окрестностями в двумерных моделях клеточных автоматов[2][3].

Понятие может быть обобщено на случай произвольного числа измерений: например, окрестность фон Неймана кубической ячейки в трёхмерном кубическом клеточном автомате состоит из шести ячеек, имеющих с ней общую грань.

Окрестность фон Неймана порядка r — множество клеток, манхэттенское расстояние до которых от данной клетки не превышает r[4]. Окрестность фон Неймана порядка r имеет форму ромба и включает в себя (не считая центральной клетки)

C_{4,r+1} - 1

клеток, где

C_{4,n} = n^2 + (n - 1)^2nцентрированное квадратное число.

В d-мерном случае общее число клеток в окрестности порядка r - число Деланноя D(d,r)[5].

Алгоритм волновой трассировки при использовании окрестности фон Неймана находит ортогональный путь[6].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Tim Tyler The von Neumann neighbourhood
  2. Клеточный автомат создаёт модель мира и мир вокруг себя. Брайан Хэйес, «В мире науки»
  3. Моделирование постбинарных клеточных автоматов
  4. Weisstein, Eric W. von Neumann Neighborhood (англ.) на сайте Wolfram MathWorld.
  5. 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), New York, NY, USA: ACM, сс. 107–114, ISBN 1-59593-010-8, DOI 10.1145/1068009.1068024 .
  6. Волновой алгоритм