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