algorithm - NP 最適化問題 (定義)

Question

NPOの定義を理解しようとしています。

ここで定義を読みました：http://www.nada.kth.se/~viggo/wwwcompendium/node2.html

最小の頂点カバーを見つけようとすると、I、sol(x)、および m は何ですか? (目標は最小)

Answer 1

あなたが投稿したリンクから判断すると、これは最小頂点カバーの解釈だと思います:

• I : すべてのグラフの集合。
• sol(x) : グラフx ∈ Iの可能な解のセット。つまり、すべてのエッジをカバーする頂点のすべてのサブセットです。
• m(x,y) :インスタンスxに対する解yの値。頂点カバーの場合、セット内の頂点の数。