細線化定理の自動化:効率的な動的計画法アルゴリズムの合成【JST・京大機械翻訳】

Ji Ruyi; Zhu Tianran; Xiong Yingfei; Hu Zhenjiang

プレプリント

J-GLOBAL ID：202202212822316605 整理番号：22P0294820

細線化定理の自動化:効率的な動的計画法アルゴリズムの合成【JST・京大機械翻訳】

Automating Thinning Theorem: Synthesizing Efficient Dynamic Programming Algorithms

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年02月24日プレプリントサーバーでの情報更新日： 2023年07月21日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

動的プログラミングは重要な最適化技術であるが,効率的な動的計画アルゴリズムを設計することは,専門のプログラマに対しても難しい。効率的な動的プログラミングアルゴリズムを系統的に導出するために開発された技法は,大きなクラスの問題に対する有効性のため,多くの研究において多くの注目を集めている。理論における薄化の成功にもかかわらず,その実用的利用は,(1)薄化の適用が数学的およびアルゴリズム的背景を必要とするため,また(2)薄化を適用することは,人間の専門家によって提案されたように,アルゴリズムを生成するのに十分ではない可能性があるため,まだ限られている。本論文では,2つのアプローチ,MetHylとMetHyl+を提案し,両方の問題を解決した。第1に,MetHylはプログラム合成による薄化の応用を自動化し,従って,薄化を適用するためのユーザへの負担を除去する。第2に,MetHyl+は,3つの規則をMetHylに統合し,それは,薄化によって無視される動的計画アルゴリズムの時間複雑性に関する3つの重要因子を最適化して,このように,それは,多くのタスクに関してエキスパートレベル動的計画アルゴリズムを自動的に作り出すことができた。アルゴリズムコースのための一般的なテキストブックであるアルゴリズムへの導入から収集された16最適化問題に関連した37タスクに関するアプローチを評価した。結果は,MetHyl+が1分未満の平均時間コストで97.3%のタスクで指数関数的スピードアップを達成することを示した。さらに,MetHyl+は,タスクの70.3%で人間エキスパートによって提供される参照プログラムと同様に効率的であるアルゴリズムを生成する。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , 【Automatic Indexing@JST】

数理計画法

, , , ,

前のページに戻る