Ensemble Computation問題に対する二つの発見的解法の提案

DOI

書誌事項

タイトル別名
  • Proposal of Two Efficient Algorithms for the Ensemble Computation Problem

抄録

Ensemble Computation問題(EC)は，与えられた複数の積項を全て求めるまでの演算回数が最小となるような演算手順を見つける最適化問題である．ECは，論理回路の簡単化やコンパイラの最適化に応用できる．本論文では，ECに対する効率的なアルゴリズムを二つ提案する．一つはBackward Search(BS)に基づくアルゴリズムで，演算手順を逆算的に求めていく方法である．もう一つは文法圧縮に使われるアルゴリズムであるRe-Pairに着想を得たアルゴリズムで，演算手順を前から順に求めていく方法である．また，これらの手法をより精度の高いアルゴリズムにするためにBeam Searchを適用した．これによって，解となりうる複数の候補を効率良く探索することができるので，より厳密解に近い解を出力することが可能になる．計算機実験では，この二つのアルゴリズムを演算回数と計算時間の二つの観点で比較した．実験結果は，BSに基づくアルゴリズムの方が計算時間は速いが，Re-Pairに基づくアルゴリズムの方が，より演算回数が少なく厳密解に近い結果が出た．

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390860852414390912
  • DOI
    10.14923/transfunj.2022jap1032
  • ISSN
    18810195
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