ヤマグチ　カズアキ   Kazuaki Yamaguchi   山口　一章    所属   追手門学院大学  理工学部 情報工学科    職種   教授
言語種別	日本語
発行・発表の年月	2023/11/01
形態種別	論文
査読	査読あり
標題	Ensemble Computation問題に対する二つの発見的解法の提案
執筆形態	共著・編著（代表編著を除く）
掲載誌名	電子電子情報通信学会論文誌A 基礎・境界
掲載区分	国内
出版社・発行元	電子情報通信学会
巻・号・頁	J106-A(11),267-272頁
総ページ数	6
担当区分	最終著者,責任著者
著者・共著者	池永 裕次郎,山口 一章
概要	Ensemble Computation問題(EC)は，与えられた複数の積項を全て求めるまでの演算回数が最小となるような演算手順を見つける最適化問題である．ECは，論理回路の簡単化やコンパイラの最適化に応用できる．本論文では，ECに対する効率的なアルゴリズムを二つ提案する．一つはBackward Search(BS)に基づくアルゴリズムで，演算手順を逆算的に求めていく方法である．もう一つは文法圧縮に使われるアルゴリズムであるRe-Pairに着想を得たアルゴリズムで，演算手順を前から順に求めていく方法である．また，これらの手法をより精度の高いアルゴリズムにするためにBeam Searchを適用した．これによって，解となりうる複数の候補を効率良く探索することができるので，より厳密解に近い解を出力することが可能になる．計算機実験では，この二つのアルゴリズムを演算回数と計算時間の二つの観点で比較した．実験結果は，BSに基づくアルゴリズムの方が計算時間は速いが，Re-Pairに基づくアルゴリズムの方が，より演算回数が少なく厳密解に近い結果が出た．
DOI	10.14923/transfunj.2022jap1032
ISSN	1881-0195