低性能デバイスに有効な分散アルゴリズムの開発

点击翻译按钮获取中文摘要

本研究では、個体群プロトコルモデル上で動作する基礎的アルゴリズムの構築を目指す。個体群プロトコルモデルは、多数の個体と呼ばれるデバイスが受動的に移動し、その衝突時に交流が発生し、状態を更新することで計算を進めていくモデルであり、メモリ量などが限られる低性能デバイス群への応用が期待されている。前年度までは、特に個体群プロトコルモデルでさまざまな状況を想定したk分割アルゴリズムの構築に取り組んだ．k分割アルゴリズムとは個体群を任意のk個のグループに分ける問題であり、この問題を解くことができればタスク分散などによる効率的なタスク処理を可能となる．本年度の具体的な成果は以下の通りである．(1)交流できる個体が限られた状況で動作するk分割アルゴリズムの開発：前年度において行ったk分割問題の成果を論文としてまとめた。それまでのアルゴリズムでは、すべての個体がお互いに交流可能であるという仮定で問題を考えてきたが、本成果では交流可能な個体が限られている状況でk分割問題を扱った。これにより、アルゴリズムはより多くの環境に適用可能となると考えられる。(2)前年度に構想していたグラフ形状決定アルゴリズムも数学的証明を与え、国内会議・国際会議にて発表を行った。グラフ形状決定アルゴリズムは通信グラフが所望の形状かどうかを判定するアルゴリズムである。ここで通信グラフとは、ノードを個体、辺をその個体間で交流可能かどうかで表したグラフである。通信グラフの形状を知ることは効率的なアルゴリズムの構築に大きく役立つ。本研究では判定するグラフの形状として二部グラフ・木グラフ・リンググラフ・ライングラフ・正則グラフ・完全グラフ・スターグラフを扱った。各グラフにおいて、正しい判定を行うアルゴリズムを提案し、さらに、正則グラフと完全グラフ以外に関しては定数状態数で正しい判定を行うアルゴリズムを提案した。