Tin học: STGT giải thuật

13.9.2004
Ch. 1: Dynamic Programming
1
Dynamic Programming
13.9.2004
Ch. 1: Dynamic Programming
2
Giới thiệu
Dynamic programming
giải bài toán bằng cách kết hợp các lời giải của các bài toán con.
(ở đây "programming" không có nghĩa là lập trình).
So sánh dynamic programming và "chia-và-trị" (divide-and-conquer)
Giải thuật chia-và-trị
chia bài toán thành các bài toán con độc lập ,
giải chúng bằng đệ quy,
kết hợp chúng để có lời giải cho bài toán ban đầu.
Giải thuật dynamic programming
các bài toán con không độc lập với nhau: chúng có chung các bài toán con nhỏ hơn.
giải mỗi bài toán con chỉ một lần, và ghi nhớ lời giải đó trong một bảng để truy cập khi cần đến.
13.9.2004
Ch. 1: Dynamic Programming
3
Bài toán tối ưu
Bài toán tối ưu
có thể có nhiều lời giải
mỗi lời giải có một trị
Tìm lời giải có trị tối ưu (cực tiểu hay cực đại).
13.9.2004
Ch. 1: Dynamic Programming
4
Nguyên tắc của dynamic programming
Một giải thuật dynamic programming được xây dựng qua bốn bước:
1. Xác định cấu trúc của một lời giải tối ưu.
2. Định nghĩa đệ quy cho giá trị của một lời giải tối ưu.
3. Tính giá trị của một lời giải tối ưu từ dưới lên ("bottom-up").
4. Xây dựng lời giải tối ưu từ các thông tin đã tính.

