Chương 3
Chiến lược giảm-để-trị (Decrease-and-conquer)
1
Nội dung
2
1. Chiến lược giảm-để-trị 2. Sắp thứ tự bằng phương pháp chèn 3. Các giải thuật duyệt đồ thị 4. Sắp xếp tôpô 5. Giải thuật sinh các hoán vị từ một tập
1. Chiến lược thiết kế giải thuật giảm-để-trị (Decrease-and-conquer)
Kỹ thuật thiết kế giải thuật giảm-để-trị lợi dụng mối liên hệ giữa lời giải cho một thể hiện của một bài toán và lời giải cho một thể hiện nhỏ hơn của cùng một bài toán.
Có ba biến thể của chiến lược này.
Giảm bởi một hằng số (decrease by a constant) Giảm bởi một hệ số (decrease by a factor) Giảm kích thước của biến (variable size decrease)
Sắp thứ tự bằng phương pháp chèn (insertion sort) là một thí dụ điển hình của chiến lược giảm-để-trị.
3
Chiến lược thiết kế giải thuật giảm-để-trị (tt.)
Giải thuật tìm ước số chung lớn nhất của 2 số theo công thức gcd(m,n) = gcd(n, m mod n) cũng là thí dụ của chiến lược giảm-để-trị theo lối giảm kích thước của biến.
Thí dụ: m = 60 và n = 24
1) m = 60 và n = 24
2) m = 24 và n = 12
3) m = 12 và n = 0
Vậy 12 là ước số chung lớn nhất
Algorithm Euclid(m,n) /* m,n : two nonnegative integers m and n */ while n<>0 do r := m mod n; m:= n; n:= r endwhile return m;
4
Chiến lược thiết kế giải thuật giảm-để-trị (tt.)
Tại mỗi bước của giải thuật duyệt đồ thị theo chiều sâu trước (DFS) hay duyệt theo bề rộng trước (BFS), giải thuật đánh dấu đỉnh đã được viếng và tiến sang xét các đỉnh kế cận của đỉnh đó.
Hai giải thuật duyệt đồ thị này đã áp dụng kỹ
thuật giảm-bớt-một (decrease-by-one), một trong 3 dạng chính của chiến lược Giảm-để-trị.
5
2. Sắp thứ tự bằng phương pháp chèn
ngưở :
ả ụ ủ ỹ ể ị ệ
ộ ứ ứ ự ộ
s r ng bài toán nh h n: s p th t ệ ự
ượ ả ỏ ơ ắ ề ấ c th c hi n. V n đ là ph i ứ ự a[0..n2].
a[n1] vào m ng con đã có th t ệ ề
Ý t • Xét m t ng d ng c a k thu t “gi m đ tr ” vào vi c ậ ầ ủ ỹ ả ắ m t m ng a[0..n1]. Theo tinh th n c a k s p th t ứ ự ộ ả ử ằ ậ m t thu t, ta gi ả chèn ả m ng a[0..n2] đã đ ầ ử ph n t • Có hai cách đ th c hi n đi u này. ể ự ệ
ứ ự ừ
ả
ộ
trái sang ph i
t ớ ơ
đ u tiên l n h n hay b ng v i
ầ ử ầ ầ ử
a[n1] vào
bên trái ph n t
ằ ớ ầ ử
ph i sang trái cho
ệ ấ
ế
ầ ử
ầ ử ầ a[n1] và chèn ph n t
ứ ự ừ ả t ằ ỏ ơ đ u tiên nh h n hay b ng v i bên ph iả ph n t ầ ử a[n1] vào
ớ ầ ử
ả M t là ta duy t m ng con đã có th t ế ấ cho đ n khi tìm th y ph n t ầ ử a[n1] và chèn ph n t ph n t này. ả Hai là ta duy t m ng con đã có th t đ n khi tìm th y ph n t ph n t này.
6
2. Sắp thứ tự bằng phương pháp chèn (tt.)
ườ ượ ứ Cách th hai th ng đ ọ c ch n:
a[0] ≤ … ≤ a[j] < a[j+1] ≤ … ≤ a[i1] | a[i] … a[n1]
(cid:0) 205 (cid:0) (cid:0)
(cid:0)
7
390 205 182 45 235 390 182 45 235 182 205 390 45 235 45 182 205 390 235 45 182 205 235 390
Giải thuật sắp thứ tự bằng phương pháp chèn
procedure insertion; var i; j; v:integer; begin
for i:=2 to N do begin
v:=a[i]; j:= i; while a[j1]> v do begin
a[j] := a[j1]; // pull down j:= j1 end;
a[j]:=v;
end;
8
end;
Những lưư ý về giải thuật insertion sort
ộ ị 1. Chúng ta dùng m t tr khóa “ i ạ
ỏ ơ ” (sentinel) t nh nh t trong
ầ c m canh ầ ử ỏ ấ a[0], làm cho nó nh h n ph n t m ng.ả
ậ ượ ự i thu t đ
ả
ự ặ
ầ ả ủ ặ c th c thi N1 l n. 2. Vòng l p ngoài c a gi ợ x u nh t ứ ự ả ấ x y ra khi m ng đã có th t ấ ng h p ớ ượ ượ c th c thi v i c. Khi đó, vòng l p trong đ ố ầ ườ Tr ả đ o ng ổ t ng s l n sau đây:
(N1) + (N2) + ... + 1 =N(N1)/2 =O(N2) ể ố ố ướ c chuy n = N(N1)/2 S so sánh = N(N1)/2 S b
ừ 3. Trung bình có kho ng ch ng (i1)/2 so sánh đ
ườ ặ ự ượ c th c ợ ng h p
ổ
9
ả thi trong vòng l p trong. Do đó, trong tr ố ầ trung bình, t ng s l n so sánh là: (N1)/2 + (N2)/2 + ... + 1/2 =N(N1)/4
=O(N2)
Độ phức tạp của sắp thứ tự bằng phương pháp chèn
ứ ự ằ
ươ
b ng ph
ng pháp chèn
S p th t
ị
2/2 so sánh và N2/4 hoán v trong
ự ườ
ắ ấ Tính ch t 1.2: ả th c thi kho ng N ấ . ợ ấ ng h p x u nh t tr
ứ ự ằ
ươ
b ng ph
: S p th t
ng pháp chèn ị
2/4 so sánh và N2/8 hoán v trong
ự ườ
ắ Tính ch t 1.3ấ ả th c thi kho ng N ợ ng h p trung bình tr
.
ắ
ứ ự ằ
ươ
b ng ph
ng pháp chèn ầ
: S p th t ế
ố ớ ộ ả
Tính ch t 1.4ấ ộ ứ ạ có đ ph c t p tuy n tính đ i v i m t m ng đã g n .ứ ự có th t
10
3. Các giải thuật duyệt đồ thị
ố ượ
ế
c đ nh nghĩa theo đ i t
ng và các k t
ố ữ
ố ượ ấ
ề Có nhi u bài toán đ n i gi a các đ i t
ượ ị ng y.
ộ ố ượ
ả ữ
ọ ng toán h c mà mô t
nh ng bài
ự
ứ
ộ ồ ị M t đ th là m t đ i t ư ậ toán nh v y. ụ Các ng d ng trong các lãnh v c:
Giao thông ễ Vi n thông ệ ự Đi n l c ạ M ng máy tính ơ ở ữ ệ C s d li u Trình biên d chị ệ ề Các h đi u hành ế ồ ị Lý thuy t đ th
11
Một thí dụ
A
H
I
B
C
G
D
E
J
K
F
L
M
ộ ồ ị
12
Hình 3.1a M t đ th thí dụ
Cách biểu diễn đồ thị
ạ ố tên đ nhỉ thành nh ng ữ s nguyên trong
ả Ta ph i ánh x các ị ữ ầ t m tr gi a 1 và V.
ả ử s có t n t
ố ỉ tên đ nh thành s nguyên
ỉ ồ ạ i hai hàm: Gi ể ổ ừ hàm index: chuy n đ i t ể ổ ố hàm name: chuy n đ i s nguyên thành tên đ nh.
13
ế ậ ậ ễ ồ ị ể Có hai cách bi u di n đ th : ế ậ ậ dùng ma tr n k c n dùng t p danh sách k c n
Cách biểu diễn ma trận kế cận
ậ ộ
đ nh y và ượ c
A B C D E F G H I J K L M A 1 1 1 0 0 1 1 0 0 0 0 0 0 B 1 1 0 0 0 0 0 0 0 0 0 0 0 C 1 0 1 0 0 0 0 0 0 0 0 0 0 D 0 0 0 1 1 1 0 0 0 0 0 0 0 E 0 0 0 1 1 1 1 0 0 0 0 0 0 F 1 0 0 1 1 1 0 0 0 0 0 0 0 G 1 0 0 0 1 0 1 0 0 0 0 0 0 H 0 0 0 0 0 0 0 1 1 0 0 0 0 I 0 0 0 0 0 0 0 1 1 0 0 0 0 J 0 0 0 0 0 0 0 0 0 1 1 1 1 K 0 0 0 0 0 0 0 0 0 1 1 0 0 L 0 0 0 0 0 0 0 0 0 1 0 1 1 M 0 0 0 0 0 0 0 0 0 1 0 1 1
14
M t ma tr n V ứ ộ hàng V c t ch a ị các giá tr Boolean mà a[x, y] là true if ế ồ ạ ộ n u t n t i m t ạ ừ ỉ x c nh t ỉ ế đ n đ nh ế false n u ng i.ạ l ế ậ Hình 3.1b: Ma tr n k ậ ủ ồ ị ở hình c n c a đ th 3.1a
Lưu ý: Mỗi cạnh tương ứng với 2 bit trong ma trận: mỗi cạnh nối giữa x và y được biểu diễn bằng giá trị true tại cả a[x, y] và a[y, x].
Để tiện lợi giả định rằng có tồn tại một cạnh nối mỗi đỉnh về chính nó.
Giải thuật program adjmatrix (input, output); const maxV = 50; var j, x, y, V, E: integer; a: array[1..maxV, 1..maxV] of boolean; begin readln (V, E); for x: = 1 to V do /*initialize the matrix */ for y: = 1 to V do a[x, y]: = false; for x: = 1 to V do a[x, x]: = true; for j: = 1 to E do begin readln (v1, v2); x := index(v1); y := index(v2); a[x, y] := true; a[y, x] := true end; end.
15
Cách biểu diễn bằng tập danh sách kế cận
ễ
ộ ỉ
ọ ỉ ố ớ i ế ậ ộ danh sách k c n
ỉ
ể Trong cách bi u di n này, m i đ nh mà n i t ượ ế c k t thành m t m t đ nh đ (adjacencylist ) cho đ nh đó.
16
program adjlist (input, output); const maxV = 100; type link = (cid:0) node node = record v: integer; next: link end; var j, x, y, V, E: integer; t, x: link; adj: array[1..maxV] of link;
Lưu ý: Mỗi cạnh trong đồ thị tương ứng với hai nút trong tập danh sách kế cận.
Số nút trong tập danh sách kế cận bằng 2|E|.
17
begin readln(V, E); new(z); z(cid:0) .next: = z; for j: = 1 to V do adj[j]: = z; for j: 1 to E do begin readln(v1, v2); x: = index(v1); y: = index(v2); new(t); t(cid:0) .v: = x; t(cid:0) .next: = adj[y]; adj[y]: = t; /* insert x to the first element of y’s adjacency list */ new(t); t(cid:0) .v = y; t(cid:0) .next: = adj[x]; adj[x]:= t; /* insert y to the first element of x’s adjacency list */ end; end.
a b c d e f g h i j k l m
a
a
e
i
h
k
j
j
f
g
a
j
f
c
e
f
e
a
m
l
l
d
m
b
d
g
ễ ằ
18
ậ ể Hình 3.1c: Bi u di n b ng t p ế ậ ủ ồ ị ở danh sách k c n c a đ th hình 3.1
Nếu biểu diễn đồ thị bằng tập danh sách kế cận, việc
So sánh hai cách biểu diễn đồ thị
Nếu biểu diễn đồ thị bằng ma trận kế cận, việc kiểm tra xem có tồn tại một cạnh giữa hai đỉnh u và v sẽ có độ phức tạp thời gian O(1) vì chỉ cần xem xét phần tử tại vị trí (u,v) của ma trận.
Biểu diễn đồ thị bằng ma trận kế cận gây lãng phí chỗ bộ nhớ khi đồ thị là một đồ thị thưa (không có nhiều cạnh trong đồ thị, do đó số vị trí mang giá trị 1 là rất ít)
19
kiểm tra xem có tồn tại một cạnh giữa hai đỉnh u và v sẽ có độ phức tạp thời gian O(V) vì có thể có O(V) đỉnh tại danh sách kế cận của đỉnh u.
Các phương pháp duyệt đồ thị
ệ
ồ ị
ỗ
ế ồ ị ộ
ế ệ ố
ỉ
Duy t hay tìm ki m trên đ th : vi ng m i đ nh/nút trong đ th m t cách có h th ng.
ể
c (
ệ ồ ị Có hai cách chính đ duy t đ th : ệ ướ depthfirstsearch ) ề c ( duy t theo chi u sâu tr ướ breadthfirst ề ộ ệ duy t theo chi u r ng tr search).
20
Duyệt theo chiều sâu trước
21
procedure dfs; procedure visit(n:vertex); begin add n to the ready stack; while the ready stack is not empty do get a vertex from the stack, process it, and add any neighbor vertex that has not been processed to the stack. if a vertex has already appeared in the stack, there is no need to push it to the stack. end; begin Initialize status; for each vertex, say n, in the graph do if the status of n is “not yet visited” then visit(n) end;
Tìm kiếm theo chiều sâu trước – biểu diễn danh sách kế cận (giải thuật đệ quy)
22
procedure listdfs; var id, k: integer; val: array[1..maxV] of integer; procedure visit (k: integer); var t: link; begin id: = id + 1; val[k]: = id; /* change the status of k to “visited” */ t: = adj[k]; / * find the neighbors of the vertex k */ while t <> z do begin if val[t (cid:0) .v] = 0 then visit(t(cid:0) .v); t: = t(cid:0) .next end end;
begin id: = 0; for k: = 1 to V do val[k]: = 0; /initialize the status of all vetices */ for k: = 1 to V do if val[k] = 0 then visit(k) end;
c a cácđ nh.
ỉ ế ạ ư ề ượ k ch a h đ ỉ ủ c vi ng (“not yet
ỉ
ế c vi ng. ượ ế ượ jth mà đ c vi ng trong quá trình
23
ệ ỉ Ghi chú: M ng ả val[1..V] ch a ứ tr ng thái ế val[k] = 0 n u đ nh visited”), ế k đã đ val[k] ≠ 0 n u đ nh ỉ val[k]: = j nghĩa là đ nh duy t là đ nh k.
A
A
A
A
E
F
F
F
A
A
A
A
G
G
G
G
E
E
E
E
F
F
F
F
A
A
A
A
G
G
G
G
D
E
D
E
D
E
D
E
F
F
F
F
A
A
A
A
C
B
B
G
G
G
G
C
C
C
E
D
E
D
D
E
D
E
F
F
F
F
24
Hình 3.2 Duyệt theo chiều sâu trước
Độ phức tạp của DFS
Nh v y k t qu c a DFS
ả ủ ở
ư ậ ế ồ ị trên đ th cho hình 3.1a ớ ậ ế ậ v i t p danh sách k c n ở cho hình 3.1c là
Tính chất 3.1.1 Duyệt theo chiều sâu trước một đồ thị biểu diễn bằng các danh sách kế cận đòi hỏi thời gian tỉ lệ V+ E.
ưở đ n th t ế ỉ
ụ A F E G D C B ỉ ứ ự ủ L u ýư : th t c a các đ nh ế ậ trong các danh sách k c n ứ ự ả có nh h ng ệ ủ duy t c a các đ nh khi áp d ng DFS.
25
Chứng minh: Chúng ta phải gán trị cho mỗi phần tử của mảng val (do đó tỉ lệ với O(V)), và xét mỗi nút trong các danh sách kết cận biểu diễn đồ thị (do đó tỉ lệ với O(E)).
ế ậ
ễ
ể
ậ
ằ DFS – bi u di n b ng ma tr n k c n
ụ ng pháp có th đ ồ ị c áp d ng cho đ th
ằ ể ượ ế ậ ậ ộ ể ươ ễ ằ c bi u di n b ng ma tr n k c n b ng cách dùng
Cùng m t ph đ th t c ượ ủ ụ visit sau đây:
Tính chất 3.1.2 Duyệt theo chiều sâu trước một đồ thị biểu diễn bằng ma trận kế cận tỉ lệ với V2.
procedure visit(k: integer); var t: integer; begin id: = id + 1; val[k]: = id; for t: = 1 to V do if a[k, t] then if val[t] = 0 then visit(t) end;
Chứng minh: Bởi vì mỗi bit trong ma trận kế cận của đồ thị đều phải kiểm tra.
26
Duyệt theo chiều rộng trước
Khi duyệt đồ thị nếu ta dùng một queue thay vì một stack, ta sẽ đi đến một giải thuật duyệt theo chiều rộng trước (breadth-first- search).
procedure bfs; procedure visit(n: vertex); begin add n to the ready queue; while the ready queue is not empty do get a vertex from the queue, process it, and add any neighbor vertex that has not been processed to the queue and change their status to ready. end; begin Initialize status; for each vertex, say n, in the graph if the status of n is “not yet visited” then visit(n) end;
27
procedure listbfs; var id, k: integer; val: array[1..max V] of integer; procedure visit(k: integer); var t: link; begin put(k); /* put a vertex to the queue */ repeat k: = get; /* get a vertex from the queue */ id: = id + 1; val[k]: = id; /* change the status of k to “visited” */ t: = adj[k]; /* find the neighbors of the vertex k */ while t <> z do begin if val[t (cid:0) .v] = 0 then begin put(t(cid:0) .v); val [t(cid:0) .v]: = 1 /* change the vertex t(cid:0) .v to “ready” */ end; t: = t(cid:0) .next end until queueempty end;
28
begin id: = 0; queueinitialze; for k: = 1 to V do val[k]: = 0; /initialize the status of all vertices */ for k: = 1 to V do if val[k] = 0 then visit(k) end;
ề ề ộ c và duy t theo chi u r ng
ệ ậ ầ
i thu t đ u dùng stack và ộ ứ ạ i thu t sau dùng hàng đ i. Do đó, đ ph c t p tính toán
29
ư ệ Duy t theo chi u sâu tr ỉ ướ c ch khác nhau tr ậ ả gi ủ c a DFS và BFS là ướ ở ỗ ả ch gi ợ nh nhau .
I
H
D
D
D
D
D
E
E
E
E
G
G
G
G
B
B
B
M
M
M
C
C
L
L
F
K
A
J
ự
ủ
ệ
ộ
ợ
Hình 3.3 N i dung c a hàng đ i khi th c hi n BFS
30
4. Xếp thứ tự tôpô
ồ ị ố ạ
ướ ướ ồ ị Các đ th có h ớ v i các nút có h ng là các đ th trong đó các c nh n i ng.
A
H
I
B
C
G
D
E
J
K
F
L
M
ụ ề ồ ị
ộ
Hình 3.4. M t thí d v đ th có h
ngướ
31
ướ ủ ố ể ạ ng c a các c nh bi u th
ườ ướ ượ ệ ị m i liên h ụ ứ (precedence relationship) trong ng d ng đ c
ng thì h Th tr c sau mô hình hóa.
ướ ể ượ ể c dùng đ mô hình hóa
ộ ườ ng có th đ ấ ụ ồ ị Thí d , đ th có h ả m t đ ng dây s n xu t (assembly line).
ầ ả ậ ắ i thu t s p th t ứ ự
32
Trong ph n này, chúng ta xem xét gi topo (topological sorting)
Lưu ý về cách biểu diễn đồ thị có hướng
Nếu ta biểu diễn đồ thị có hướng bằng tập danh
Nếu ta biểu diễn đồ thị có hướng bằng ma trận kế
sách kế cận, mỗi cạnh trong đồ thị tương ứng với một nút trong tập danh sách kế cận. (mỗi cạnh nối từ x đến y được biểu diễn bằng một nút có nhãn y được đưa vào danh sách kế cận của đỉnh x) Số nút trong tập danh sách kế cận bằng với số cạnh |E|
33
cận, mỗi cạnh trong đồ thị tương ứng với một bit 1 trong ma trận kế cận. (mỗi cạnh nối từ x đến y được biểu diễn bằng giá trị true tại a[x, y]).
Xếp thứ tự tôpô
ướ ng không chu trình (Directed Acyclic
ượ ọ c g i là các
ướ ướ ồ ị Đ th có h Graph) ồ ị Đ th có h ồ ị đ th có h ng mà không có chu trình đ ng không chu trình (dags).
ứ ự ậ ứ ự ế ầ T p th t riêng ph n và x p th t tôpô
ng không chu trình. Xét quan
ư ệ ứ ự < đ
ộ ồ ị ướ Cho G là m t đ th có h ượ ị c đ nh nghĩa nh sau: h th t ộ ố ế u < v n u có m t l i đi t ừ u đ n ế v trong G.
ấ ệ
ớ ỗ ỉ không ph n ả
ế ế
ố ứ ) không đ i x ng Truy nề ) 34 ệ ứ ự ệ Quan h này có 3 tính ch t: (1) V i m i đ nh trong V[G], not (u < u). ( xạ) (2) n u u < v, thì not( v < u) . ( (3) n u u < v và v < w, thì u < w. ( ầ . ộ quan h th t riêng ph n Quan h < là m t
Xếp thứ tự tôpô
ướ
ộ ồ ị tôpô (
ả
ng không chu trình. ủ ộ topological sort)T c a G là m t ầ ứ ự riêng ph n
ậ
Cho G là m t đ th có h ứ ự ộ M t th t ế ứ ự th t tuy n tính mà b o toàn th t ỉ ầ ban đ u trong t p đ nh V[G].
i
ế ệ
ướ
ế
ứ ấ thì u xu t hi n tr
ộ ố c v trong
ế
Nghĩa là: n uế u < v trong V (t c là n u có m t l ừ đi t ứ ự th t
u đ n v trong G), tuy n tính T .
35
A
H
I
B
C
G
D
E
J
K
F
L
M
ể ượ ắ ứ ự hình trên có th đ c s p th t
ứ ự
36
ồ ị ở Các nút trong đ th sau: tôpô theo th t J K L M A G H I F E D B C
Phương pháp 1 sắp xếp tôpô
ệ ế ể tìm ki m theo ự ng pháp này th c hi n theo ki u
ỗ
c ộ ể ế ụ ộ ỏ ướ và thêm m t nút vào danh sách m i khi ặ t l y m t nút ra kh i stack đ ti p t c. Khi g p
ẽ ấ
đ nh stack. L p l ượ ứ ự i quá trình này cho đ n khi ẽ ượ ộ ế c th t c danh sách này ta s đ
ươ Ph ề chi u sâu tr ế ấ ầ c n thi ộ m t nút không có nút đi sau thì ta s l y ra (pop) m t ặ ạ ầ ử ừ ỉ t ph n t ả ỗ stack r ng. Đ o ng tôpô.
37
Algorithm: Start with nodes with no predecessor, put them in the stack. while the stack is not empty do if the node at top of the stack has some successors then push all its successors onto the stack else pop it from the stack and add it to the list.
1
2
10
4
6
9
8
3
5
7
ứ ự
ắ
Hình 3.5 S p th t
tôpô
8 6 5 5 5 4 4 4 3 3 3 3 3 10 10 10 10 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 9 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
38
Độ phức tạp của giải thuật sắp xếp tô pô phương pháp 1
Tính chất: Độ phức tạp tính toán của giải thuật sắp xếp tô pô là O(|E|+|V|) nếu đồ thị được diễn tả bằng tập danh sách kế cận.
Chứng minh: Điều này hiển nhiên vì thân của vòng lặp while được thực hiện tối đa 1 lần cho mỗi cạnh. Và tác vụ khởi tạo stack thì tỉ lệ với số đỉnh của đồ thị
39
Phương pháp 2 sắp thứ tự tô pô
Ý tưởng: Liên tiếp nhận diện một nút là nút nguồn (nút không có nút đi sau) và tháo gỡ nó ra khỏi đồ thị cùng với các cạnh đi ra từ nó. Quá trình lặp sẽ dừng lại khi không còn nút trong đồ thị. Thứ tự của các nút bị xóa bỏ sẽ tạo thành một lời giải của bài toán sắp thứ tự tô pô.
Giải thuật này thể hiện rất rõ chiến lược giảm (một)-
40
để-trị.
a
d
d
d
gỡ a
gỡ b
c
c
c
b
e
e
b
e
d
gỡ c
gỡ d
gỡ e
e
e
41
Thứ tự tô pô là a, b, c, d, e
Giải thuật của phương pháp 2
Algorithm: Start with nodes with no predecessor, put them in the queue. while the queue is not empty do remove the front node N of the queue for each neighbor node M of node N do delete the edge from N to M if the node M has no successor then add M to the rear of the queue endfor endwhile
Độ phức tạp của giải thuật này là bao nhiêu?
42
5. Giải thuật sinh các hoán vị
Cho một tập n phần tử A= {a1,a2,…,an}. Ta muốn sinh ra
Chiến lược Giảm-để-trị có thể có gợi ý gì về giải thuật
tất cả n! hoán vị của tập ấy.
Bài toán nhỏ hơn một bậc là sinh ra tất cả (n-1)! hoán vị cho một tập con n -1 phần tử của tập A nói trên. Giả sử bài toán này đã được giải xong, ta có thể giải bài toán nguyên thủy bằng cách chèn phần tử còn lại vào tại mỗi vị trí trong n vị trí khả hữu của các phần tử trong từng hoán vị của tập n -1 phần tử đã sinh.
Tất cả các hoán vị đạt được bằng cách này sẽ khác biệt
sinh tất cả các hoán vị của một tập n phần tử?
43
nhau.
Thí dụ
khởi đầu thêm 2 1 12 21
right to left 123 132 312 213 231 321
right to left
right to left
thêm 3
44
Để đơn giản, giả sử tập A là một tập hợp các số nguyên từ 1 đến n. Chúng có thể được hiểu như là tập các chỉ số của tập n phần tử {a1,a2,…,an}.
Giải thuật PERM
45
1. Set j:= 1 and write down the permutation <1>
2. set j:= j+1
3. for each permutation
Độ phức tạp của giải thuật PERM
Tính chất: Độ phức tạp của giải thuật PERM sinh ra tất cả
các hoán vị của tập n phần tử là n!
Chứng minh: Thao tác căn bản: thao tác chèn phần tử còn lại vào một
Với mỗi hoán vị từ tập con n-1 phần tử (gồm tất cả (n-1)! các hoán vị này), ta đưa phần tử còn lại vào n vị trí khả hữu. Như vậy tổng cọng có n.(n-1)! thao tác chèn phần tử còn lại vào một hoán vị đã có.
Do đó: C(n) = O(n!) Nhận xét: Vì n! tăng rất nhanh nên với n chỉ hơi lớn (10
hoán vị đã có.
46
trở lên), giải thuật cho ra kết quả cực kỳ chậm.
Công thức Stirling
n! xấp xỉ bằng với hàm
n(cid:0)2
(n/e)n
47
với e là cơ số logarit tự nhiên (e = 2.71828)
