組合せ最適化のソースを表示

{{pathnav|最適化問題|frame=1}}
{{出典の明記|date=2018年12月26日 (水) 02:14 (UTC)}}
'''組合せ最適化'''（くみあわせさいてきか、{{lang-en-short|combinatorial optimization}}、'''組み合わせ最適化'''、または'''組み合せ最適化'''とも表記される）は、[[応用数学]]や[[情報工学]]での[[組合せ論]]の[[最適化問題]]である。[[オペレーションズリサーチ]]、[[アルゴリズム]]理論、[[計算複雑性理論]]と関連していて、[[人工知能]]、[[数学]]、および[[ソフトウェア工学]]などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。

==非形式的定義==
組合せ最適化は、最適化問題の中でも最適解の集合が離散的であるか、離散的なものに減らすことができるものであり、その目的は最も良い解決法を見つけることである。

解が二値ベクトルの場合は'''0-1最適化問題'''（{{lang-en-short|0-1 optimization problem}}）とも言われる。

==形式的定義==
組合せ最適化問題の[[インスタンス]]は、 <math>(X,P,Y,f,\mathrm{extr})</math> の要素の[[順序組|組]] (tuple) として形式的に記述できる。

ここで
* ''X'' は解空間（solution space、その中に ''f'' と ''P'' が定義されている）
* ''P'' は実現可能かどうかを判定する関数
* ''Y'' は実現可能な解の集合
* ''f'' は最適化関数
* extr は極値（extreme、最大または最小）

==問題例==
* [[巡回セールスマン問題]]
* [[中国人郵便配達問題]]
* [[最小全域木問題]]
* [[最短経路問題]]
* [[線形計画問題]]（基底にするべき変数を選ぶ問題と見なすと組合せ的になる）
* [[整数計画問題]]
* [[エイト・クイーン]]（[[制約充足問題]]の一種）
* [[ナップサック問題]]
* [[最大流問題]]
* [[最小カット問題]]
* [[最大マッチング問題]]
* [[劣モジュラ関数最小化]]
* [[劣モジュラ関数最大化]]
<!-- この部分。完全に間違っています。上記の具体例を見れば分かるように、普通に手続き型言語で多数書かれています。
組合せ最適化アルゴリズムは[[命令型プログラミング]]言語や[[Prolog]]のような[[宣言型プログラミング]]言語で実装されることが多い。あるいは少し妥協して[[Haskell]]のような[[関数型言語]]や[[LISP]]のようなマルチパラダイム言語が使われることもある。
-->

== NP困難 ==
[[計算複雑性理論]]の研究は、組合せ最適化に役立っている。いくつかの組合せ最適化問題が、[[NP困難]]である事に関係している。そのような問題は、一般的には効率的に解けるとは思われていない。しかし、複雑性理論の様々な近似は、これらの問題のいくつか（例えば「小さな」問題）が効率的に解けることを示唆する。組合せ最適化にも近似解法があり、そのような解法はしばしば重要な応用が可能である。

==手法==
{{See also|探索}}

=== 一般的な手法 ===
<!-- 厳密解法、近似解法の分類を削除しました。全部、厳密解法ですよ。途中で打ち切れば近似解法になる場合もあるというだけです。 -->
* [[分枝限定法]]
* [[動的計画法]]
* [[力まかせ探索]]
* [[深さ優先探索]]
** [[反復深化深さ優先探索]]
** [[深さ制限探索]]
* [[幅優先探索]]
* [[均一コスト探索]]
* [[双方向探索]]
* [[貪欲法]]

=== 特定の問題に対する手法 ===
* [[最短経路問題]]
** [[ダイクストラ法]]
** [[ベルマン-フォード法]]
* 最小[[全域木]]
** [[プリム法]]
** [[クラスカル法]]
** [[ブルーフカ法]]
* [[最大フロー問題]]・最小カット問題
** [[フォード・ファルカーソンのアルゴリズム]]
** [[エドモンズ・カープのアルゴリズム]]
** [[ディニッツ法]]
** [[プリフロープッシュ法]]
* [[巡回セールスマン問題]]
** [[最近傍法]]
**[[クリストフィードのアルゴリズム]]

=== ヒューリスティックを使用する物 ===
* [[局所探索法]]、[[山登り法]]
* [[最良優先探索]]
* [[A*]]

=== メタヒューリスティック ===
{{See also|メタヒューリスティック}}
以下の発見的探索法（[[メタヒューリスティック]]アルゴリズム）は、この種の問題を解くのに使われる。
==== [[近傍探索法]] ====
* [[局所探索法]]
* [[焼きなまし法]]
* [[タブーサーチ]]

==== [[進化的計算]] ====
* [[群知能]]
** [[蟻コロニー最適化]]
* [[進化的アルゴリズム]]
** [[遺伝的アルゴリズム]]

==== その他のアルゴリズム ====
* [[GRASP (メタヒューリスティック)|GRASP]]
* [[Population-based incremental learning]]
* [[シミュレーティド・エボリューション]]
* [[Reactive search]]

== 参考文献 ==
* B.コルテ、J.フィーゲン：「組合せ最適化 [原書6版]：理論とアルゴリズム」、丸善、ISBN 978-4-621-30762-5 (2022年11月).
* 河原吉伸、永野清仁：「劣モジュラ最適化と機械学習」、講談社サイエンティフィク、ISBN 978-4-06-152909-0 (2015年12月8日).

==関連項目==
* [[探索]]
* [[マトロイド]]
* [[離散凸解析]]
* [[組合せ数学]]

== 外部リンク ==
* [http://research.nii.ac.jp/~uno/combi_1.htm 組合せ最適化（研究者向けの解説）]
* [http://hp.vector.co.jp/authors/VA016496/glps/GLPS11.html 組合せ最適化応用例]
* [http://www-or.amp.i.kyoto-u.ac.jp/members/yagiura/open-campus-2004/happyo-shiryo.pdf 簡単そうで難しい組合せ最適化(PDF)]
* [https://doi.org/10.3389/fphy.2014.00005 Andrew Lucas:"Ising formulations of many NP problems", Front.Phys (Feb. 2014)]

{{最適化アルゴリズム}}

{{DEFAULTSORT:くみあわせさいてきか}}
[[Category:組合せ最適化|*]]
[[Category:組合せ論]]
[[Category:最適化]]
[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]