13.9.2004
Ch. 1: Dynamic Programming
5
Nhân một chuỗi ma trận
Cho một chuỗi ma trận ?A1, A2,..., An?.
Xác định tích A1A2 ??? An dựa trên giải thuật xác định tích của hai ma trận.
Biểu diễn cách tính tích của một chuỗi ma trận bằng cách "đặt giữa ngoặc" (pa`renthesize) các cặp ma trận sẽ được nhân với nhau.
Một tích của một chuỗi ma trận là fully parenthesized nếu nó là
một ma trận hoặc là
tích của hai tích của chuỗi ma trận fully parenthesized khác, và được đặt giữa ngoặc.
Ví dụ: một vài tích của chuỗi ma trận được fully parenthesized
A
(AB)
((AB)C).
13.9.2004
Ch. 1: Dynamic Programming
6
Chuỗi ma trận fully parenthesized
Ví dụ: Cho một chuỗi ma trận ?A1 , A2 , A3 , A4?. Tích A1A2A3A4 có thể được fully parenthesized theo đúng 5 cách khác nhau:





(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
13.9.2004
Ch. 1: Dynamic Programming
7
Nhân hai ma trận
Tích của hai ma trận A và B với
A có chiều là p ? q
B có chiều là q ? r
là một ma trận C có chiều là p ? r.








Thời gian để tính C tỷ lệ với số phép nhân vô hướng thực thi trong dòng 7, tức là p ? q ? r .
MATRIX-MULTIPLY(A, B)
1 if columns[A] ? rows[B]
2 then error "các chiều không tương thích"
3 else for i ? 1 to rows[A]
4 do for j ? 1 to columns[B]
5 do C[i, j] ? 0
6 for k ? 1 to columns[A]
7 do C[i, j] ? C[i, j] + A[i, k]?B[k, j]
8 return C
13.9.2004
Ch. 1: Dynamic Programming
8
Phí tổn để nhân một chuỗi ma trận
Nhận xét: Phí tổn nhân một chuỗi ma trận tùy thuộc vào cách đặt giữa ngoặc (parenthesization).
Ví dụ: Cho chuỗi ma trận ?A1 , A2 , A3? trong đó các chiều (dimension) của các ma trận là 10 ? 100, 100 ? 5, và 5 ? 50
Có đúng 2 cách để đóng ngoặc hoàn toàn tích A1A2A3 :
Cách 1: ((A1A2)A3)
Tính A1A2 cần 10 ? 100 ? 5 = 5000 phép nhân vô hướng
Kế đó nhân A1A2 với A3 cần 10 ? 5 ? 50 = 2500 phép nhân vô hướng
Tổng cộng: 7500 phép nhân vô hướng
Cách 2: (A1(A2A3))
Tính A2A3 cần 100 ? 5 ? 50 = 25000 phép nhân vô hướng
Kế đó nhân A1 với A2A3 cần 10 ? 100 ? 50 = 50000 phép nhân vô hướng
Tổng cộng: 75000 phép nhân vô hướng.
13.9.2004
Ch. 1: Dynamic Programming
9
Bài toán nhân chuỗi ma trận
Cho chuỗi ma trận ?A1, A2,..., An? gồm n ma trận, trong đó chiều của Ai là pi?1 ? pi , với i = 1, 2,., n.
Bài toán: Xác định một đóng ngoặc hoàn toàn cho tích A1A2???An sao cho số phép nhân vô hướng là tối thiểu.
Giải bài toán trên bằng cách vét cạn?
13.9.2004
Ch. 1: Dynamic Programming
10
Đếm số cách đóng ngoặc
Cho một chuỗi gồm n ma trận ?A1 , A2 , A3 ,..., An?.
Nhận xét: tạo ra một cách đóng ngoặc bằng cách tách (split) giữa Ak và Ak+1 , với k = 1, 2,..., n - 1, tạo ra hai chuỗi con A1A2 ??? Ak và Ak+1 ??? An , sau đó đóng ngoặc mỗi chuỗi con.
Gọi P(n) là số các cách đóng ngoặc cho một chuỗi n ma trận
nếu n = 1 thì chỉ có một cách đóng ngoặc (không cần dấu ngoặc tường minh). Vậy P(1) = 1.
nếu n ? 2 thì từ nhận xét trên ta có


Từ đó chứng minh được:

Vậy dùng phương pháp vét cạn duyệt qua tất cả các cách đóng ngoặc để tìm một đóng ngoặc tối ưu cần thời gian chạy lũy thừa.
13.9.2004
Ch. 1: Dynamic Programming
11
Bước 1: Cấu trúc của một đóng ngoặc tối ưu
Bước 1 của phương pháp dynamic programming là
xác định tính chất cấu trúc con tối ưu
dựa vào đó xây dựng lời giải tối ưu cho bài toán từ các lời giải tối ưu cho các bài toán con.
Ở đây:
Gọi Ai.. j là ma trận có được từ tích Ai Ai+1 ??? Aj .
Nhận xét: Một đóng ngoặc tối ưu bất kỳ của tích Ai Ai+1???Aj tách nó giữa Ak và Ak+1, với k nào đó thõa i ? k ? j :
(Ai Ai+1 ??? Ak)(Ak+1 ??? Aj)
Nghĩa là đầu tiên ta tính các ma trận Ai..k và Ak+1..j , sau đó ta nhân chúng với nhau để có tích cuối cùng Ai..j . Do đó phí tổn để tính tích từ đóng ngoặc tối ưu là phí tổn để tính Ai..k , cộng phí tổn để tính Ak+1..j , cộng phí tổn để nhân chúng với nhau.
13.9.2004
Ch. 1: Dynamic Programming
12
Bước 1: Cấu trúc của một đóng ngoặc tối ưu (tiếp)
Cấu trúc con tối ưu
Đóng ngoặc của chuỗi con "tiền tố" Ai Ai+1 ??? Ak có được từ đóng ngoặc tối ưu của Ai Ai+1 ??? Aj phải là một đóng ngoặc tối ưu của Ai Ai+1 ??? Ak . (Chứng minh bằng phản chứng).
Tương tự, đóng ngoặc của chuỗi con còn lại Ak+1 Ak+2 ??? Aj có được từ đóng ngoặc tối ưu của Ai Ai+1 ??? Aj phải là một đóng ngoặc tối ưu của Ak+1 Ak+2 ??? Aj .
Để cho gọn, sẽ nói "phí tổn của một đóng ngoặc" thay vì nói "phí tổn để tính tích từ một đóng ngoặc".
Xây dựng lời giải tối ưu
Chia bài toán thành hai bài toán con
Tìm lời giải tối ưu cho mỗi bài toán con
Kết hợp các lời giải tìm được ở trên.
Cần tìm vị trí thích hợp (trị của k) để tách chuỗi ma trận Ai Ai+1 ??? Aj !
13.9.2004
Ch. 1: Dynamic Programming
13
Bước 2: Giải đệ quy
Bước 2 của phương pháp dynamic programming là
định nghĩa đệ quy phí tổn (trị) của một lời giải tối ưu tùy theo các lời giải tối ưu của các bài toán con.
Bài toán con ở đây: Xác định phí tổn tối thiểu cho một đóng ngoặc của chuỗi ma trận Ai Ai+1??? Aj với 1 ? i ? j ? n.
Định nghĩa m[i, j] là số phép nhân vô hướng tối thiểu để tính ma trận Ai..j . Phân biệt hai trường hợp:
nếu i = j thì Ai Ai+1???Aj = Ai . Vậy, với i = 1,..., n,
m[i, i] = 0.
nếu i < j thì từ bước 1 ta có
m[i, j] = m[i, k] + m[k + 1, j] + pi?1 pk pj .
Nhưng trị của k?
13.9.2004
Ch. 1: Dynamic Programming
14
Bước 2: Giải đệ quy (tiếp)
Trả lời:
Bằng cách duyệt qua tất cả các trị của k, i ? k ? j - 1, ta tìm được
m[i, j] = mini ? k ? j ?1 {m[i, k] + m[k + 1, j] + pi?1 pk pj}.

Để ghi lại cách xây dựng lời giải tối ưu ta định nghĩa s[i, j] là trị của k xác định nơi tách chuỗi Ai Ai+1 ??? Aj để có một đóng ngoặc tối ưu. Nghĩa là s[i, j] là một trị k sao cho
m[i, j] = m[i, k] + m[k + 1, j] + pi?1 pk pj .
13.9.2004
Ch. 1: Dynamic Programming
15
Bước 3: Tính các chi phí tối ưu
Bước 3 của phương pháp dynamic programming là tính chi phí tối ưu bằng một phương pháp từ dưới lên (bottom-up) và dùng bảng.
Nhận xét:
Có thể viết được ngay một giải thuật đệ quy (dựa trên hàm đệ quy đã tìm được) để tính phí tổn tối ưu m[1, n] cho tính tích A1A2 ??? An . Nhưng sau này chúng ta sẽ thấy là giải thuật này chạy trong thời gian lũy thừa.
13.9.2004
Ch. 1: Dynamic Programming
16
Bước 3: Tính các chi phí tối ưu (tiếp)
Ma trận Ai có chiều là pi?1 ? pi , với i = 1, 2,..., n .
Input là một chuỗi p = < p0 , p1,..., pn >
Giải thuật trả về hai bảng m[1..n, 1..n] và s[1..n, 1..n].
MATRIX-CHAIN-ORDER(p)
1 n ? length[p] ? 1
2 for i ? 1 to n
3 do m[i, i] ? 0
4 for l ? 2 to n
5 do for i ? 1 to n ? l + 1
6 do j ? i + l ? 1
7 m[i, j] ? ?
8 for k ? i to j ? 1
9 do q ? m[i, k] + m[k + 1, j] + pi?1 pk pj
10 if q < m[i, j]
11 then m[i, j] ? q
12 s[i, j] ? k
13 return m and s
13.9.2004
Ch. 1: Dynamic Programming
17
Phân tích MATRIX-CHAIN-ORDER
Thời gian chạy của MATRIX-CHAIN-ORDER là O(n3).
Giải thuật cần bộ nhớ ?(n2) cho các bảng m và s.
13.9.2004
Ch. 1: Dynamic Programming
18
Chạy MATRIX-CHAIN-ORDER lên một ví dụ





Các bảng m và s tính được:
11,875
9,375
15,125
15,750
0
7,875
7,125
4,375
10,500
0
2,625
2,500
750
5,375
0
1,000
0
3,500
5,000
0
0
3
3
3
1
1
3
3
3
2
3
3
3
4
5
5
m
s
A1 A2 A3 A4 A5 A6
j
i
j
i
ma trận chiều
A1 30 ? 35
A2 35 ? 15
A3 15 ? 5
A4 5 ? 10
A5 10 ? 20
A6 20 ? 25
1
1
1
6
6
2
6
5
13.9.2004
Ch. 1: Dynamic Programming
19
Bước 4: Xây dựng một lời giải tối ưu
Bảng s[1..n, 1..n] trữ một cách đóng ngoặc tối ưu do MATRIX-CHAIN-ORDER tìm ra.
Thủ tục sau, MATRIX-CHAIN-MULTIPLY, trả về tích của chuỗi ma trận Ai..j khi cho A = ?A1 , A2 , A3 ,..., An?, bảng s, và các chỉ số i và j.








Gọi MATRIX-CHAIN-MULTIPLY(A, s, 1, n) để tính tích của chuỗi ma trận A.
MATRIX-CHAIN-MULTIPLY(A, s, i, j)
1 if j > i
2 then X ? MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j])
3 Y ? MATRIX-CHAIN-MULTIPLY(A, s, s[i, j] + 1, j)
4 return MATRIX-MULTIPLY(X, Y)
5 else return Ai
13.9.2004
Ch. 1: Dynamic Programming
20
Các yếu tố để áp dụng dynamic programming
Hai yếu tố để áp dụng được phương pháp dynamic programming vào một bài toán tối ưu
"Cấu trúc con tối ưu"
"Các bài toán con trùng nhau".
13.9.2004
Ch. 1: Dynamic Programming
21
Một lời giải không tối ưu
Giải thuật không ghi nhớ lời giải của các bài toán con.
RECURSIVE-MATRIX-CHAIN(p, i, j)
1 if i = j
2 then return 0
3 m[i, j] ? ?
4 for k ? i to j ? 1
5 do q ? RECURSIVE-MATRIX-CHAIN(p, i, k)
+ RECURSIVE-MATRIX-CHAIN(p, k + 1, j) + pi?1 pk pj
6 if q < m[i, j]
7 then m[i, j] ? q
8 return m[i, j]
13.9.2004
Ch. 1: Dynamic Programming
22
Phân tích RECURSIVE-MATRIX-CHAIN
Gọi T(n) là thời gian chạy của RECURSIVE-MATRIX-CHAIN(p, 1, n), thì T(n) phải thỏa (xem code)



Từ đó chứng minh được: T(n) = ?(2n).
Tại sao RECURSIVE-MATRIX-CHAIN chạy trong thời gian ?(2n) còn MATRIX-CHAIN-ORDER chỉ cần thời gian đa thức? Đó là vì
RECURSIVE-MATRIX-CHAIN là giải thuật đệ quy từ trên xuống (top-down) và không tận dụng được tính chất "các bài toán con trùng nhau" (overlapping subproblems).
MATRIX-CHAIN-ORDER là giải thuật dynamic-programming từ dưới lên (bottom-up), tận dụng được tính chất "các bài toán con trùng nhau".
13.9.2004
Ch. 1: Dynamic Programming
23
Cây đệ quy
Cây đệ quy cho RECURSIVE-MATRIX-CHAIN(p, 1, 4)
1..4
2..2
1..1
3..4
2..3
4..4
2..2
3..3
1..2
4..4
1..1
2..3
3..3
1..1
2..4
1..2
3..4
1..3
4..4
4..4
3..3
2..2
3..3
1..1
2..2
3..3
2..2
13.9.2004
Ch. 1: Dynamic Programming
24
Một biến dạng của dynamic programming: memoization
Memoization là phương pháp tận dụng tính chất "các bài toán con trùng nhau" để cải tiến giải thuật đệ quy từ trên xuống bằng cách
sử dụng một bảng chung mà mỗi triệu gọi của giải thuật đệ quy có thể truy cập để
ghi kết quả sau khi giải một bài toán con mới
đọc kết quả của một bài toán con đã được giải rồi.
13.9.2004
Ch. 1: Dynamic Programming
25
Memoize giải thuật RECURSIVE-MATRIX-CHAIN
Memoize giải thuật RECURSIVE-MATRIX-CHAIN bằng cách sử dụng bảng m[1..n, 1..n].
MEMOIZED-MATRIX-CHAIN có input là một chuỗi p = < p0 , p1,..., pn >
MEMOIZED-MATRIX-CHAIN(p)
1 n ? length[p] ? 1
2 for i ? 1 to n
3 do for j ? i to n
4 do m[i, j] ? ?
5 return LOOKUP-CHAIN(p, 1, n)
13.9.2004
Ch. 1: Dynamic Programming
26
Memoization
LOOKUP-CHAIN bao giờ cũng trả về m[i, j]. Nhưng nó chỉ tính m[i, j] khi nào đó là lần gọi đầu tiên với các tham số i và j.
LOOKUP-CHAIN(p, i, j)
1 if m[i, j] < ?
2 then return m[i, j]
3 if i = j
4 then m[i, j] ? 0
5 else for k ? i to j ? 1
6 do q ? LOOKUP-CHAIN(p, i, k)
+ LOOKUP-CHAIN(p, k + 1, j) + pi?1 pk pj
7 if q < m[i, j]
8 then m[i, j] ? q
9 return m[i, j]
13.9.2004
Ch. 1: Dynamic Programming
27
Phân tích MEMOIZED-MATRIX-CHAIN
MEMOIZED-MATRIX-CHAIN chạy trong thời gian O(n3).
Nhận xét:
MEMOIZED-MATRIX-CHAIN tận dụng được tính chất "các bài toán con trùng nhau",
còn RECURSIVE-MATRIX-CHAIN chạy trong thời gian ?(2n) vì nó luôn luôn giải các bài toán con mà không để ý xem bài toán con đã được giải rồi hay chưa.
13.9.2004
Ch. 1: Dynamic Programming
28
Phân tam giác
Đa giác
Đa giác đơn ("simple")
Đa giác lồi
Phân tam giác (triangulation)
13.9.2004
Ch. 1: Dynamic Programming
29
Các khái niệm cơ bản
Cạnh, đỉnh, biên của một đa giác
Ta biểu diễn một đa giác lồi P bằng danh sách các đỉnh theo thứ tự ngược chiều kim đồng hồ: P = ?v0 , v1,..., vn?1?
Cung ("chord") của một đa giác
Một phân tam giác của một đa giác là một tập hợp các cung của đa giác chia đa giác thành các tam giác rời nhau.
13.9.2004
Ch. 1: Dynamic Programming
30
Bài toán phân tam giác tối ưu
Cho:
Một đa giác lồi P = ?v0 , v1 ,..., vn?1 ?
Một hàm trọng số w ("weight function") được định nghĩa trên các tam giác tạo bởi cạnh và cung của P.
Bài toán: Tìm một phân tam giác cho P sao cho tổng các trọng số của các tam giác trong phân tam giác này là nhỏ nhất.
Ví dụ một hàm trọng số:
w(một tam giác) = tổng các chiều dài của các cạnh của tam giác.
13.9.2004
Ch. 1: Dynamic Programming
31
Parse tree của một biễu thức
Biễu thức (expression)
Ví dụ một biễu thức: tích của một chuỗi ma trận đã được đóng ngoặc hoàn toàn ((A1(A2A3))(A4(A5 A6)))
Parse tree.
Ví dụ: parse tree của biễu thức ((A1(A2A3))(A4(A5 A6))) là
A1
A2
A3
A4
A5
A6
13.9.2004
Ch. 1: Dynamic Programming
32
Parse tree của một biễu thức

Định nghĩa: parse tree của một biễu thức là một cây mà
Lá: có nhản là một trong các nguyên tử ("atomic element", ví dụ: A1) tạo nên biễu thức.
Nếu gốc của một cây con của parse tree có cây con bên trái tượng trưng biễu thức El và có cây con bên phải tượng trưng biễu thức Er , thì cây con này tượng trưng biễu thức (ElEr).

13.9.2004
Ch. 1: Dynamic Programming
33
Từ phân tam giác sinh ra parse tree
Ví dụ: Parse tree cho đa giác P = ?v0 , v1,., v6? sau.
13.9.2004
Ch. 1: Dynamic Programming
34
Từ parse tree sinh ra phân tam giác
Cho parse tree biểu diễn bởi (((A1(A2A3))A4)(A5 A6)). Phân tam giác tương ứng:
A1
A2
A3
A4
A5
A6
v0
v1
v2
v3
v4
v6
v5
A1
A2
A3
A5
A6
A4
13.9.2004
Ch. 1: Dynamic Programming
35
Tương ứng giữa parse tree và phân chia tam giác
Tương ứng giữa parse trees và các phân chia tam giác là tương ứng một-đối-một:
Mỗi phân tam giác của một đa giác lồi có n + 1 cạnh tương ứng với parse tree cho một biễu thức gồm n nguyên tử.
Mỗi parse tree có n lá tương ứng với phân tam giác của một đa giác lồi có n + 1 cạnh.
13.9.2004
Ch. 1: Dynamic Programming
36
Tương ứng giữa đóng ngoặc hoàn toàn của tích của n ma trận và phân chia tam giác
Đóng ngoặc hoàn toàn của tích của n ma trận tương ứng với phân tam giác của một đa giác lồi có n + 1 đỉnh.
Mỗi ma trận Ai trong tích A1A2 ??? An tương ứng với cạnh vi-1vi của đa giác lồi.
Cung vivj , với i < j, tương ứng với ma trận Ai +1.. j .
13.9.2004
Ch. 1: Dynamic Programming
37
Nhân chuỗi ma trận và phân tam giác tối ưu
Bài toán nhân chuỗi ma trận là một trường hợp đặc biệt của bài toán phân tam giác tối ưu.
Tính tích A1A2 ??? An thông qua một bài toán phân tam giác tối ưu:
Định nghĩa một đa giác lồi có n + 1 đỉnh P = ?v0 , v1,., vn?
Nếu ma trận Ai có dimension pi?1 ? pi , với i = 1, 2,..., n, định nghĩa hàm trọng số w cho phân tam giác là
w(?vivjvk ) = pi pj pk
Một phân tam giác tối ưu của P cho ta parse tree của một đóng ngoặc tối ưu của A1A2 ??? An .
13.9.2004
Ch. 1: Dynamic Programming
38
Nhân chuỗi ma trận và phân tam giác tối ưu (tiếp)
Ngược lại là không đúng: bài toán phân tam giác tối ưu không là trường hợp đặc biệt của bài toán nhân chuỗi ma trận.
Mặc dù vậy, có thể chỉnh lại MATRIX-CHAIN-ORDER để giải bài toán phân tam giác tối ưu cho một đa giác có n + 1 đỉnh như sau
Thay chuỗi p = < p0 , p1,..., pn > của các chiều của ma trận bằng chuỗi ?v0 , v1 ,..., vn ? của các đỉnh.
Thay các truy cập đến p bằng các truy cập đến v và thay dòng 9 bởi
9 do q ? m[i, k] + m[k + 1, j] + w(Dvi?1 vk vj )
Khi giải thuật thực thi xong, m[1, n] chứa trọng số của một phân tam giác tối ưu.
Phần sau cho thấy tại sao làm được như vậy.
13.9.2004
Ch. 1: Dynamic Programming
39
Bước 1: Cấu trúc con của một phân tam giác tối ưu
Cho T là một phân tam giác tối ưu của một đa giác P = ?v0 , v1,., vn? , T chứa tam giác Dv0vkvn với k nào đó, 1 ? k ? n ? 1.






Trọng số của T là tổng của các trọng số của tam giác Dv0vkvn và các tam giác chứa trong phân tam giác của hai đa giác con ?v0, v1,., vk? và ?vk , vk+1,., vn?. Một đa giác con suy thoái có trọng số là 0.
Do đó các phân tam giác (xác định bởi T) của các đa giác con trên cũng phải là tối ưu. (Chứng minh bằng phản chứng.)
13.9.2004
Ch. 1: Dynamic Programming
40
Bước 2: Lời giải đệ quy
Định nghĩa t[i, j] là trọng số của một phân tam giác tối ưu của đa giác ?vi?1,vi ,., vj?. Như vậy trọng số của một phân tam giác tối ưu của đa giác P là t[1, n].
Xác định t[?,?]
nếu đa giác chỉ có 2 đỉnh (đa giác suy thoái)
t[i, i] = 0 cho i = 1,..., n
nếu đa giác có ít nhất 3 đỉnh, i < j
t[i, j] = t[i, k] + t[k + 1, j] + w(?vi?1vkvj) .
Nhưng trị của k?
13.9.2004
Ch. 1: Dynamic Programming
41
Bước 2: Lời giải đệ quy (tiếp)
Bằng cách duyệt qua tất cả các trị của k, i ? k ? j - 1, ta nhận được
t[i, i] = 0, i = 1,..., n
t[i, j] = min i ? k ? j?1 {t[i, k] + t[k + 1, j] + w(?vi?1vkvj)} nếu i < j .
Hàm đệ quy này tương tự hàm đệ quy m[?,?] cho số phép nhân vô hướng tối thiểu để tính Ai Ai+1??? Aj . Do đó có thể chỉnh lại thủ tục MATRIX-CHAIN-ORDER (như đã nói) để tính trọng số của một phân tam giác tối ưu.
Vậy thủ tục phân tam giác tối ưu chạy trong thời gian O(n3) và cần bộ nhớ ?(n2).