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

(Двумерная) окрестность фон Неймана порядка 1.

(Двумерная) окрестность фон Неймана порядка 2.

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

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

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

${\displaystyle C_{4,r+1}}$

клеток, где

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

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

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

См. также

• Окрестность (теория графов)
• Окрестность Мура
• Расстояние городских кварталов
• Клеточный автомат
• Wireworld

Примечания

1. Tim Tyler The von Neumann neighbourhood Архивная копия от 7 мая 2013 на Wayback Machine
2. Клеточный автомат создаёт модель мира и мир вокруг себя Архивная копия от 15 мая 2013 на Wayback Machine. Брайан Хэйес, «В мире науки»
3. Моделирование постбинарных клеточных автоматов  (неопр.). Дата обращения: 24 июля 2013. Архивировано из оригинала 1 июня 2012 года.
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, pp. 107—114, doi:10.1145/1068009.1068024, ISBN 1-59593-010-8.
6. Волновой алгоритм  (неопр.). Дата обращения: 8 августа 2013. Архивировано 11 декабря 2013 года.