TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN
KHOA KHOA HỌC MÁY TÍNH
-----------***-----------

THUẬT TOÁN
(Algorithms)

Nguyễn Thanh Cẩm


Nội Dung

C1

THUẬT TOÁN VÀ ĐỘ PHỨC TẠP

C2

CHIA ĐỂ TRỊ

C3

QUY HOẠCH ĐỘNG

C4

THUẬT TOÁN THAM LAM

C5

THUẬT TOÁN QUAY LUI

Nguyễn Thanh


QUY HOẠCH ĐỘNG
 Chia để trị là thiết kế thuật toán theo kiểu từ trên
xuống (top-down)
 Quy hoạch động là quá trình tiếp cận thuật toán
theo quá trình ngược lại, đó là thiết kế theo kiểu từ
dưới lên (bottom-up).
 Điểm khác cơ bản của quy hoạch động với phương
pháp chia để trị đó là:







các bài toán con không độc lập với nhau,
nghĩa là các bài toán con cùng có chung các bài toán con
nhỏ hơn.
Trong tình huống đó, phương pháp chia để trị sẽ tỏ ra không
hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con
chung đó.
Quy hoạch động sẽ giải một bài toán con một lần và lời giải
của các bài toán con sẽ được ghi nhận, nhằm thoát khỏi
việc giải lại các bài toán con mỗi khi ta cần lời giải của nó.

Nguyễn Thanh



QUY HOẠCH ĐỘNG
 Trong ngành khoa học máy tính, quy hoạch động là một
phương pháp giảm thời gian chạy của các thuật toán thể hiện
các tính chất của các bài toán con gối nhau (overlapping
subproblem) và cấu trúc con tối ưu (optimal substructure).
 Nhà toán học Richard Bellman đã phát minh phương pháp quy
hoạch động vào năm 1953.

Nguyễn Thanh


QUY HOẠCH ĐỘNG
2.1

Thuật toán quy hoạch động tổng quát

2.2

Một số thí dụ minh họa

2.2.1

Bài toán thực hiện dãy phép nhân ma trận

2.2.2

Bài toán tìm đường đi ngắn nhất thuật toán Floy


2.2.3

Bài toán dãy con lớn nhất

2.2.4

Bài toán dãy con chung dài nhất

Nguyễn Thanh


3.1 Thuật toán quy hoạch động tổng quát
 Để giải một bài toán bằng quy hoạch động, chúng
ta cần tiến hành những công việc sau:








Tìm nghiệm của các bài toán con (các trường hợp
riêng) đơn giản nhất.
Tìm ra các công thức (hoặc quy tắc) xây dựng
nghiệm của bài toán con thông qua nghiệm của các
bài toán con cỡ nhỏ hơn.
Tạo ra một bảng để lưu giữ các nghiệm của các bài
toán con. Sau đó tính nghiệm của các bài toán con
theo các công thức đã tìm ra và lưu vào bảng.

Từ bảng đã làm đầy, tìm cách xây dựng nghiệm của
bài toán đã cho.

Nguyễn Thanh


3.1 Thuật toán quy hoạch động tổng quát
 Việc phát triển giải thuật dựa trên quy hoạch động có thể chia
làm 3 giai đoạn:


Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn
có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước
nhỏ nhất có thể giải một cách trực tiếp. Bản thân bài toán xuất
phát có thể coi là bài toán con có kích thước lớn nhất trong họ các
bài toán con này.



Ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một
bảng. Việc làm này là cần thiết vì lời giải của các bài toán con
thường được sử dụng lại rất nhiều lần, và điều đó nâng cao hiệu
quả của giải thuật do không phải giải lặp lại cùng một bài toán
nhiều lần.



Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con kích
thước nhỏ hơn tìm cách xây dựng lời giải của bài toán kích thước
lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài

toán con có kích thước lớn nhất).

Nguyễn Thanh


3.1 Thuật toán quy hoạch động tổng quát
 Có hai tính chất quan trọng mà một bài toán tối ưu
cần phải thoả mãn để có thể áp dụng quy hoạch
động để giải nó là:


Cấu trúc con tối ưu: Để giải được bài toán đặt ra một cách
tối ưu, mỗi bài toán con cũng phải được giải một cách tối ưu.



Số lượng các bài toán con phải không quá lớn. Rất
nhiều các bài toán NP (xem [1] trang 234) – khó có thể giải
được nhờ quy hoạch động, nhưng việc làm này là không hiệu
quả do số lượng các bài toán con tăng theo hàm mũ. Một đòi
hỏi quan trọng đối với quy hoạch động là tổng số các bài
toán con cần giải là không quá lớn, cùng lắm phải bị chặn
bởi một đa thức của kích thước dữ liệu vào.

Nguyễn Thanh


QUY HOẠCH ĐỘNG
2.1


Thuật toán quy hoạch động tổng quát

2.2

Một số thí dụ minh họa

2.2.1

Bài toán thực hiện dãy phép nhân ma trận

2.2.2

Bài toán tìm đường đi ngắn nhất thuật toán Floy

