Matrix Chain Multiplication

Q: Độ phức tạp thời gian của phép nhân chuỗi ma trận là bao nhiêu?

Bảng có khoảng n²/2 đoạn và mỗi đoạn thử tối đa n cách chia, vì vậy quy hoạch động có thời gian chạy O(n³) và cần O(n²) bộ nhớ. Đệ quy thuần không dùng bộ nhớ đệm sẽ gọi 3^(n-1) lần với n ma trận.

Q: Tại sao thứ tự nhân ma trận lại quan trọng?

Phép nhân ma trận có tính kết hợp, vì vậy (AB)C và A(BC) cho ra cùng một ma trận, nhưng các ma trận trung gian có kích thước khác nhau. Trong ví dụ đầu tiên, (AB)C tạo ma trận 4 × 3 với chi phí 264, còn A(BC) tạo ma trận 10 × 12 với chi phí 840.

Q: Tự bạn tìm cách đặt dấu ngoặc tối ưu như thế nào?

Lưu điểm chia tối ưu trong choice[left][right] bên cạnh best[left][right] . Để in ra, nếu chỉ có một ma trận thì in tên của ma trận; nếu có nhiều ma trận liên tiếp thì in dấu ngoặc mở, phần trước choice[left][right] , phần sau nó và dấu ngoặc đóng. Cách này cần thêm bộ nhớ O(n²) .

KhóQuy hoạch động

+10

Một chuỗi ma trận được mô tả bằng dims: ma trận i có dims[i] hàng và dims[i+1] cột, nên mỗi ma trận có kích thước phù hợp với ma trận tiếp theo. Nhân ma trận p × q với ma trận q × r cần p × q × r phép nhân vô hướng và cho ra ma trận p × r. Mọi cách đặt dấu ngoặc đều cho cùng một tích cuối cùng, nhưng không có cùng chi phí. Hãy trả về số phép nhân vô hướng ít nhất cần thiết để nhân toàn bộ chuỗi.

Hàm

matrixChainOrder(dims: integer-array) → integer

dimsinteger-array: kích thước dọc theo chuỗi: ma trận i có kích thước dims[i] × dims[i+1]
Trả vềinteger: số phép nhân vô hướng ít nhất để nhân toàn bộ chuỗi

Ràng buộc

2 ≤ dims.length ≤ 100, vì vậy chuỗi này gồm từ 1 đến 99 ma trận.
1 ≤ dims[i] ≤ 100
Đáp án tối đa là 98 × 10⁶, nằm gọn trong giới hạn của số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: dims = [4, 10, 3, 12]
Đầu ra: 264
Giải thích: Nhân hai ma trận đầu tiên tốn 4 × 10 × 3 = 120 và cho ra một ma trận 4 × 3. Nhân ma trận này với ma trận 3 × 12 tốn thêm 144, tổng cộng là 264. Thứ tự còn lại tốn 360 + 480 = 840.

Câu hỏi mở rộng

Bạn cũng có thể đếm số cách đặt dấu ngoặc khác nhau để đạt chi phí tối thiểu không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thứ tự làm thay đổi chi phí: 264 so với 840 trong ví dụ đầu tiên. Hãy xem phép nhân cuối cùng. Nó kết hợp tích của phần bên trái và phần bên phải trong chuỗi, mỗi phần đều là cùng một bài toán trên một chuỗi ngắn hơn. Một bảng bao quát các đoạn của chuỗi giải mỗi bài toán đúng một lần, với thời gian O(n³).

Thử mọi cách chia bằng đệ quy thuần túy

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Đánh số các ranh giới của chuỗi từ 0 đến m-1, trong đó m = dims.length: ranh giới k có kích thước dims[k]. Các ma trận nằm giữa ranh giới left và right khi nhân với nhau sẽ tạo thành ma trận kích thước dims[left] × dims[right], bất kể thứ tự nhân. Vì vậy, nếu bước cuối cùng chia đoạn đó tại split, chi phí của bước này là dims[left] × dims[split] × dims[right], bất kể những gì đã diễn ra bên trong hai khối. Mỗi khối cần được tạo với chi phí thấp nhất có thể, nên cheapest(left, right) là tổng chi phí nhỏ nhất của hai khối cộng với bước cuối cùng, xét qua mọi giá trị split. Thử mọi cách chia ở bước cuối cùng sẽ đảm bảo lời giải đúng.

