1 0 0 0 2次元アレイ上における一斉射撃アルゴリズムについて
- 著者
- 久岡 雅也 前田 雅史 梅尾 博司
- 出版者
- 日本ソフトウェア科学会
- 雑誌
- 日本ソフトウェア科学会大会講演論文集 (ISSN:13493515)
- 巻号頁・発行日
- vol.2003, pp.54-54, 2003
従来から数多くの研究がされている一斉射撃問題は, 主として1次元格子点上にセルを配列した1次元アレイを考察の対象とし, そのための同期アルゴリズムが考案されてきた. また2次元アレイに対しては, 正方形, 長方形など単純な形状を持つ2次元アレイ上では, 比較的容易に同期アルゴリズムの設計が可能であるが, 任意の形状を持つ2次元連結アレイに対しては,(1) 長方形などと同様なアルゴリズム設計が可能か?(2) 同期アルゴリズムの実現に必要な状態数は?(3) 同期に必要なステップ数は?など, 考察すべき問題が多く残されている. そこで本研究の目的は, 1次元アレイにおけるアルゴリズムを新しい埋め込み手法に基づいて設計することで, 2次元アレイ上において動作可能なセルの連結が任意の状態においても同期を実現でき, 初期状態において将軍位置が任意であることも示すことである.
1 0 0 0 OA シストリック・アレイ
1 0 0 0 マルチビット最適時間一斉射撃アルゴリズムの設計(NLP一般)
- 著者
- 柳原 崇 金澤 優 梅尾 博司
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. NLP, 非線形問題 (ISSN:09135685)
- 巻号頁・発行日
- vol.105, no.417, pp.35-40, 2005-11-12
- 参考文献数
- 12
- 被引用文献数
- 2
本稿では, いくつかのビット通信を基本とするセルラーオートマトン上での同期プロトコルを提案する.5ビット通信セルラーオートマトン上で内部状態数が1で動作する同期アルゴリズムを設計した.このアルゴリズムはセル数nが有限個であれば, いかなる数でも2n-2ステップという最適時間で同期するものである.従来のセルラーオートマトンでは内部状態数が4以下の同期アルゴリズムは存在しないとされており, 非常に興味深い結果となっている.