2.2.3

Bài toán dãy con lớn nhất

2.2.4

Bài toán dãy con chung dài nhất

Nguyễn Thanh


3.2 Một số thí dụ minh họa

3.2.1

Bài toán thực hiện dãy phép nhân ma trận


3.2.2

Bài toán tìm đường đi ngắn nhất thuật toán Floy

3.2.3

Bài toán dãy con lớn nhất

3.2.4

Bài toán dãy con chung dài nhất

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Tích của ma trận A = (aik) kích thước p x q với ma trận B = (bkj)
kích thước q x r là ma trận C = (cij) kích thước p x r với các phần
tử của C được tính theo công thức: 
q

cij = ∑ aik bkj ,
k =1

1 <= i <= p,   1 <= j <= r.
 Thí dụ: A là ma trận kích thước 2×3, B là ma trận kích thước 3×4,
thì C là ma trận kích thước 2×4.

7 8 9 1 

1 2 3 
29 35 41 38

4 5 6 × 2 3 4 5 = 74 89 104 83

 6 7 8 9 



Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Chúng ta có thể sử dụng đoạn chương trình sau đây
để tính tích của hai ma trận A, B:
for (i =1; i <= p;i++)
      for (j =1 ; j <= r;j++)
     {   c [i, j] = 0
         for( k = 1 ;k<= q;k++)
c[i, j] = c[i, j] + a[i, k] *b[k, j];
}         
 Rõ ràng, đoạn chương trình trên đòi hỏi thực hiện tất
cả p.q.r phép nhân vô hướng để tính tích của hai ma
trận.

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Thí dụ: như ma trận ở trên thì:

 Phần tử dòng 1 cột 1 của ma trận C được tính như
sau:1×7 + 2×2 + 3×6 = 29 nên nó có 3 phép nhân
vô hướng.
 Phần tử dòng 1 cột 2 được tính: 1×8 + 2×3 + 3×7 =
35 nên cũng có 3 phép nhân vô hướng,…
 Suy ra số phép nhân vô hướng (phí tổn) của 2 ma trận
A và B là: 2×3×4 = 24 phép nhân.

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Bây giờ ta xét tích của 4 ma trận A, B, C, D với kích
trước lần lượt như sau:
A × B
×
C
×
D
(*)
[20×2] [2×30] [30×12] [12×8]
 Một điều nên lưu ý là, để thực hiện được tích của các
ma trận ở trên, đòi hỏi chúng phải tương thích với
nhau. Tức là số cột của A phải đúng bằng số dòng của
B, số cột của B phải đúng bằng số dòng của C,…

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận

 Do phép nhân ma trận không có tính chất giao hoán,
nhưng lại có tính chất kết hợp nên tích của 4 ma trận
trên có thể được tính bằng nhiều cách như sau:
 A(B(CD))
30×12×8 + 2×30×8 + 20×2×8 = 3.680





(AB)(CD)
A((BC)D)
((AB)C)D
(A(BC))D

20×2×30 + 30×12×8 + 20×30×8 =
2×30×12 + 2×12×8 + 20×2×8 =
20×2×30 + 20×30×12 + 20×12×8 =
2×30×12 + 20×2×12 + 20×12×8 =

Nguyễn Thanh

8.880
1.232
10.320
3.120


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Từ kết quả trên ta thấy, trình tự thực hiện có ảnh

hưởng lớn tới phí tổn để thực hiện dãy phép nhân của
các ma trận. Bài toán đặt ra là tính số phí tổn ít nhất
có thể được, khi thực hiện dãy phép nhân của n ma
trận.
 M = M1*M2*…Mn
 Với:
 M1 là ma trận có kích thước a1×a2
 M2 là ma trận có kích thước a2×a3
 ….
 Mn là ma trận có kích thước an×an+1
 Suy ra a[1..n+1] là vector kích thước của các ma trận.
Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Áp dụng phương pháp quy hoạch động chúng ta sẽ giải quyết bài
toán theo kiểu “bottom-up”:
 Gọi F[i, j] là số phép nhân tối thiểu cần thực hiện để nhân đoạn
ma trận liên tiếp: Mi*Mi+1*…*Mj (1 <= i <= j <= n).
 Khi đó F[i, i] = 0 với mọi i.
 Để tính Mi*Mi+1*…*Mj ta có thể có nhiều cách kết hợp: Mi*Mi+1*…
*Mj = (Mi*Mi+1*…*Mk)*(Mk+1*…*Mj-1*Mj) với i<= k kết hợp (phụ thuộc vào cách chọn vị trí k), chi phí tối thiểu phải
thực hiện bằng:
 Chi phí thực hiện phép nhân: Mi*Mi+1*…*Mk = F[i, k]
 Cộng với chi phí thực hiện phép nhân: Mk+1*…*Mj-1*Mj = F[k+1, j]

Nguyễn Thanh

