Hãy V là một mảng của các yếu tố thuộc về một miền D (ví dụ số nguyên)số tối thiểu các hoạt động để thực hiện một hoạt động kết hợp trên bộ chồng chéo
V = {v1, v2, ..., vN}
Hãy f (x, y) là một nhà điều hành nhị phân z = f (x, y) được xác định trong [DxD] -> D.
f là liên kết và giao hoán.
f không hỗ trợ nghịch đảo trên tên miền đầy đủ của nó, tức là nếu kết quả z và một trong các đối số x hoặc y được biết, không phải lúc nào cũng có thể nhận được đối số khác.
Đưa ra một cặp chỉ số có thứ tự (i, j), toán tử g (i, j) được định nghĩa là giảm mảng phụ {vi, ..., vj} thu được với toán tử f.
Ví dụ, nếu f là toán tử nhân, tức là f (x, y) = x * y, sau đó
g(2,5) = v2 * v3 * v4 * v5
tôi cần phải tính toán g chức năng trên một tập hợp lớn các cặp (i, j), liên quan đến các phần tử chồng chéo của vectơ V.
Tôi muốn tận dụng lợi thế của tính kết hợp của toán tử f để thực hiện phép tính này với số lượng ứng dụng tối thiểu có thể của toán tử f, vì f là tính toán rất tốn kém . Ví dụ, gắn vào ví dụ trên, trong đó f là phép nhân số nguyên, cho một mảng V với 5 mục và cặp chỉ số (1,3), (2,4), (2,5), (1,4), tôi có thể tính toán tất cả các cặp với 6 phép nhân:
V={1, 2, 0, 3, 5}
1. V12 = V1 * V2
2. V13 = V12 * V3 // pair (1,3)
3. V14 = V13 * V4 // pair (1,3)
4. V23 = V2 * V3
5. V24 = V23 * V4 // pair (2,4)
6. V25 = V24 * V5 // pair (2,5)
Ai có thể đề xuất thuật toán lấy đồ thị tính toán tối ưu như tôi đã làm theo cách thủ công ở trên không? Tôi biết giải pháp cho vấn đề không phải là duy nhất. Bất kỳ giải pháp tối thiểu nào cũng có thể làm được. Ngay cả một giải pháp giả tối ưu giả cũng sẽ làm.
Cây khoảng thời gian dường như là một công cụ tốt để xác định các tính toán chồng chéo – Rerito