Von Neumann-kvarteret

Von Neumann -  kvarteret i en celle er et sæt af fire celler på en firkantet parket , der har en fælles side med en given celle. Nabolaget fik sit navn til ære for John von Neumann , som brugte det i sin cellulære automater , inklusive den universelle konstruktør [1] . von Neumann - kvarteret og Moore-kvarteret er de mest almindeligt anvendte kvarterer i 2D-cellulære automatmodeller [2] [3] .

Begrebet kan generaliseres til tilfældet med et vilkårligt antal dimensioner: for eksempel består von Neumann-kvarteret i en kubisk celle i en tredimensionel kubisk cellulær automat af seks celler, der har et fælles ansigt med sig.

Et von Neumann-kvarter af orden r er det sæt af celler, hvis Manhattan-afstand fra en given celle ikke overstiger r [4] . von Neumann-kvarteret af orden r har form som en rombe og omfatter

celler hvor

I det d -dimensionelle tilfælde er det samlede antal celler i et kvarter af orden r Delannoy-tallet D ( d , r ) [5] .

Bølgesporingsalgoritmen finder, når man bruger von Neumann-kvarteret, en ortogonal vej [6] .

Se også

• Nabolag (grafteori)
• Moore kvarter
• Byblok afstand
• Cellulær automat
• Wireworld

Noter

1. ↑ Tim Tyler The von Neumann-kvarteret Arkiveret 7. maj 2013 på Wayback Machine
2. ↑ Cellular automaton skaber en model af verden og verden omkring den Arkiveret kopi af 15. maj 2013 på Wayback Machine . Brian Hayes, "In the World of Science"
3. ↑ Modellering af post-binære cellulære automater (utilgængeligt link) . Dato for adgang: 24. juli 2013. Arkiveret fra originalen 1. juni 2012. (ubestemt) 
4. ↑ Weisstein, Eric W. von Neumann Neighborhood  (engelsk) på Wolfram MathWorld- webstedet .
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, s. 107–114, ISBN 1-59593-010-8 , DOI 10.1145/1068009.1068024  .
6. ↑ Bølgealgoritme . Hentet 8. august 2013. Arkiveret fra originalen 11. december 2013. (ubestemt)