phương pháp hiệu quả để thực hiện tổng kết

Question

Có kỹ thuật hiệu quả nào để thực hiện tổng kết sau không?

Cho một tập hữu hạn Một chứa n số nguyên A = {X1, X2, ..., Xn}, nơi Xi là một số nguyên. Hiện có n tập hợp con của A, được biểu thị bằng A1, A2, ..., An. Chúng tôi muốn tính tổng kết cho từng tập hợp con. Có một số kỹ thuật hiệu quả?

(Lưu ý rằng n thường lớn hơn kích thước trung bình của tất cả các tập con của Một.)

Ví dụ, nếu A = {1,2,3,4,5,6 , 7,9}, A1 = {1,3,4,5}, A2 = {2,3,4}, A3 = .... Một cách ngây thơ của tính tổng cho A1 và A2 nhu cầu 5 thất bại cho bổ sung:

Sum (A1) = 1 + 3 + 4 + 5 = 13

Sum (A2) = 2 + 3 + 4 = 9

...

Bây giờ, nếu tính 3 + 4 đầu tiên, và sau đó ghi kết quả của nó 7, chúng tôi chỉ cần 3 thất bại cho addtions:

Sum (A1) = 1 + 7 + 5 = 13

Sum (A2) = 2 + 7 = 9

...

gì về trường hợp tổng quát? Có phương pháp hiệu quả nào để tăng tốc độ tính toán không? Cảm ơn!

Answer 1

Đối với một số lựa chọn của tập hợp phụ có nhiều cách để tăng tốc độ tính toán, nếu bạn không ngại làm một số tiền (có thể tốn kém) precomputation, nhưng không phải cho tất cả. Ví dụ: giả sử các tập con của bạn là {1,2}, {2,3}, {3,4}, {4,5}, ..., {n-1, n}, {n, 1}; sau đó cách tiếp cận ngây thơ sử dụng một phép toán số học cho mỗi tập con, và bạn rõ ràng không thể làm tốt hơn điều đó. Mặt khác, nếu tập con của bạn là {1}, {1,2}, {1,2,3}, {1,2,3,4}, ..., {1,2, ..., n} sau đó bạn có thể nhận được bằng với các số học số học n-1, trong khi cách tiếp cận ngây thơ là tồi tệ hơn nhiều.

Dưới đây là một cách để thực hiện precomputation. Nó sẽ không luôn luôn tìm thấy kết quả tối ưu. Đối với mỗi cặp tập con, hãy xác định chi phí chuyển đổi thành phút (kích thước chênh lệch đối xứng, kích thước Y - 1). (Sự khác biệt đối xứng của X và Y là tập hợp các thứ trong X hoặc Y nhưng không phải cả hai.) Vì vậy, chi phí chuyển đổi là số phép tính số học bạn cần làm để tính tổng các phần tử của Y, với tổng của X's. Thêm bộ trống vào danh sách các tập hợp con của bạn và tính toán cây kéo dài chi phí tối thiểu bằng thuật toán Edmonds (http://en.wikipedia.org/wiki/Edmonds%27_algorithm) hoặc một trong các biến thể nhanh hơn nhưng phức tạp hơn trên chủ đề đó. Bây giờ hãy chắc chắn rằng khi cây bao trùm của bạn có cạnh X -> Y bạn tính X trước Y. (Đây là "kiểu topo" và có thể được thực hiện hiệu quả.)

Điều này sẽ cho kết quả tối ưu dưới mức rõ ràng khi, ví dụ: bạn có {1,2}, {3,4}, {1,2,3,4}, {5,6}, {7,8}, {5,7,7,8}. Sau khi quyết định thứ tự hoạt động của bạn bằng cách sử dụng quy trình trên, bạn có thể thực hiện một bước tối ưu hóa, nơi bạn tìm thấy cách rẻ hơn để đánh giá tổng của mỗi tập hợp cho số tiền đã tính, và điều này có thể sẽ cho kết quả khá tốt trong thực tế.

Tôi nghi ngờ, nhưng không cố gắng chứng minh, rằng việc tìm kiếm một quy trình tối ưu cho tập hợp con các tập con nhất định là NP-hard hoặc tệ hơn. (Chắc chắn là tính toán; bộ tính toán có thể có mà bạn có thể làm là hữu hạn. Nhưng, đối mặt với nó, nó có thể cực kỳ tốn kém; có khả năng bạn sẽ theo dõi khoảng 2^n khoản tiền một phần, thêm bất kỳ một trong số chúng ở mỗi bước khác, và có tới khoảng 2 bước, cho một chi phí siêu ngây thơ (2^2n)^(n^2) = 2^(2n^3) hoạt động để thử mọi khả năng.)

Answer 2

Nếu giả sử tổng kết là hành động tốn thời gian, bạn có thể tìm thấy LCS của mỗi cặp tập con (bằng cách giả định chúng được sắp xếp như được đề cập trong nhận xét hoặc nếu chúng không được sắp xếp), sau đó tính tổng LCS có độ dài tối đa (trên tất cả LCS theo cặp), sau đó thay thế giá trị của nó trong các mảng liên quan bằng các số liên quan, cập nhật LCS của chúng và tiếp tục theo cách này cho đến khi không có LCS với nhiều hơn một số. Chắc chắn đây không phải là tối ưu, nhưng nó tốt hơn so với thuật toán ngây thơ (số lượng nhỏ hơn của tổng kết). Tuy nhiên bạn có thể làm backtracking để tìm giải pháp tốt nhất.

