組合せ最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/12/26 02:14 UTC 版)
組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。
| |||||||||||||||||||||||||||||||||||||||||||||||||
- 1 組合せ最適化とは
- 2 組合せ最適化の概要
- 3 外部リンク
組合せ最適化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
組合せ最適化問題の多くは、独立性システム ( E , F ) {\displaystyle (E,F)} とコスト関数 c : E → R {\displaystyle c:E\to \mathbb {R} } に対して、 ∑ e ∈ X c ( e ) {\displaystyle \sum _{e\in X}c(e)} を最大（あるいは最小）にする X ∈ F {\displaystyle X\in F} を求める最適化問題に定式化できる。 例えば、以下の中で最小全域木問題はマトロイドになるが、他はマトロイドにはならず、独立性システムとなる。 巡回セールスマン問題 - Eをグラフの辺、Fはハミルトン閉路の部分集合 ナップサック問題 - Eを荷物、Fは規定の重さを超えない荷物の組合せ 最小全域木問題 - Eはグラフの辺、Fはグラフの森の集合
※この「組合せ最適化」の解説は、「マトロイド」の解説の一部です。
「組合せ最適化」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
組合せ最適化と同じ種類の言葉
固有名詞の分類
- 組合せ最適化のページへのリンク
