ハッシュライフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/07/22 02:07 UTC 版)
ハッシュライフはライフゲームないし類似したセル・オートマトンで、繰り返しパターンなどがある場合を効率的に表現したり、全盤面について1世代ずつ計算を繰り返すのではなく、影響範囲をうまく利用することで効率よく未来の状態を計算することが可能な手法である。「ハッシュ」の名の通り、ハッシュテーブルを利用した部分構造の共有が前提[1]だが、さらにメモ化を利用すれば、1世代ごとの計算の繰り返しに比べて、非常に高速に未来の世代を得ることも可能となる。初出は1980年代初期で、その頃ゼロックスパロアルト研究所の研究に参加していたビル・ゴスパーによる[2]。ゴスパーによる実装には、シンボリックスのLISPマシンと、FlavorsというLISPのオブジェクト指向拡張が用いられた。
- ^ それをしない場合、極端に効率が悪いため現実的ではない手法となってしまう。
- ^ ライフゲームでは、グライダー銃の発見などでも知られる。
- ^ Zebra stripes などのパターンの場合に最大になる。
- ^ 原文献を参照するのも良いが、Dr Dobb's Journal の解説記事 An Algorithm for Compressing Space and Time がわかりやすい。
- ^ なぜ効率的に計算できるのかはここでは説明しない。外部にある詳細な解説か、実装を読むこと。
- ^ マックス (ライフゲーム) のようなパターンのこと。
[続きの解説]
「ハッシュライフ」の続きの解説一覧
- 1 ハッシュライフとは
- 2 ハッシュライフの概要
- 3 参考文献
- ハッシュライフのページへのリンク