ví dụ Đối với đầu vào mẫu của bạn:

A1={1,3,4,5} , A2={2,3,4} 

LCS (A_1,A_2) = {3,4} ==>7 ==>replace it: 

A1={1,5,7}, A2={2,7} ==> LCS = {7}, maximum LCS length is `1`, so calculate sums. 

Tuy nhiên bạn có thể cải thiện nó bằng cách tổng hợp tính toán của hai số ngẫu nhiên, sau đó một lần nữa tham gia LCS, ...

Answer 3

Giả sử rằng 'Ngoài ra' không phải là chỉ đơn giản là một hoạt động ADD nhưng thay vào đó một số chức năng rất chuyên sâu liên quan đến hai toán hạng số nguyên, thì cách tiếp cận rõ ràng sẽ là lưu vào bộ nhớ cache kết quả.

Bạn có thể đạt được điều đó thông qua cấu trúc dữ liệu phù hợp, ví dụ: từ điển khóa-giá trị có chứa các khóa được tạo bởi hai toán hạng và câu trả lời làm giá trị.

Nhưng khi bạn đã xác định C trong câu hỏi, sau đó cách tiếp cận đơn giản nhất sẽ là một n bởi n mảng các số nguyên, nơi mà các giải pháp cho x + y được lưu trữ tại array[x][y].

Sau đó bạn có thể lặp đi lặp lại lặp lại các tập con, và đối với mỗi cặp toán hạng bạn kiểm tra vị trí thích hợp trong mảng. Nếu không có giá trị thì nó phải được tính toán và được đặt trong mảng. Giá trị sau đó thay thế hai toán hạng trong tập hợp con và bạn lặp lại.

Nếu hoạt động là giao hoán thì các toán hạng phải được sắp xếp trước khi tìm kiếm mảng (tức là chỉ số đầu tiên luôn là nhỏ nhất trong hai toán hạng) vì điều này sẽ tối đa hóa số lần truy cập "bộ nhớ cache".

Answer 4

Kỹ thuật tối ưu hóa phổ biến là tính toán trước các kết quả trung gian. Trong trường hợp của bạn, bạn có thể tính toán trước tất cả các khoản tiền với 2 lệnh từ A và lưu trữ chúng trong bảng tra cứu. Điều này sẽ dẫn đến các mục nhập bảng |A|*|A+1|/2, trong đó |A| là bản số của A.

Để tính tổng yếu tố của Ái, bạn:

• nhìn lên tổng của hai yếu tố đầu tiên của Ai và lưu chúng trong tmp
• trong khi có một yếu tố x còn lại trong Ai :
• nhìn lên tổng tmp và x

để tính tổng yếu tố của A1 = {1,3,4,5} từ ví dụ của bạn, bạn thực hiện như sau:

• tra cứu (1,3) = 4
• tra cứu (4,4) = 8
• tra cứu (8,5) = 13

Lưu ý rằng tính tổng của bất kỳ Ái đưa không yêu cầu tổng kết, vì tất cả công việc đã được tiến hành trong khi tính toán trước bảng tra cứu.

Nếu bạn lưu trữ bảng tra cứu trong bảng băm, thì lookup() nằm trong O (1).

tối ưu hóa để có thể tiếp cận này:

• xây dựng các bảng tra cứu trong khi tính toán kết quả tổng kết; do đó, bạn chỉ tính các tóm tắt mà bạn thực sự cần. Bảng tra cứu của bạn hiện là bộ nhớ cache.
• nếu hoạt động bổ sung của bạn là giao hoán, bạn có thể tiết kiệm một nửa kích thước bộ nhớ cache của mình bằng cách chỉ lưu trữ những tóm tắt mà tóm tắt nhỏ hơn đến trước. Sau đó sửa đổi lookup() sao cho lookup(a,b) = lookup(b,a) nếu a > b.

Answer 5

NO. Không có techique hiệu quả.

Vì đó là vấn đề NP complete. và không có giải pháp hiệu quả cho vấn đề như vậy

tại sao NP-hoàn thành?
Chúng tôi có thể sử dụng thuật toán cho vấn đề này để giải quyết set cover problem, chỉ bằng cách đặt thêm tập hợp trong bộ, conatining tất cả các yếu tố.

Ví dụ: Chúng tôi có bộ yếu tố
A1 = {1,2}, A2 = {2,3}, A3 = {3,4} Chúng tôi muốn giải quyết vấn đề thiết lập trang bìa.

chúng ta thêm vào bộ này, thiết lập các số có chứa tất cả các yếu tố A4 = {1,2,3,4}

Chúng tôi sử dụng algorhitm rằng John Smith được aking cho và chúng tôi kiểm tra giải pháp A4 được đại diện whit. Chúng tôi đã giải quyết vấn đề NP-Complete.