確率的セルオートマトンに基づく組合せ最適化問題求解ハードウェアアーキテクチャ
熊澤 輝顕
2018 年度 卒 ／修士（情報科学）
修士論文の概要
本論文ではZDD (ゼロサプレス型二分決定グラフ)を用いた三角形分割パターン列挙問題解法の超高速アルゴリズムの提案と、SCA (確率セルオートマトン)に基づく組合せ最適化問題処理ハードウェアの提案をしている。組合せ最適化問題とは、要素x∈ Eの集合族2Eの中からもっとも要求を満たす集合Cmax ⊆ 2Eを求める問題である。Cmax内の要素の組合せを最適解と呼ぶ。一般的に、要素数が増えると集合族の大きさ| 2E |は指数的に大きくなる。最適解を求める方法は、集合を全て列挙するか、問題に応じた目的関数を元にヒューリティクスを用いて解く2通りの方法がある。本論文では、まずZDDを用いた列挙を行うことで、組合せ最適化問題の解を圧縮しながら超高速に列挙することが可能であることを示し、その後SCAに基づき設計した組合せ最適化問題を解くハードウェアが、並列性と柔軟性を兼ね備えていることを示すとともに、今後の発展性を示唆する。