ここから本文です

一次元セルオートマトンと二次元セルオートマトンの明確な違いってなんですか?

ano********さん

2016/4/813:47:09

一次元セルオートマトンと二次元セルオートマトンの明確な違いってなんですか?

閲覧数:
386
回答数:
1

違反報告

ベストアンサーに選ばれた回答

ghw********さん

2016/4/820:27:27

1.「1次元セルオートマトンとは?」

一次元セルオートマトンとは、人工生命の分野で生命とは何かを探るデモプログラムとして考案されました。
オートマトンとは、自動機械のことです。
オート(自動)マトン(機械)です。
そしてセルというのは、細胞、小さな箱のことを表します。
以下の図を見てください、黒と白の四角があります。
それぞれの四角をセルと呼びます、各セルは隣の状態と自分の状態から、次の状態を決定します。
各セルの状態は、白か黒(□or■)を取ります。

■■■□□■□□□■□■□■■■

真ん中の白い四角に注目します、自分の両隣が黒です。そして、自分は白です。
こういう場合は、例えば次の状態を黒(■)というルールにします。
すると、
■□■



となります。同様にすべての条件のルールを定義しておきす。
必要なルールは、両隣と自分が白か黒の組み合わせなので、2の3乗の組み合わせ = 8通り のルールが必要になります。.すべてのルールを上げると…
真ん中のセルが次ぎどうなるか?

■■■ → ?
■■□ → ?
■□■ → ?
■□□ → ?
□■■ → ?
□■□ → ?
□□■ → ?
□□□ → ?
全部の8つありますよね?このルールを個々のセルに適用して、次の状態を決めていきます。
決めた状態を、先の四角の列の下に並べます、これをずっと繰り返していきます。
■■■□□■□□□■□■□■■■
■■■□□■□□□■□■□■■■
■■■□□■□□□■□■□■■■
■■■□□■□□□■□■□■■■
■■■□□■□□□■□■□■■■
■■■□□■□□□■□■□■■■
・・・続ける。

そうすると、先のセルの変化ルールの違いによって、様々な模様が現れます。
その模様の中に、フラクタル図形とよばれる特殊な模様が現れます。
個々のセルは、隣のセルの状態と自分の状態で次の状態を作っているだけなのに、複雑な模様が現れるという、不思議なことが起こるのです。
別の見方をすれば、「自己組織化」と呼んだりします。
こういう実験を通して、自己組織化によってあるパターンが生まれたりすることを分析し、生命現象の根元の機能を探そうというのが人工生命の分野です。


2.「二次元セルオートマトン」
2次元の(つまり面状の)セル・オートマトンの例として、無限に広がる方眼紙を考えます。
方眼紙のひとつのマス目がセルにあたります。
それぞれのセルは「黒」と「白」の2つの内部状態をもちます。
セルの「近傍」とは、そのセルの周辺のセル群であり、通常は隣接するセルを指します。
近傍には、フォン・ノイマン近傍(英語版)とムーア近傍(英語版)という2種類の典型的な定義があります。
前者はセル・オートマトンの考案者の名を冠しており、直交して接する4つのセルを近傍とします。
後者はフォン・ノイマン近傍を含み、さらに斜め方向の4つのセルも加えた中心のセルを囲む8つのセルの状態を考慮します。
ムーア近傍の場合、それら9つのセルが取ることができる状態は全部で29 = 512個存在します。
セル・オートマトンがどのように時間発展していくかのルールは表として与えられます。
すなわち次の時間ステップ(t+1)で、中心のセルが「黒」「白」いずれになるかは、現在の時間ステップ(t)でとり得る512個のパターンそれぞれについての一覧表によって決定されます。
ライフゲームはこのモデルの有名な例です、もう1つのよく知られている近傍の定義として「拡張フォン・ノイマン近傍」があり、直交する4方向それぞれの最も近い2つのセルを近傍とし、全部で8つのセルを近傍とします。
セルがとりうる状態数を k、次の状態を決定するのに使われる近傍のセル数(自身も含める場合がある)を s とすると、このようなシステムの規則は kks という式で表されます。
したがって2次元のシステムでムーア近傍の場合、考えられるオートマトンの総数は 229 または 1.34×10154 となる。
例えば1次元セル・オートマトンでは、時刻(ステップ)を t、位置を1次元の i としたとき、セル xit の近傍は {xi−1t−1, xit−1, xi+1t−1} となります。

2次元のセル・オートマトンで最も有名なものがライフゲームです。
ライフゲームは以下のようなルールで記述されます。
誕生: 死んでいるセル(「白」)の周囲に3つの生きているセル(「黒」)があれば次の時間ステップでは生きる(「黒」になる)。
維持: 生きているセル(「黒」)の周囲に2つか3つの生きているセル(「黒」)があれば次の世代でも生き残る(「黒」のままである)。
死亡: 上以外の場合には次の世代では死ぬ(「白」になる)。

このライフゲームのルールは細菌などの生物の繁殖のアナロジーです。
すなわち、孤独でも人口過密でも死んでしまいます。
最も快適な人口密度では子孫を残し繁栄するというものです。
実際ライフゲームは生物の増殖のような複雑で多様な振舞いを示します。

一般に、各セルは同じ状態から開始し、一部の有限個のセルだけがそれ以外の状態から開始します。
これを「コンフィギュレーション」と呼びます。また、全体が周期的なパターンを形成していて、一部がそのパターンから外れた状態で開始するということもあります。
後者は1次元のセル・オートマトンでは一般的です。

セル・オートマトンのシミュレーションには有限の格子を使うことが多い。
2次元の場合、無限の平面ではなく、有限の四角形で表されます。
有限の格子での明らかな問題は端のセルをどう扱うかです。
端をどう扱うかが格子全体のセルの状態に影響を与えます。
1つの手法は、端のセルを全て変化しない定数を状態として持つとするものです。別の手法は端のセルの近傍を一般のセルとは違う内容にするというものです。
つまり、端のセルの近傍を通常より少なく定義することもできますが、その場合は規則も新たに定義しなければなりません。
別の手法として、2次元の場合に四角形の平面の端の上下と左右を繋げて、トーラス形にすることもあります。
これは、ある意味で無限の平面が同じ四角形で平面充填されていることになります。
1次元であれば、線の端を繋いでループにすることになります。
これは端の問題を回避するために行いますが、モジュロ演算関数を使って容易にプログラム可能という利点もあります。

http://aidiary.hatenablog.com/entry/20120113/1326464820

1.「1次元セルオートマトンとは?」...

質問した人からのコメント

2016/4/10 22:55:24

非常に詳しく分かりやすい回答ありがとうございます。

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる