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

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

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

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

клеток, где

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

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

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

См. также

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

Примечания