Sousedství Von Neumann - Von Neumann neighborhood

Vzdálenost na Manhattanu r = 1
Vzdálenost na Manhattanu r = 2

v mobilní automaty, sousedství von Neumann (nebo 4 sousedství) je klasicky definován na dvourozměrném čtvercová mříž a skládá se z centrální buňky a jejích čtyř sousedních buněk.[1] Sousedství je pojmenováno po John von Neumann, který jej použil k definování buněčný automat von Neumann a von Neumann univerzální konstruktér v něm.[2] Je to jeden ze dvou nejčastěji používaných typů sousedství pro dvourozměrné celulární automaty, druhým je Moore sousedství.

Toto sousedství lze použít k definici pojmu 4-připojeno pixelů v počítačová grafika.[3]

Sousedství von Neumann buňky je buňka sama a buňky v Vzdálenost na Manhattanu ze dne 1.

Koncept lze rozšířit na vyšší dimenze, například vytvoření 6článku osmistěn sousedství pro kubický buněčný automat ve třech rozměrech.[4]

Von Neumann sousedství rozsahu r

Rozšíření výše popsaného jednoduchého von Neumannova okolí má vzít množinu bodů v a Vzdálenost na Manhattanu z r > 1. Výsledkem je oblast ve tvaru kosočtverce (zobrazeno pro r = 2 na obrázku). Tito se nazývají von Neumannovy sousedství rozsahu nebo rozsahu r. Počet buněk v dvourozměrné oblasti von Neumann rozsahu r lze vyjádřit jako . Počet buněk v a d-rozměrná oblast Neumannova rozsahu r je Delannoyovo číslo D(d,r).[4] Počet buněk na povrchu a d-rozměrná oblast okolí Neumanna r je Zaitsevovo číslo (sekvence A266213 v OEIS ).

Viz také

Reference

  1. ^ Toffoli, Tommaso; Margolus, Norman (1987), Stroje celulárních automatů: Nové prostředí pro modelování, MIT Stiskněte, str. 60.
  2. ^ Ben-Menahem, Ari (2009), Historická encyklopedie přírodních a matematických věd, svazek 1, Springer, str. 4632, ISBN  9783540688310.
  3. ^ Wilson, Joseph N .; Ritter, Gerhard X. (2000), Příručka algoritmů počítačového vidění v obrazové algebře (2. vydání), CRC Press, str. 177, ISBN  9781420042382.
  4. ^ A b Breukelaar, R .; Bäck, Th. (2005), „Využití genetického algoritmu k vývoji chování ve vícerozměrných celulárních automatech: vznik chování“, Sborník ze 7. výroční konference o genetických a evolučních výpočtech (GECCO '05), New York, NY, USA: ACM, s. 107–114, doi:10.1145/1068009.1068024, ISBN  1-59593-010-8.

externí odkazy