3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Cộng với chi phí thực hiện phép nhân hai ma trận cuối
cùng: ma trận tạo thành từ phép nhân Mi*Mi+1*…*Mk
có kích thước ai×ak+1, và ma trận tạo thành từ phép
nhân Mk+1*…*Mj-1*Mj có kích thước ak+1×aj+1, vậy chi
phí này là : ai×ak+1×aj+1.
 Từ đó suy ra: do có nhiều cách kết hợp, mà ta cần
chọn cách kết hợp để có chi phí ít nhất nên ta sẽ cực
tiểu hóa F[i, j] theo công thức:
 F[i, j] = min(F[i, k] + F[k+1,j] + ai*ak+1*aj+1) mọi i<= k

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Tính bảng phương án:
 Bảng phương án F là bảng hai chiều, nhìn vào công thức (3.1) ta
thấy để tính được F[i, j] khi ta đã biết F[i, k] và F[k+1, j] tức là
ban đầu ta điền cơ sở quy hoạch động vào đường chéo chính của
bảng (F[i, i] = 0) từ đó tính các giá trị thuộc đường chéo nằm
phía trên (tính các F[i, i+1]), rồi lại tính các giá trị nằm phía trên
nữa (F[i, i+2])… dến khi tính được F[1, n] thì dừng lại.

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Tìm cách kết hợp tối ưu:
 Tại mỗi bước tính F[i, j], ta ghi nhận lại điểm k mà

cách tính (Mi*Mi+1*…*Mk)*(Mk+1*…*Mj-1*Mj) cho số
phép nhân vô hướng nhỏ nhất, chẳng hạn ta đặt F[i, j]
= k. Khi đó muốn in ra phép kết hợp tối ưu để nhân
đoạn Mi*Mi+1*…*Mk*Mk+1*…*Mj-1*Mj ta sẽ in ra
cách kết hợp tối ưu để nhân đoạn Mi*Mi+1*…*Mk và
cách kết hợp tối ưu để nhân đoạn Mk+1*…*Mj-1*Mj
(có kèm theo dấu mở ngoặc) đồng thời viết thêm dấu
“*” vào giữa hai biểu thức đó.

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận


















Ta có hàm:
int Minmult(int n, const int a[], index P[][]) //a[] kích thước của các ma trận
{
//P[][] là ma trận lưu vị trí kết hơp k tối ưu
index i, j, k, d;
int F[1..n][1..n];
for (i = 1; i <= n; i++)
F[i][i] = 0;
for (d = 1; d <= n-1; d++) //d là đường chéo
for (i = 1; i <= n-d; i++)
{
j = i +d;
for (k = i; kF[i][j] = min(F[i][k] + F[k+1][j] + ai*ak+1*aj+1);
P[i][j] = k sao cho F[i][j] dat min
}
return M[1][n];
}

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Thí dụ 2: Tìm cách tính tối ưu cho tích của bốn ma trận cho trong
(*).
 Ta có a = (20, 2, 30, 12, 8).
 Với d = 1, F[1,2] = 1200, F[2,3] = 720 và F[3,4] = 2880.
 Tiếp theo, với d = 2 ta thu được
F[1,3] = min(F[1,1] + F[2,3] + 20 x 2 x 12, F[1,2] + F[3,3] + 20 x

30 x 12)
          = min(1200, 8400) = 1200
F[2,4] = min(F[2,2] + F[3,4] + 2 x 30 x 8, F[2,3] + F[4,4] + 2 x 12 x
8)
          = min(3360, 912) = 912
 Cuối cùng với d = 3 ta có
F[1,4] =  min(F[1,1] + F[2,4] + 20 x 2 x 8),          {k = 1}
                     F[1,2] + F[3,4] + 20 x 30 x 8,     {k = 2}
                    F[1,3] + F[4,4] + 20 x 12 x 8,        {k = 3}
        = min(1232, 8880, 3120) = 1232.
Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Giá trị F được cho trong bảng dưới đây
 Bảng 3.1 Bảng giá trị F

i=1
2
3
4

j=1

2

3

4

0

1200

1200

1232

0

720

912

d=3

0

2880

d=2

0

d=1
d=0

Nguyễn Thanh

3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Để tìm lời giải tối ưu, ta sử dụng bảng P[i][j] ghi nhận
cách đặt dấu ngoặc tách đầu tiên cho giá trị F[i][j].
Cùng với việc tính các giá trị F[i][j], ta sẽ tính P[i][j]
theo quy tắc:
d = 1:
1< d < n:

F[i][i+1] = ai×ak+1×aj+1
P[i][i+1] = i+1
F[i][i+d] = min(F[i][k] + F[k+1][i+d] + aiakai+d)
P[i][i+d] = k

Nguyễn Thanh


3.2.1 Bài toán thực hiện dãy phép nhân ma trận
 Thí dụ 3: Các giá trị của P[i, j] theo (*) được cho
trong bảng dưới đây:
 Bảng 3.2 Các giá trị của P[i, j]

 

j=1

2

3

4

 

i=1

1

2

1

1

 

2

 

2

3

2

d =3

 3

 

 

3

4

d =2

4

 

 

 

4

d =1

 

 

 

 

 

d =0

Nguyễn Thanh