くみあわせさいてきか‐もんだい〔くみあはせサイテキクワモンダイ〕【組(み)合(わ)せ最適化問題】
組合せ最適化
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2018年12月) |
組合せ最適化(くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。
非形式的定義
組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最も良い解決法を見つけることである。
解が二値ベクトルの場合は0-1最適化問題(英: 0-1 optimization problem)とも言われる。
形式的定義
組合せ最適化問題のインスタンスは、
一般 | |
---|---|
微分可能 |
凸最小化 | |||||||
---|---|---|---|---|---|---|---|
線形 および 二次 |
|
系列範例 (Paradigms) | |||||
---|---|---|---|---|---|
グラフ理論 |
| ||||
ネットワークフロー (最大流問題) |