본문 바로가기

개발&컴퓨터/알고리즘

Cellular Automata 를 이용한 Forest Fire Modeling (1)

반응형

Cellular Automata 란?


* John von Neumann에 의해 고안됨

* 유한개의 state를 갖는 cell이 1차원, 2차원 등의 공간에 존재
* 예를 들어 on / off 또는 생 / 사 또는 적 / 녹 / 청 등의 state를 가짐
* 각 cell은 시간에 따라, cell의 현재 state와 주변 cell들의 state에 근거한 규칙에 따라 변화한다.

* 인공지능의 한 분야인 인공생명 (Artificial Life) 연구에 사용된다.
* 개체 (cell)간의 관계를 표현함으로써 전체적인 규칙을 만들어 내게 된다.
* Self-reproducing organisms -> universal computation -> modeling of natural phenomena
* 간단한 규칙들로 구성된 CA가 복잡한 현상을 보여준다.



1차원 Cellular Automata


* state 는 0 또는 1
* 규칙은  다음과 같다


0 0 0   ->  0  1 0 0   ->  1 0 0 1   ->  1 1 0 1   ->  1
0 1 0   ->  1 1 1 0   ->  0  0 1 1   ->  0 1 1 1   ->  0



* 1로 시작한다고 가정하면


Time 0 :  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0
Time 1 :  0  0  0  0  0  0  1  1  1  0  0  0  0  0  0  0
Time 2 :  0  0  0  0  0  1  0  1  0  1  0  0  0  0  0  0
Time 3 :  0  0  0  0  1  1  1  1  1  1  1  0  0  0  0  0
Time 4 :  0  0  0  1  0  1  1  1  1  1  0  1  0  0  0  0
Time 5 :  0  0  1  1  1  0  1  1  1  0  1  1  1  0  0  0
Time 6 :  0  1  0  1  0  1  0  1  0  1  0  1  0  1  0  0



2-D CA: Game of Life

* John Conway가 1970년에 고안
* 인공생명에서 연구되는 "emergent complexity" 나 "self-organizing systems” 을 보여주는 간단한 예


* 규칙



* 단 두개의 규칙으로 여러가지 복잡한 현상이 만들어 진다.
  - Gliders, glider gun, spacefiller
* 동일한 규칙이 반복적으로 적용되어 state 가 변하는 일종의 recursion이 적용된다.
* 초기 배열에 따라 여러 가지 모양을 갖는다.
  예 ) 동영상




반응형