著者

柳井 孝介 伊庭 斉志

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.100, pp.1-8, 2005-03-17

参考文献数

11

被引用文献数

1

---

本稿ではNo Free Lunch Treorem (NFL)の別証明を与える.NFLは「どんな問題に対しても平均的に効率良く解けるような探索アルゴリズムは存在しない」ということを主張する定理であり, 探索アルゴリズムあるいは最適化法の研究に大きな影響を与えた.本稿では, より簡潔でかつ直観的な証明を与える.我々は評価関数の空間を部分集合に分割し, それぞれの部分集合ごとにパフォーマンスが得られる確率を合計する.関数空間の分割により, 定理のより深い理解が可能となり, またアルゴリズムと問題の関係が明確となる.