「マトロイド」の版間の差分

2025年1月13日 (月) 10:20時点における版

2025年1月14日 (火) 13:37時点における最新版

189行目:

==== オラクル ====

組合せ最適化問題において F は明示的に与えられることはまずない。F を列挙しようとすることは無謀であるので、現実には E とコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定する[[神託機械|オラクル]]{{要曖昧さ回避|date=2025年1月}}である。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためには X ⊆ E が与えられたとき X が基<ref group="注">'''X''' の基でないことに注意</ref>を含むかを判定する基拡張集合オラクルを必要とする。

では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を[[多項式時間]]で実行可能(多項式等価)だろうか<ref group="注">概念は「[[多項式時間変換]]」に詳しい</ref>。例えば、[[巡回セールスマン問題]]に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは[[完全グラフ]]であるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまり[[ハミルトン閉路問題]]と等価であり、ハミルトン閉路問題はNP完全である<ref>{{Cite book |author=Richard M. Karp |chapter=[http://www.cs.berkeley.edu/~luca/cs172/karp.pdf Reducibility Among Combinatorial Problems] |title=Complexity of Computer Computations |editor=R. E. Miller and J. W. Thatcher eds |publisher=New York: Plenum |pages=85-103 |year=1972}}</ref>ため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。