Thuật toán giải đi giải lại cùng một đoạn: với n ma trận, cần 3^(n-1) lời gọi, khoảng 1.2 × 10^9 lời gọi với 20 ma trận, trong khi chỉ có khoảng m²/2 đoạn khác nhau.

Thuật toán

Viết cheapest(left, right) cho các ma trận nằm giữa hai ranh giới left và right.
Nếu right - left < 2, chỉ có một ma trận: trả về 0.
Với mỗi split nằm giữa chúng, cộng cheapest(left, split), cheapest(split, right) và dims[left] × dims[split] × dims[right].
Trả về tổng nhỏ nhất.
Đáp án là cheapest(0, m-1).

def matrixChainOrder(dims):
    def cheapest(left, right):
        # The fewest multiplications for the matrices between boundaries left and right
        if right - left < 2:
            return 0  # a single matrix costs nothing
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        return best

    return cheapest(0, len(dims) - 1)

Đệ quy với bộ nhớ đệm

Ý tưởng

Mỗi lần gọi chỉ phụ thuộc vào left và right. Lưu kết quả vào memo[left][right], với mọi ô ban đầu có giá trị -1, một giá trị mà không chi phí thực nào có thể nhận được; các lần gọi sau đọc ô đó thay vì gọi đệ quy. Mỗi cặp trong khoảng m²/2 cặp chỉ được giải một lần với ít hơn m lần chia: O(n³), hoặc 161.700 lượt kiểm tra điểm chia cho 99 ma trận. Đệ quy không bao giờ sâu hơn độ dài của chuỗi, nên 100 ranh giới vừa với mọi ngăn xếp lời gọi.

Thuật toán

Cấp phát memo với m hàng và m cột, đặt mọi ô bằng -1.
Trong cheapest(left, right), nếu đoạn chỉ gồm một ma trận thì trả về 0, còn nếu ô khác -1 thì trả về chi phí đã lưu.
Nếu không, tính chi phí cho từng split giống hệt như cách đệ quy thông thường và lấy giá trị nhỏ nhất.
Ghi giá trị nhỏ nhất đó vào memo[left][right] trước khi trả về.
Đáp án là cheapest(0, m-1).

def matrixChainOrder(dims):
    m = len(dims)
    # memo[left][right]: the answer for boundaries left and right, -1 while unknown
    memo = [[-1] * m for _ in range(m)]

    def cheapest(left, right):
        if right - left < 2:
            return 0  # a single matrix costs nothing
        if memo[left][right] != -1:
            return memo[left][right]
        best = None
        for split in range(left + 1, right):
            cost = (cheapest(left, split) + cheapest(split, right)
                    + dims[left] * dims[split] * dims[right])
            if best is None or cost < best:
                best = cost
        memo[left][right] = best
        return best

    return cheapest(0, m - 1)

Điền vào bảng bằng cách kéo giãn chiều rộng

Ý tưởng

Mỗi ô chỉ phụ thuộc vào các đoạn hẹp hơn, vì vậy các vòng lặp có thể điền best[left][right] từ hẹp đến rộng. Độ rộng 1 là một ma trận đơn và giữ nguyên giá trị 0. Khi đến một đoạn rộng hơn, cả hai phần của mọi cách chia đều đã được tính xong. Với dims = [6, 2, 7, 3, 5]:

Độ rộng 2: best[0][2] = 84, best[1][3] = 42, best[2][4] = 105.
Độ rộng 3: best[0][3] là 78 (cách chia 1: 0 + 42 + 36), best[1][4] là 72 (cách chia 3: 42 + 0 + 30).
Độ rộng 4: các cách chia 1, 2 và 3 lần lượt cho 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 và 78 + 0 + 90 = 168, vậy best[0][4] = 132.

