6

それを解決するための汎用アルゴリズムのように見えるものを思いついたとき、サブセットサムの問題について読んでいました。

(defun subset-contains-sum (set sum)
    (let ((subsets) (new-subset) (new-sum))
        (dolist (element set)
            (dolist (subset-sum subsets)
                (setf new-subset (cons element (car subset-sum)))
                (setf new-sum (+ element (cdr subset-sum)))
                (if (= new-sum sum)
                    (return-from subset-contains-sum new-subset))
                (setf subsets (cons (cons new-subset new-sum) subsets)))
            (setf subsets (cons (cons element element) subsets)))))

「set」は重複を含まないリストで、「sum」はサブセットを検索する合計です。"subsets" はコンス セルのリストで、"car" はサブセット リストで、"cdr" はそのサブセットの合計です。新しいサブセットは、要素を前面にコンスするだけで、古いサブセットから O(1) 時間で作成されます。

実行時の複雑さはわかりませんが、各要素の「合計」が大きくなると、「サブセット」のサイズが2倍になり、プラス1になるように見えるため、少なくとも2次のように見えます。

以前の印象では、NP完全問題は扱いにくい傾向があり、通常期待できる最善の方法はヒューリスティックであるという印象があったため、これを投稿していますが、CPUサイクルがあると仮定すると、これは汎用目的のソリューションのようです、常に正しい答えを教えてください。このような NP 完全問題を他にいくつ解くことができますか?

4

5 に答える 5

7

NP 完全問題は解けますが、(私たちが知る限り) 多項式時間では解けません。つまり、NP 完全問題にはO(n*2^n)それを解決できるアルゴリズムがあるかもしれませんが、たとえばO(n^3)それを解決するアルゴリズムはありません。

興味深いことに、任意の NP 完全問題に対して高速 (多項式) アルゴリズムが見つかった場合、NP のすべての問題は多項式時間で解決できます。これがP=NPです。

私があなたのアルゴリズムを正しく理解していれば (これはコードよりもあなたのコメントに基づいています)、それはここO(n*2^n)のアルゴリズムと同等です。サブセットがあり、各サブセットも合計する必要があるため、アルゴリズムはです。2^nO(n*2^n)

複雑さについてもう 1 つ - はO(whatever)、特定のアルゴリズムがどれだけうまくスケールするかを示すだけです。2 つのアルゴリズムを比較して、これに基づいて一方が他方よりも高速であると言うことはできません。Big-O 記法は、実装の詳細と最適化を気にしません。同じアルゴリズムの 2 つの実装を記述して、一方が他方よりもはるかに高速であっても、どちらもO(n^2). ある女性が赤ちゃんを作るのは手術ですが、これはあなたが行うO(n)ほとんどの手術よりもはるかに時間がかかる可能性があります. O(n*log(n))これに基づいて言えることは、n の値が非常に大きい場合、ソートが遅くなるということだけです。

于 2010-03-01T02:11:10.923 に答える
5

すべての NP 完全問題には解があります。答えを計算するのに時間を費やしても構わないと思っている限り、そうです。効率的なアルゴリズムがないからといって、それがないわけではありません。たとえば、可能性のあるすべてのソリューションを反復するだけで、最終的に 1 つが得られます。これらの問題は、実世界のコンピューティングのいたるところで使用されます。問題を解決するために指数関数的な時間 (またはさらに悪い!) が必要になる場合は、自分で設定した問題がどれほど大きいかについて注意する必要があります。

于 2010-03-01T02:13:11.883 に答える
3

実行時の複雑さはわかりませんが、各要素の「合計」が大きくなると、「サブセット」のサイズが2倍になり、プラス1になるように見えるため、少なくとも2次のように見えます。

N が増加するたびに実行時間が 2 倍になる場合は、O(2^N) アルゴリズムを見ています。これは、セットのすべてのサブセット (またはセットのパワーセットのすべてのメンバー) を訪問することから期待されることでもあります。これは、正確に 2^N のメンバーであるためです (空のセットを含める場合)。

これまでに見られたすべてのセットに要素を追加するか追加しないかが高速であるという事実は、全体の処理が高速であることを意味しません。

于 2010-03-01T08:35:54.177 に答える
2

ここで行われていることは、再帰を使用してもっと簡単に表現できます。

(defun subset-sum (set sum &optional サブセット)
  （設定時
    (destructuring-bind (head . tail) セット
      (or (and (= head sum) (cons head subset)))
          (サブセットサムテールサムサブセット)
          (subset-sum tail (- sum head) (cons headサブセット))))))

最後の 2 つの再帰呼び出しは、指定されたセットのサイズである深さ n のバイナリ ツリーをトラバースしていることを明確に示しています。バイナリ ツリーのノード数は、予想どおり O(2^n) です。

于 2010-03-01T09:11:22.027 に答える
0

多項式時間に karpreducible です。ヒープまたはバイナリ検索の上限を使用して決定問題 O(nM) に Karp リダクションで還元すると、log(M*2^M)=logM+log(2^M)=logM+Mlog2 エルゴ時間:O(nM)

于 2010-03-22T02:25:09.803 に答える