文献

J-GLOBAL ID：201002206654604665   整理番号：10A0485325

確率的アルゴリズムの場合のNo Free Lunch定理の厳密な証明

A Rigorous Proof of No Free Lunch Theorem for Stochastic Algorithms

著者 (2件)： 橋谷祐司 (京大 総合人間) ,  櫻川貴司 (京大 大学院人間・環境学研究科)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2009  号： 6  ページ： ROMBUNNO.AL-129,3  発行年： 2010年04月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,確率的アルゴリズムを用いた場合におけるNo Free Lunch定理(NFL定理)を厳密に証明する。NFL定理は「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」ということが帰結される定理で,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている。本稿では確率的アルゴリズムを形式的に定義し,いくつかの補題を示した上で確率的アルゴリズムの場合のNFL定理を確率論によって厳密に証明する。(著者抄録)

シソーラス用語： *アルゴリズム ,  *確率モデル ,  定理 ,  定理証明 ,  *最適化問題 ,  *探索問題 ,  形式的手法【計算機】 ,  確率論 ,  探索アルゴリズム ,  *数学モデル
準シソーラス用語： No Free Lunch定理 ,  *確率アルゴリズム ,  補題

分類 (4件)： 計算理論  (JB02000A) ,  システム・制御理論一般  (IA02010H) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 確率 ,  アルゴリズム ,  NO ,  証明