組合せ最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』
組合せ最適化(Combinatorial optimization。組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学と情報工学での最適化の一部であり、オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、一般に難しいと思われる問題を解くために、その問題の広大な解空間を探索する。組合せ最適化のアルゴリズムは、解空間を狭めたり、効率的に探索を行う。
組合せ最適化アルゴリズムは命令型プログラミング言語やPrologのような宣言型プログラミング言語で実装されることが多い。あるいは少し妥協してHaskellのような関数型言語やLISPのようなマルチパラダイム言語が使われることもある。
計算複雑性理論の研究は、組合せ最適化に役立っている。組合せ最適化アルゴリズムは、一般にNP困難である問題に関係している。そのような問題は、一般に効率的に解けるとは思われない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか(例えば「小さな」問題)が効率的に解けることを示唆する。組合せ最適化は実にそのケースであり、そのような例はしばしば重要な応用が可能である。
目次 |
[編集] 非形式的定義
組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最もよい解決法を見つけることである。
[編集] 形式的定義
組合せ最適化問題のインスタンスは、(X,P,Y,f,extr)の要素の組(touple)として形式的に記述できる。
ここで
- X は解空間(solution space、その中に f と P が定義されている)
- P は実現可能かどうかを判定する関数
- Y は実現可能な解の集合
- f は最適化関数
- extr は極値(extreme、最大または最小)
[編集] 問題例
[編集] 手法
以下の発見的探索法(メタヒューリスティックアルゴリズム)は、この種の問題を解くのに使われる。
[編集] 関連項目
- 離散最適化
- 検索
- 力まかせ探索
- 状態空間探索
これらの手法に関しては効率が最も重視される。すなわち、全てのタイプの問題についてどの探索手法が最も効率的か、である。その質問への答えは90年代にノーフリーランチ定理で示された。
