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

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

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

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

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

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

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

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