NP Hard 問題はマッピングによって他の NP Hard 問題に還元されるため、私の質問は一歩前進です。たとえば、そのアルゴのすべてのステップ: 他の NP ハードにもマッピングできますか?
前もって感謝します
2 に答える
2
問題が NP 困難であることを証明する場合、通常、出力が yes または no である問題の決定バージョンを検討します。ただし、近似アルゴリズムを検討するときは、問題の最適化バージョンを検討します。
ある問題の近似アルゴリズムを使用して、NP-Hard の証明の簡約を使用して別の問題を解決すると、近似比率が変わる場合があります。たとえば、問題 A に 2 近似アルゴリズムがあり、それを使用して問題 B を解く場合、削減によって近似比が保持されないため、問題 B に O(n) 近似アルゴリズムが得られる可能性があります。したがって、ある問題に近似アルゴリズムを使用して別の問題を解決する場合は、有用なアルゴリズムを得るために、削減によって近似比が大きく変化しないようにする必要があります。たとえば、L-リダクションまたはPTAS リダクションを使用できます。
于 2013-05-06T11:10:34.447 に答える