Cách chia tối ưu ở ranh giới 1 có nghĩa là ma trận 6 × 2 được ghép cuối cùng, như trong ví dụ thứ hai. Thời gian và bộ nhớ tương đương với phiên bản ghi nhớ kết quả, nhưng không dùng đệ quy.

Thuật toán

Gọi m = dims.length và cấp phát một bảng m × m tên best, chứa toàn số 0.
Lặp width từ 2 đến m-1. Bên trong vòng lặp này, tăng left từ 0 khi right = left + width vẫn nằm trong giới hạn.
Với đoạn đó, tính best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right] cho mọi split từ left+1 đến right-1, rồi lưu giá trị nhỏ nhất vào best[left][right].
Đáp án nằm trong best[0][m-1].

def matrixChainOrder(dims):
    m = len(dims)
    # best[left][right]: the fewest multiplications for the matrices
    # between boundary left and boundary right (0 for a single matrix)
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            low = None
            for split in range(left + 1, right):
                # the last product joins a dims[left] x dims[split] block
                # with a dims[split] x dims[right] block
                cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
                if low is None or cost < low:
                    low = cost
            best[left][right] = low
    return best[0][m - 1]

Lỗi thường gặp và trường hợp biên

Nhân cặp có tích nhỏ nhất trước. Với [10, 10, 1, 9], cặp cuối cùng có tích nhỏ nhất (90), nhưng bước tiếp theo tốn 900, tổng cộng là 990. Nhân cặp đầu tiên trước chỉ tốn 190.
Đọc kết quả từ nhầm ô. dims có nhiều hơn số ma trận một phần tử, vì vậy đáp án là best[0][m-1], không phải best[0][m].
Cho left tăng dần trong vòng lặp ngoài. Khi đó, hàng left đọc best[split][right] từ một hàng phía sau vẫn còn bằng 0. Đặt độ rộng ở vòng lặp ngoài hoặc đếm left giảm dần.
Bỏ sót trường hợp chỉ có một ma trận. [3, 7] phải trả về 0, còn trong R, vòng lặp 2:(m-1) trở thành 2:1 và chạy ngược, vì vậy cần kiểm tra điều kiện trước.

Câu hỏi thường gặp3

Độ phức tạp thời gian của phép nhân chuỗi ma trận là bao nhiêu?

Bảng có khoảng n²/2 đoạn và mỗi đoạn thử tối đa n cách chia, vì vậy quy hoạch động có thời gian chạy O(n³) và cần O(n²) bộ nhớ. Đệ quy thuần không dùng bộ nhớ đệm sẽ gọi 3^(n-1) lần với n ma trận.

Tại sao thứ tự nhân ma trận lại quan trọng?

Phép nhân ma trận có tính kết hợp, vì vậy (AB)C và A(BC) cho ra cùng một ma trận, nhưng các ma trận trung gian có kích thước khác nhau. Trong ví dụ đầu tiên, (AB)C tạo ma trận 4 × 3 với chi phí 264, còn A(BC) tạo ma trận 10 × 12 với chi phí 840.

Tự bạn tìm cách đặt dấu ngoặc tối ưu như thế nào?

Lưu điểm chia tối ưu trong choice[left][right] bên cạnh best[left][right]. Để in ra, nếu chỉ có một ma trận thì in tên của ma trận; nếu có nhiều ma trận liên tiếp thì in dấu ngoặc mở, phần trước choice[left][right], phần sau nó và dấu ngoặc đóng. Cách này cần thêm bộ nhớ O(n²).

def matrixChainOrder(dims):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

dims = [4, 10, 3, 12]

Đầu ra mong đợi

Matrix Chain Multiplication

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử mọi cách chia bằng đệ quy thuần túy

Đệ quy với bộ nhớ đệm

Điền vào bảng bằng cách kéo giãn chiều rộng

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự