Vấn đề tập con-sum và khả năng giải được của NP-đầy đủ các vấn đề

Question

Tôi đã đọc về vấn đề tập hợp con-tiền khi tôi đã đưa ra những gì dường như là một thuật toán có mục đích chung để giải quyết nó:

(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" là danh sách không chứa các từ khóa trùng lặp và "tổng hợp" là tổng để tìm kiếm các tập con. "tập hợp con" là danh sách các ô đối sánh trong đó "ô tô" là danh sách tập hợp con và "cdr" là tổng của tập hợp con đó. Các tập con mới được tạo từ các tập con cũ trong thời gian O (1) bằng cách chỉ cần gán phần tử cho mặt trước.

Tôi không chắc độ phức tạp của thời gian chạy là gì, nhưng xuất hiện với mỗi phần tử "tổng" tăng lên, kích thước của "tập hợp con" tăng gấp đôi, cộng thêm một, vì vậy nó xuất hiện với tôi ít nhất là bậc hai.

Tôi đăng bài này bởi vì ấn tượng của tôi trước đây là các vấn đề NP-complete có xu hướng khó hiểu và điều tốt nhất thường có thể hy vọng là một heuristic, nhưng điều này dường như là một giải pháp đa năng, giả sử bạn có chu kỳ CPU, luôn luôn cung cấp cho bạn câu trả lời đúng. Có bao nhiêu vấn đề NP-complete khác có thể được giải quyết như thế này?

Answer 1

Tất cả các sự cố NP-complete đều có giải pháp. Miễn là bạn sẵn sàng dành thời gian để tính toán câu trả lời, đó là. Chỉ vì không có thuật toán hiệu quả, không có nghĩa là không có thuật toán. Ví dụ, bạn chỉ có thể lặp qua mọi giải pháp tiềm năng và cuối cùng bạn sẽ có được một giải pháp. Những vấn đề này được sử dụng khắp nơi trên thế giới thực. Bạn chỉ cần cẩn thận về một vấn đề lớn mà bạn đặt ra cho chính mình nếu bạn cần thời gian theo cấp số nhân (hoặc tệ hơn!) Để giải quyết nó.

Answer 2

Sự cố NP-complete có thể giải quyết được, không phải trong thời gian đa thức (theo như chúng tôi biết). Nghĩa là, một vấn đề NP-complete có thể có một thuật toán O(n*2^n) có thể giải quyết nó, nhưng nó sẽ không có, ví dụ, một thuật toán O(n^3) để giải quyết nó.

Thật thú vị, nếu thuật toán nhanh (đa thức) được tìm thấy cho bất kỳ vấn đề NP-complete nào thì mọi vấn đề trong NP đều có thể được giải quyết trong thời gian đa thức. Đây là những gì P = NP là về.

Nếu tôi hiểu thuật toán của bạn chính xác (và điều này dựa trên nhận xét của bạn nhiều hơn trên mã), thì nó tương đương với thuật toán O(n*2^n)here. Có 2^n tập hợp con và do bạn cũng cần tính tổng mỗi tập hợp con, thuật toán là O(n*2^n).

Một điều nữa về độ phức tạp - O(whatever) chỉ cho biết thuật toán cụ thể có quy mô như thế nào. Bạn không thể so sánh hai thuật toán và nói rằng một thuật toán nhanh hơn các thuật toán khác dựa trên điều này. Ký hiệu Big-O không quan tâm đến chi tiết triển khai và tối ưu hóa - có thể viết hai cách triển khai cùng một thuật toán với một thuật toán nhanh hơn nhiều so với thuật toán khác, mặc dù cả hai có thể là O(n^2). Một phụ nữ làm cho trẻ sơ sinh là hoạt động của O(n), nhưng có khả năng là việc này sẽ mất nhiều thời gian hơn hầu hết các loại bạn thực hiện O(n*log(n)). Tất cả những gì bạn có thể nói dựa trên điều này là việc phân loại sẽ chậm hơn đối với các giá trị rất lớn trên n.

Answer 3

Tôi không chắc chắn những gì thời gian chạy phức tạp của nó, nhưng dường như với mỗi yếu tố "tiền" phát triển bởi, kích thước của "tập con" tăng gấp đôi, cộng với một, để nó xuất hiện với tôi ít nhất là bậc hai.

Nếu thời gian chạy tăng gấp đôi cho mỗi lần tăng N, bạn đang xem thuật toán O (2^N). Đó cũng là những gì tôi mong đợi từ việc truy cập tất cả các tập hợp con của một tập hợp (hoặc tất cả các thành viên của một tập hợp), vì đó là chính xác 2^N thành viên (nếu bạn bao gồm tập hợp rỗng).

Thực tế là việc thêm hoặc không thêm phần tử vào tất cả các bộ đã thấy cho đến nay là nhanh không có nghĩa là tổng số quá trình xử lý nhanh.

Answer 4

gì đang xảy ra ở đây có thể được thể hiện nhiều hơn nữa chỉ đơn giản là sử dụng đệ quy:

 
(defun subset-sum (set sum &optional subset) 
    (when set 
    (destructuring-bind (head . tail) set 
     (or (and (= head sum) (cons head subset)) 
      (subset-sum tail sum   subset) 
      (subset-sum tail (- sum head) (cons head subset)))))) 

Hai cuộc gọi đệ quy ở cuối hiển thị rõ ràng chúng ta đang đi qua một cây nhị phân của sâu n, kích thước của các tập hợp . Số lượng các nút trong cây nhị phân là O (2^n), như mong đợi.

Answer 5

Đó là điều khó hiểu đối với thời gian đa thức. Giảm với giảm Karp thành một vấn đề quyết định O (nM) bằng cách sử dụng một giới hạn trên hoặc tìm kiếm nhị phân trên là log (M * 2^M) = logM + log (2^M) = logM + Mlog2 Thời gian Ergo: O (nM)