Độ phức tạp về thời gian của thuật toán tìm kiếm toàn diện

Tôi có các bộ $S_1=\{2,10,20,6\}$ và $S_2=\{25,26,20\}$ và tôi muốn tìm những số có tổng bằng 32. Điều này rất dễ dàng bằng cách kiểm tra; 6 và 26. Nó có vẻ tương tự như vấn đề Ba lô, nhưng tôi không phải là chuyên gia.

Tuy nhiên, giả sử tôi có 1000 bộ, mỗi bộ có 500 phần tử sao cho tổng một số hạng từ mỗi bộ luôn mang lại cho bạn một giá trị duy nhất. Điều này khó kiểm tra và giải quyết hơn nhiều, đặc biệt nếu các tập hợp tuân theo một cấu trúc có vẻ ngẫu nhiên (chúng sẽ được xây dựng từ các tập hợp có cấu trúc đã bị xáo trộn và gần như không thể đoán được sự trộn lẫn và đảo ngược các tập hợp).

Vì vậy, cách duy nhất phải là Thuật toán tìm kiếm toàn diện. Với số của tôi là 52.485.332, có $1000^{500}$ tùy chọn có thể để xem xét. Thật vậy, sẽ có nhiều cách để rút ngắn tìm kiếm này (chẳng hạn như khi một tập hợp có các số lớn hơn giá trị mục tiêu của bạn, bạn có thể bỏ qua các số đó). Nhưng nếu không thì bạn có thể vẫn đang xem $750^{500}$ lựa chọn có thể.

Vì vậy, độ phức tạp thời gian của một thuật toán tìm kiếm như vậy là gì? $O(n^{k})$, với $n$ số lượng bộ và $k$ số phần tử của các tập hợp đó? Họ phải kiểm tra "tất cả" các kết hợp cụm từ có thể có cho đến khi một cụm từ khớp với giá trị đã cho.

Các câu hỏi chính dường như là "có bao nhiêu bộ?" và "bộ lớn như thế nào?". Thật vậy, các bộ cũng có thể có nhiều kích cỡ khác nhau, không chỉ đồng nhất.

Tôi không phải là người thích mật mã; nghiên cứu của tôi chỉ tán tỉnh với ý tưởng trong tầm tay. Bất kỳ trợ giúp sẽ được đánh giá cao.

Vì vậy, cách duy nhất phải là Thuật toán tìm kiếm toàn diện

Như tôi đã đề cập trong nhận xét của mình, có những phương pháp thực tế cho các giá trị không quá lớn của $m$ (và $m=52485332$ không lớn). Đây là phác thảo của một phương pháp như vậy (giả sử tất cả các tập hợp bao gồm các số nguyên không âm):

• Chúng tôi có một mảng $A_{n, m+1}$; từng phần tử của mảng $A_{a, b}$ sẽ lưu ý cách chúng ta có thể tạo tổng $b$ từ đầu tiên $a$ bộ (hoặc $\perp$ nếu chưa có cách nào như vậy được tìm thấy).

• Khởi tạo tất cả các phần tử $A$ đến $\perp$

• Vì $i := 1$ đến $n$ tìm kiếm các yếu tố $A_{i-1}$ cho không$\perp$ phần tử (và cho $i=1$, phần tử thứ 0 được coi là phần tử duy nhất không phải$\perp$ thành phần. Đối với mỗi phần tử như vậy $A_{i-1, x}$, bộ $A_{i, x + S_{i,j}}$ đến $j$ (đối với mỗi phần tử $S_{i,j}$ của bộ $S_i$) Nếu $x + S_{i,j} > m$, đừng để ý đến nó.

• Cuối cùng, nếu $A_{n,m} = \perp$, không có tập con nào dẫn đến tổng $m$. Nếu đó là bất kỳ điều gì khác, chúng tôi có thể khôi phục các thuật ngữ bằng cách quay lui qua mảng $A$.

Đây phải là một thuật toán thực tế để khôi phục các thuật ngữ cho các tham số bạn đã chỉ định.

Đây là một câu trả lời nhiều hơn cho lý do tại sao tính duy nhất của các khoản tiền lại ảnh hưởng đến quy mô đến mức trường hợp $52485332$ trở nên tầm thường (theo cách của nó để mong đợi một bình luận).

Khi tất cả các tổng phải là duy nhất, thì chúng phải dẫn đến các số nguyên khác nhau. Bởi vì có $500^{1000}$ số tiền có thể, cũng có $500^{1000}$ kết quả số nguyên khác nhau cho điều đó. trường hợp thấp nhất sẽ là tất cả các số nguyên từ $0$ đến $500^{1000}-1$.

Ví dụ,

$S_1 = \{0, 1, 2, ..., 499\}$

$S_2 = \{0, 500, 1000, ..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

sẽ là một cách để đảm bảo tính duy nhất của kết quả. Như bạn có thể thấy, Các con số trở nên lớn rất nhanh.

Trong ví dụ cụ thể này, thật dễ dàng để tìm thấy kết quả (chỉ cần luôn chọn số lớn nhất phù hợp từ tập hợp cuối cùng đến tập hợp đầu tiên). Thậm chí hầu hết các số là $S_3$ lớn hơn $52485332$ và do đó có thể bỏ qua.

Bạn có thể muốn các giá trị tương đối ngẫu nhiên trong tập hợp của mình. Trong trường hợp này, phạm vi của các giá trị ít nhất phải lớn hơn một chút.

Tuy nhiên, rất khó có khả năng bất kỳ giá trị nào thấp hơn hoặc bằng $52485332$ (khi bạn thống nhất chọn $500000$ các giá trị trong số $500^{1000}$)

Lập trình động, như @poncho đã đề xuất, thực sự chỉ hoạt động với các số nhỏ và hiệu suất của nó không tốt hơn nhiều so với tìm kiếm toàn diện (sự khác biệt tuyến tính về số lượng tập hợp), bởi vì các tổng phụ, có thể được sử dụng lại là duy nhất, lợi thế của việc không nhìn vào những khả năng khác là không có. Thời gian chạy phải theo thứ tự như tìm kiếm toàn diện. Chỉ có sự cải thiện là lên tàu khi các giá trị lớn hay nhỏ để đạt được mục tiêu, nhưng đối với các mục tiêu hợp lý thì không có nhiều lợi thế.

Bật có thể dễ dàng giảm bài toán tính tổng tập hợp con hoặc bài toán chiếc ba lô xuống bài toán này bằng cách chỉ sử dụng cùng một tập hợp nhiều lần số bạn muốn tính tổng.Vấn đề với điều này là đây không phải là một con kiến ​​​​giảm thời gian đa thức, do đó không đủ để chứng minh nếu vấn đề là NP khó.