Giáo trình Lý thuyết thuật toán

93 trang phuongnguyen 3950

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết thuật toán", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_ly_thuyet_thuat_toan.pdf

Nội dung text: Giáo trình Lý thuyết thuật toán

Giáo trình Lý thuyết thuật toán
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 MỤỤ C L C Nộ i dung Trang Chươ ng 1: K ỹ thu ậ t phân tích đánh giá thu ậ t toán 4 1.1. Khái niệ m bài toán và đ ộ ph ứ c t ạ p d ữ li ệ u vào 4 1.1.1. Khái niệ m bài toán 4 1.1.2. Độ ph ứ c t ạ p d ữ li ệ u vào c ủ a bài toán 4 1.2. Các mô hình tính toán 4 1.2.1. Máy Turing 5 1.2.2. Máy xử lý thu ậ t toán vi ế t b ằ ng ngôn ng ữ t ự a ALGOL 7 1.3. Khái niệ m thu ậ t toán và đ ộ ph ứ c t ạ p c ủ a thu ậ t toán 7 1.3.1. Thuậ t toán(Algorithm) 7 1.3.2 Chi phí phả i tr ả cho m ộ t quá trình tính toán và các khái 7 niệ m v ề đ ộ ph ứ c t ạ p thu ậ t toán 1.4. Cách tính độ ph ứ c t ạ p 10 1.4.1. Các quy tắ c c ơ b ả n 10 1.4.2. Độ ph ứ c t ạ p c ủ a các ch ươ ng trình đ ệ quy 11 1.5. Thuậ t toán không đ ơ n đ ị nh đa th ứ c(Nodeterministic 14 Polynomial NP) 1.5.1. Sự phân l ớ p các bài toán. 16 1.5.2. Khái niệ m “d ẫ n v ề đ ượ c” (Phép quy dẫ n) 17 1.5.3 Lớ p bài toán NP - khó (NP - hard) và NP - đầ y đ ủ (NP – 18 Complate) 1.6. Thuậ t toán x ấ p x ỉ (Heuristic) 22 1.6.1. Các khái niệ m 22 1.6.2. Thuậ t toán ε - xấ p x ỉ tuy ệ t đ ố i 24 1.6.3.Thuậ t toán ε - xấ p x ỉ 26 1.7. Chứ ng minh tính đúng đ ắ n c ủ a thu ậ t toán 28 1.7.1. Ví dụ : 28 1.7.2. Phươ ng pháp th ử 28 1.7.3. Kiể m ch ứ ng tính đúng đ ắ n 29 Chươ ng 2: Các thuậ t toán S ắ p x ế p 31 2.1. Bài toán sắ p x ế p 31 2.1.1. Tầ m quan tr ọ ng c ủ a bài toán s ắ p x ế p 31 2.1.2. Sắ p x ế p trong và s ắ p x ế p ngoài 31 2.1.3. Tổ ch ứ c d ữ li ệ u và ngôn ng ữ cài đ ặ t 31 2.1.4. Thuậ t toán s ắ p x ế p 32 2.2. Các phươ ng pháp s ắ p x ế p đ ơ n gi ả n 32 2.2.1. Sắ p x ế p ch ọ n (Selection Sort) 32 2.2.2. Sắ p x ế p chèn (InsertionSort) 33 2.2.3. Sắ p x ế p n ổ i b ọ t(Bubble Sort) 35 2.3. Sắ p x ế p nhanh QUICK SORT 36 2.3.1. Ý tưở ng 36 2.3.2. Thiế t k ế gi ả i thu ậ t 36 2.3.3. Đánh giá độ ph ứ c t ạ p 38 2.4. Sắ p x ế p ki ể u vun đ ố ng (Heapsort) 39 2.4.1. Đị nh nghĩa HEAP 39 2.4.2. Sắ p x ế p ki ể u vun đ ố ng 40 1
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 2.4.3. Độ ph ứ c t ạ p tính toán 40 2.5. Sắ p x ế p hòa nh ậ p (Merge Sort) 43 2.5.1. Ý tưở ng 43 2.5.2. Thiế t k ế gi ả i thu ậ t 44 2.5.3. Đánh giá độ ph ứ c t ạ p 46 2.6. Cấ u trúc d ữ li ệ u và gi ả i thu ậ t x ử lý ngoài 46 2.6.1. Mô hình xử lý ngoài 46 2.6.2. Đánh giá các giả i thu ậ t x ử lý ngoài 47 2.6.3. Sắ p xêp ngoài - MergeSorting 47 2.6.4. Cả i ti ế n s ắ p x ế p tr ộ n 51 2.6.5. Trộ n nhi ề u đ ườ ng 52 Chươ ng 3: K ỹ thu ậ t thi ế t k ế thu ậ t toán 54 3.1. Chia để tr ị 54 3.1.1. Nộ i dung 54 3.1.2. Mộ t s ố bài toán áp d ụ ng 55 3.2. Quy hoạ ch đ ộ ng (Dynamic) 58 3.2.1. Nộ i dung 58 3.2.2. Ví dụ áp d ụ ng 59 3.3. Phươ ng pháp tham lam (Greedy Method) 63 3.3.1. Bài toán tố i ư u t ổ h ợ p 63 3.3.2. Nộ i dung 64 3.4. Phươ ng pháp nhánh c ậ n (Branch- and- Bound) 68 3.4.1. Nộ i dung 68 3.4.2. Các bài toán áp dụ ng 69 Chươ ng 4: Lý thuy ế t l ậ p l ị ch 75 4.1. Vấ n đ ề l ậ p l ị ch t ố i ư u 75 4.1.1. Bài toán 75 4.1.2. Nhậ n xét 76 4.1.3. Tình hình giả i bài toán l ậ p l ị ch hi ệ n nay 77 4.2. Phân lớ p bài toán l ậ p l ị ch d ạ ng tĩnh 78 4.2.1. Thông tin về công vi ệ c 78 4.2.2. Quan hệ gi ữ a các máy 78 4.2.3. Quan hệ gi ữ a các công vi ệ c 79 4.2.4. Mộ t s ố tiêu chu ẩ n t ố i ư u 80 4.2.5. Mộ t s ố ví d ụ 80 4.2.6. Mộ t s ố thu ậ t toán l ậ p l ị ch 81 4.3. Mộ t s ố bài toán l ậ p l ị ch gi ả i b ằ ng thu ậ t toán l ậ p l ị ch t ố i 81 ưu nhanh 4.3.1. Hệ 1,n  Cmax 81 4.3.2. Nhóm hệ 1, n Lmax và 1, n Tmax 83 ≥ 4.3.3. Hệ 1,n ri 0 Cmax 85 4.4. Bài toán lậ p l ị ch gia công trên 2 máy, thu ậ t toán Johnson 88 ≥ 4.4.1. Bài toán 2; Fri 0 Cmax 88 4.4.2. Thiế t k ế thu ậ t toán 88 4.4.3. Mộ t s ố tr ườ ng h ợ p riêng có th ể d ẫ n v ề bài toán 2 máy 91 2
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Chươ ng 1 KỸẬẬ THU T PHÂN TÍCH, ĐÁNH GIÁ THU T TOÁN 1.1. Khái niệ m bài toán và đ ộ ph ứ c t ạ p d ữ li ệ u vào 1.1.1. Khái niệ m bài toán - Thông thườ ng m ộ t bài toán đ ượ c cho d ướ i d ạ ng sau: + Input: Các dữ li ệ u vào c ủ a bài toán. + Output: Các dữ li ệ u ra tho ả mãn yêu c ầ u c ủ a bài toán. - Giả i bài toán có nghĩa là xu ấ t phát t ừ d ữ li ệ u vào, th ự c hi ệ n m ộ t dãy h ữ u h ạ n nhữ ng thao tác có c ơở s khoa h ọ c thích h ợểượữệ p đ tìm đ c d li u ra (k ếả t qu ) theo yêu cầ u c ủ a bài toán. 1.1.2. Độ ph ứ c t ạ p d ữ li ệ u vào c ủ a bài toán Có hai quan niệ m ch ủ y ế u: Quan niệ m 1(quan niệ m đ ơ n gi ả n): Độ ph ứ c t ạ p d ữ li ệ u vào c ủ a bài toán đ ự oc hiể u là s ố l ượ ng d ữ li ệ u vào c ủ a bài toán (kích th ướ c c ủ a bài toán Quan niệ m 2: Là tổ ng đ ộ dài c ủ a m ọ i d ữ li ệ u vào đã đ ượ c mã hóa theo m ộ t cách nào đó. Ví dụ : Cho dãy s ố nguyên X={x1,x2, ,xn}. Tìm giá trị l ớ n nh ấ t trong dãy? Bài toán đượ c bi ể u di ễ n nh ư sau: Input : Cho dãy số nguyên X= {x1,x2, ,xn}, số l ượ ng n. Output: Tìm số l ớ n nh ấ t Max c ủ a dãy X. - Theo quan niệ m 1 : Kích th ướ c c ủ a bài toán là (n+1) - Theo quan niệ m 2 : Kích th ướ c c ủ a bài toán là + Số t ự nhiên xi theo mã nhị phân có đ ộ dài là [log2xi]+1 VD: xi mã độ dài 3 11 [log23]+1=2 5 101 [log25]+1=3 n +Độ dài d ữ li ệ u c ủ a bài toán trên là: ∑ [log2xi] +log2n+n+1 i=1 1.2. Các mô hình tính toán Thông tườ ng ng ườ i ta xét đ ế n 2 mô hình tính toán thông d ụ ng: - Mô hình lí thuyế t: Máy Turing. 3
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Mô hình ứ ng d ụ ng: Máy x ử lý thu ậ t toán vi ế t b ằ ng ngôn ng ữ t ự a Algol ( các ngôn ngữ l ậ p trình b ậ c cao). 1.2.1. Máy Turing a) Câú tạ o: + B ộ nh ớ : G ồ m m ộ t băng tuy ế n tính vô h ạ n ở đ ầ u ph ả i, chia thành các ô nhớ , m ỗ i ô ch ứ a đ ượ c m ộ t kí hi ệ u nguyên t ố . n ô trái (n≥ 0) đượ c ghi các kí hiệủ u c a xâu vào, ph ầ n còn l ạở i bên ph ảượấầởộ i đ c l p đ y b i m t kí hiệ u đ ặ c bi ệ t g ọ i là kí hi ệ u tr ắ ng B. + Bộềể đi u khi n: Có h ữạạ u h n tr ng thái, t ạỗờể i m i th i đi m có m ộ t trạ ng thái xác đ ị nh. + Mộ t đ ầ u đ ọ c/ vi ế t, nó cho phép t ạ i m ộ t th ờ i đi ể m có th ể đ ọ c hay viế t ở m ộ t ô trên băng. b) Hoạộ t đ ng: Theo th ờ i gian “r ờạượềểởộềể i r c”, đ c đi u khi n b i b đi u khi n. Tùy thuộ c vào tr ạ ng thái hi ệ n t ạ i và kí hi ệ u đ ọ c đ ượ c trên băng mà nó ti ế n hành mộ t b ướ c chuy ể n g ồ m đ ồ ng th ờ i 3 đ ộ ng tác sau: 1. Đổ i tr ạ ng thái trên b ộ đi ề u khi ể n 2. Viế t m ộ t kí hi ệ u lên ô đang đ ọ c 3. Chuyể n đ ầ u đ ọ c vi ế t sang ph ả i hay trái m ộ t ô theo quy đ ị nh c ủ a hàm chuyể n. Mộ t cách hình th ứ c, xem máy Turing là m ộ t b ộ T = (∑, Q, Γ, δ, q0, B,F) Trong đó : Q: Tậ p h ữ u h ạ n các tr ạ ng thái. Γ : Tậ p h ữ u h ạ n các kí hi ệ u trên băng B : Mộ t kí hi ệ u đ ặ c bi ệ t thu ộ c Γ gọ i là kí hi ệ u tr ắ ng. ∑ : Tậ p con c ủ a Γ , không chứ a B, đ ượ c g ọ i là b ộ ch ữ vào(kí hi ệ u kế t thúc) q0: Trạ ng thái đ ầ u F⊆Q: Tậ p tr ạ ng thái k ế t thúc. δ: Hàm chuyể n tr ạ ng thái δ : Q x Γ Q x Γ x {L,R} L, R là các trạ ng thái: trái, ph ả i 4
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Mộ t hình tr ạ ng c ủ a máy Turing là m ộ t xâu có d ạ ng #γ 1q γ 2#, trong đó # là mộ t ký * hiệ u không thu ộ c Γ , # gọ i là ký hi ệ u mút ; còn γ 1, γ 2 ∈Γ , q ∈Q. Hình trạ ng đ ầ u là * #q0w # vớ i w∈∑ Ví dụ 1: Thờ i đi ể m t X Z C D p Thờ i đi ể m t+1 Y Z C1 D1 q (sang phả i) Hình 1: Mộ t b ướ c ho ạ t đ ộ ng c ủ a máy Turing Tạ i th ờ i đi ể m t máy Turing ở tr ạ ng thái p, đ ầ u đ ọ c /vi ế t nhòm vào ô nh ớ có kí hiệ u là X. T ạờểế i th i đi m ti p theo t+1 (m ộơịờ t đ n v th i gian) máy ởạ tr ng thái q, ký hiệ u X đã thay b ằ ng Y, đ ầ u đ ọ c/vi ế t chuy ể n sang trái ho ặ c sang ph ả i. δ: (p,X)→(q,Y,d) d∈{L,R} hay viế t pX→qYd g ọ i là m ộ t m ệ nh l ệ nh c ủ a máy T, xâu kí t ự CpXD g ọ i là m ộ t hình trạ ng c ủ a máy T. CpXD→C1qZD1 gọ i là m ộ t b ướ c chuy ể n hình tr ạ ng, n ế u q∈F thì xem như quá trình xử lý k ế t thúc hay C1qZD1 là hình trạ ng cu ố i cùng. - Nế u δ là hàm đơ n tr ị thì T đ ượ c g ọ i là máy t ấ t đ ị nh(đ ơ n đ ị nh) - Nế u δ là hàm đa trị thì T đ ượ c g ọ i là máy không t ấ t đ ị nh(không đ ơ n đ ị nh) - Đơịớ n v nh : Là ô nh ớứộệế ch a m t kí hi u, n u dùng mã nh ị phân thì đ ơịớ n v nh là 1 bit. - Đơịờ n v th i gian: Là th ờ i gian đ ểựệộướạộơảướ th c hi n m t b c ho t đ ng c b n (b c chuyể n hình tr ạ ng). Nhậ n xét: Máy Turing có cấạự u t o c c kì đ ơảưạ n gi n nh ng l i làm đ ượọệ c m i vi c liên quan tớ i tính toán các phép tính. T ừ mô hình này có th ể đ ị nh nghĩa ra phép c ộ ng (mã hóa dạ ng nh ị phân) b ằ ng cách d ị ch chuy ể n đ ầ u đ ọ c 0, 1 và t ừ đó đ ị nh nghĩa ra các phép tính khác. 5
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 1.2.2. Máy xử lý thu ậ t toán vi ế t b ằ ng ngôn ng ữ t ự a ALGOL - Đơịớộ n v nh : M t ô nh ớứọẹộữệ ch a tr n v n m t d li u. - Đơịờ n v th i gian: Th ờ i gian đ ểựệộ th c hi n m t phép tính c ơả b n trong s ốọ h c hay logic như c ộ ng, tr ừ , nhân, chia, gán, so sánh 1.3. Khái niệ m thu ậ t toán và đ ộ ph ứ c t ạ p c ủ a thu ậ t toán 1.3.1. Thuậ t toán(Algorithm) Thuậ t toán đ ượểơả c hi u đ n gi n là m ộ t dãy h ữạ u h n các qui t ắớấạ c. V i c u t o và hoạ t đ ộ ng c ủ a máy Turing, ta có th ể đ ị nh nghĩa m ộ t cách hình th ứ c thu ậ t toán chính là mộ t máy Turing. Ta đã có 2 mô hình tính toán là máy Turing và máy xử lý thu ậ t toán vi ế t b ằ ng ngôn ngữ t ự a ALGOL. Ứ ng v ớ i hai mô hình tính toán này có 2 cách bi ể u di ễ n thu ậ t toán: + Thuậ t toán đ ượ c bi ể u di ễ n b ằ ng ngôn ng ữ máy Turing. + Thuậ t toán đ ượ c bi ể u di ễ n b ằ ng ngôn ng ữ t ự a ALGOL. 1.3.2 Chi phí phả i tr ả cho m ộ t quá trình tính toán và các khái ni ệ m v ề đ ộ ph ứ c tạ p thu ậ t toán 1.3.2.1. Chi phí phả i tr ả cho m ộ t quá trình tính toán Thườ ng quan tâm t ớ i chi phí th ờ i gian và chi phí không gian (bộ nh ớ) - Chi phí thờ i gian c ủ a m ộ t quá trình tính toán là th ờ i gian c ầ n thi ế t đ ể th ự c hi ệ n mộ t quá trình tính toán. + Vớ i máy Turing: Chi phí th ờ i gian là s ố b ướ c chuy ể n hình tr ạ ng t ừ hình tr ạ ng đầ u đ ế n hình tr ạ ng k ế t thúc. + Vớ i thu ậ t toán t ự a Algol: Chi phí th ờ i gian là s ố các phép tính c ơ b ả n c ầ n th ự c hiệ n trong quá trình tính toán. - Chi phí không gian củ a m ộ t quá trình tính toán là s ố ô nh ớ c ầ n đ ể th ự c hi ệ n m ộ t quá trình tính toán. Gọ i A là m ộ t thu ậ t toán t ươ ng ứ ng v ớ i m ộ t mô hình tính toán Gọ i e là b ộ d ữ li ệ u vào đã đ ượ c mã hóa theo cách nào đó Khi đó thuậ t toán A tính trên d ữ li ệ u e c ầ n ph ả i tr ả m ộ t giá nh ấ t đ ị nh bao g ồ m 2 giá: + tA(e) là giá thờ i gian + lA(e) là giá bộ nh ớ Cùng mộ t thu ậ t toán A, x ử lý trên các b ộ d ữ li ệ u khác nhau thì s ẽ có giá khác nhau. Ví dụ 2: Cho dãy s ố nguyên S={x1,x2, xn}, số ph ầ n t ử n. 6
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Tìm số l ớ n nh ấ t c ủ a dãy ? Bài toán đượ c bi ể u di ễ n nh ư sau. Input: Dãy số nguyên S={x1,x2, xn}, n Ouput: Số l ớ n nh ấ t Max=max{xi} củ a S. Thuậ t toán A: Begin Max:=x1; For i:=2 to n do If xi>Max then Max:=xi; End. * Xét bộ d ữ li ệ u vào e1={4, 0, 9, 1, 5} lA(e1)=5+1+1+1=8 (số bi ế n vào:6, s ố bi ế n ra:1, s ố bi ế n ph ụ :1) tA(e1)=5+1=6 vì max:=4 thự c hi ệ n 1 phép tính vì x2=0 max=4 nên max:=9 thự c hi ệ n 2 phép tính x4=1<max=9 nên không làm gì thự c hi ệ n 1 phép tính x5=5<max=9 nên không làm gì thự c hi ệ n 1 phép tính ⇒ T ổ ng c ộ ng th ự c hi ệ n: 6 phép tính * Xét bộ d ữ li ệ u vào e2={2, 7, 8, 11, 17} ta có: lA(e2)=8 tA(e2)=1+4.2 = 9 Như v ậ y v ớ i e1≠ e2 chi phí xử lý c ủ a A trên e1 và e2 là khác nhau. b) Các khái niệ m v ề đ ộ ph ứ c t ạ p c ủ a thu ậ t toán  Độ ph ứ c t ạ p trong tr ườ ng h ợ p x ấ u nh ấ t Cho mộ t thu ậ t toán A v ớ i đ ầ u vào n, khi đó: - Độứạềộớ ph c t p v b nh trong tr ườ ng h ợấ p x u nh ấượị t đ c đ nh nghĩa là: LA(n) = max{lA(e)║│e│≤n} Tứ c là chi phí l ớ n nh ấ t v ề b ộ nh ớ . Trong ví dụ trên: D ữ li ệ u vào: n+1, ra:1, ph ụ :1 nên LA(e)=n+3. - Độứạờ ph c t p th i gian trong tr ườợấấượị ng h p x u nh t đ c đ nh nghĩa là : TA(n) = max{tA(e)║│e│≤n} Tứ c là chi phí l ớ n nh ấ t v ề th ờ i gian. 7
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Trong ví dụ trên TA(n) =1+2(n-1) = 2n-1.  Độ ph ứ c t ạ p trung bình Là tổốộứạ ng s các đ ph c t p khác nhau ứớ ng v i các b ộữệ d li u chia cho t ổố ng s .  Độ ph ứ c t ạ p ti ệ m c ậ n Thuậ t toán A v ớ i đ ầ u vào n g ọ i là có đ ộ ph ứ c t ạ p O(f(n)) n ế u ∃ hằ ng s ố C, N0: TA(n)≤ C.f(n) , ∀ n≥ N0. Tứ c là TA(n) có tố c đ ộ tăng là O(f(n))  Độ ph ứ c t ạ p đa th ứ c(Polynomial) Thuậ t toán đ ượọ c g i là có đ ộứạ ph c t p đa th ứếồạ c n u t n t i đa th ứ c P(n) mà TA(n)≤ C.P(n) , ∀ n≥ N0.  Thuậ t toán đa th ứ c Thuậ t toán đ ượọ c g i là đa th ứếộứạềờ c n u đ ph c t p v th i gian trong tr ườợấ ng h p x u nhấ t c ủ a nó là đa th ứ c. Việ c đánh giá đúng đ ộứạủ ph c t p c a bài toán là m ộấềếứứạ t v n đ h t s c ph c t p. Vì vậườ y ng i ta th ườ ng quan tâm đ ếệấ n vi c đ nh giá đ ộứạờ ph c t p th i gian trong trườ ng h ợ p x ấ u nh ấ t c ủ a bài toán. Mộ t s ố đ ơ n v ị đo t ố c đ ộ tăng: - O(1): Hầế u h t các ch ỉịủươ th c a ch ng trình đ ềượựệộầ u đ c th c hi n m t l n hay nhi ề u nhấỉộ t ch m t vài l ầ⇒ờ n Th i gian ch ạủươ y c a ch ng trình là h ằố ng s . - O(logN): Thờ i gian ch ạ y c ủ a ch ươ ng trình là logarit, t ứ c là th ờ i gian ch ạ y c ủ a chươ ng trình ti ế n ch ậ m khi N l ớ n d ầ n. - O(N):Thờ i gian ch ạ y là tuy ế n tính. Đây là tình hu ố ng t ố i ư u cho m ộ t thu ậ t toán phả i x ử lý N d ữ li ệ u nh ậ p. - O(NlogN): Thờ i gian ch ạ y tăng d ầ n lên cho các thu ậ t toán mà gi ả i m ộ t bài toán bằ ng cách tách nó thành các bài toán con nh ỏ h ơ n, sau đó t ổ h ợ p các l ờ i gi ả i. - O(N2): Thờ i gian ch ạ y là b ậ c 2, tr ườ ng h ợ p này ch ỉ có ý nghĩa th ự c t ế cho các bài toán tươốỏờ ng đ i nh . Th i gian bình ph ươườ ng th ng tăng d ầ n trong các thu ậ t toán phảửấả i x lý t t c các c ặầửữệ p ph n t d li u (2 vòng l ặồ p l ng nhau). - O(N3): Thuậ t toán x ử lý các b ộủ ba c a các ph ầửữệ n t d li u (3 vòng l ặồ p l ng nhau) ⇒ ý nghĩa vớ i các bài toán nh ỏ . - O(2n) , O(n!), O(nn): Thờ i gian th ự c hi ệ n thu ậ t toán là r ấ t l ớ n do t ố c đ ộ tăng c ủ a các hàm mũ. 1.4. Cách tính độ ph ứ c t ạ p 8
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 1.4.1. Các quy tắ c c ơ b ả n a) Quy tắ c c ộ ng: Nế u T1(n) và T2(n) là thờ i gian th ự c hi ệ n 2 ch ươ ng trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thờ i gian th ự c hi ệ n c ủ a đo ạ n 2 ch ươ ng trình đó nố i ti ế p nhau là T(n)=O(max(f(n),g(n)) Ví dụ : L ệ nh gán x:=5 t ố n m ộ t h ằ ng th ờ i gian ≈ O(1). Lệ nh đ ọ c d ữ li ệ u READ(x) t ố n m ộ t h ằ ng ≈ O(1). Thờ i gian th ự c hi ệ n c ả 2 l ệ nh trên n ố i ti ế p nhau là O(max(1,1))=O(1). b) Quy tắ c nhân: Nế u T1(n) và T2(n) là thờ i gian th ự c hi ệ n 2 đo ạ n ch ươ ng trình P1, P2 và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thờ i gian th ự c hi ệ n c ủ a 2 đo ạ n ch ươ ng trình đó lồ ng nhau là T(n)=O(f(n).g(n)). c) Quy tắ c t ổ ng quát đ ể phân tích m ộ t ch ươ ng trình - Thờ i gian th ự c hi ệ n c ủ a m ỗ i l ệ nh gán, READ, WRITE là O(1) - Thờ i gian th ựệủộỗầựệượ c hi n c a m t chu i tu n t các l nh đ c xác đnh ịằ b ng quy t ắ c cộ ng ⇒ Th ờ i gian này là th ờ i gian thi hành m ộ t l ệ nh nào đó lâu nh ấ t trong chu ỗ i lệ nh. - Thờ i gian th ự c hiên c ấ u trúc IF là th ờ i gian l ớ n nh ấ t th ự c hi ệ n câu l ệ nh sau THEN hoặ c ELSE và th ờ i gian ki ể m tra đi ềệườờ u ki n, th ng th i gian ki ể m tra đi ềệ u ki n là O(1). - Thờ i gian th ựệ c hi n vòng l ặổ p là t ng (trên t ấảầặờ t c các l n l p) th i gian th ựệ c hi n thân vòng lặ p. N ế u th ờ i gian th ự c hi ệ n thân vòng l ặ p không đ ổ i thì th ờ i gian th ự c hiệ n vòng l ặ p là tích s ố l ầ n l ặ p v ớ i th ờ i gian th ự c hi ệ n thân vòng l ặ p. Ví dụ 3: Tính th ờ i gian th ự c hi ệ n đo ạ n ch ươ ng trình: Begin 1. for i:=1 to n-1 do {lặ p n-1 l ầ n}. 2. for j:=n downto i+1 do {thự c hi ệ n (n-i)l ầ n,m ỗ i l ầ n O(1) ⇒ 9
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 O((n-i).1)=O(n-i). 3. if a[j-1]>a[j] then begin đổ i ch ỗ (a[i],a[j]). 4. temp:=a[j-1]; O(1) 5. a[j-1]:=a[i]; 6. a[j]:=temp; end. End. n−1 n(n −1) Độ ph ứ c t ạ p T(n)=∑(n − i) = =O(n2). i=1 2 Chú ý: Độ ph ứ c t ạ p thu ậ t toán không ch ỉ ph ụ thu ộ c vào kích th ướ c, th ờ i gian mà còn phụ thu ộ c vào tính ch ấ t c ủ a d ữ li ệ u vào. Ví dụ 4: Thu ậ t toán s ắ p x ế p dãy s ố nguyên tăng d ầ n. N ế u dãy nh ậ p vào đã có th ứ t ự thì thờ i gian th ự c hi ệ n khác v ớ i khi nh ậ p vào dãy ch ư a có th ứ t ự 1.4.2. Độ ph ứ c t ạ p c ủ a các ch ươ ng trình đ ệ quy Vớ i các ch ươ ng trình ch ươ ng trình đ ệ quy, tr ướ c h ế t ta c ầ n thành l ậ p các ph ươ ng trình đệ quy, sau đó gi ả i các ph ươ ng trình đ ệ quy. Nghi ệ m c ủ a ph ươ ng trình đ ệ quy là thờ i gian th ự c hi ệ n ch ươ ng trình đ ệ quy đó. a)Thành lậ p ph ươ ng trình đ ệ quy: Phươ ng trình đ ệ quy là m ộươ t ph ng trình bi ểễố u di n m i liên h ệữ gi a T(n) và T(k) trong đó T(n) là thờ i gian th ự c hi ệ n v ớ i kích th ướ c d ữ li ệ u nh ậ p là n, T(k) là thờ i gian th ự c hi ệ n v ớ i kích th ướ c d ữ li ệ u nh ậ p là k, k<n. Để thành l ậ p ph ươ ng trình đ ệ quy ta căn c ứ vào ch ươ ng trình đ ệ quy. Ví dụ 5: Hàm tính giai th ừ a vi ế t b ằ ng gi ả i thu ậ t đ ệ quy sau: Function Giai_thua(n:Integer):Integer; Begin If n=0 then Giai_thua:=1 Else Giai_thua:=n*Giai_thua(n-1); 10
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 End. Gọ i T(n) : Th ờ i gian th ự c hi ệ n tính n! T(n-1) : Thờ i gian th ự c hi ệ n tính (n-1)! ⇒ ⇒ Trườ ng h ợ p n = 0 Th ự c hi ệ n m ộ t l ệ nh gán Giai_th ư a:=1 O(1) T(0)=C1 Trườ ng h ợ p n>0⇒ Gọ i đ ệ quy Giai_thua(n-1) t ố n T(n-1) th ờ i gian Sau khi có kế t qu ả c ủ a vi ệ c g ọ i đ ệ quy, ph ả i nhân k ế t qu ả đó v ớ i n và gán cho Giai_thua, thờ i gian th ự c hi ệ n phép nhân và phép gán là m ộ t h ằ ng C2. Vậ y ta có ph ươ ng trình đ ệ quy là : C1 nế u n=0 T(n)= T(n-1) + C2 nế u n>0. *Ví dụ 6: Xét th ủ t ụ c Mergesort sau: Function Mergesort(L:List;n:Integer):List; Var L1,L2:List; Begin If n=1 then return(L) Else Begin Chia L thành 2 nử a L1,L2 ,mỗ i n ử a có đ ộ dài n/2 Return(Merge(Mergesort(L1,n/2), Mergesort(L2,n/2)); End; End; Hàm Mergesort nhậ n m ộ t danh sách có đ ộ dài n và tr ả v ề m ộ t danh sách đ ẫ đ ượ c sắ p x ế p. Th ủ t ụ c Merge nh ậ n 2 danh sách đ ẫ đ ượ c s ắ p L1, L2 mỗ i danh sách có đ ộ dài n/2 trộ n chúng l ạớ i v i nhau đ ểượộ đ c m t danh sách g ồ m n ph ầửứự n t có th t ⇒ Thờ i gian th ự c hi ệ n Merge các danh sách có đ ộ dài n/2 là O(n). - Gọ i T(n) là th ờ i gian th ự c hi ệ n Mergesort 1 danh sách có n ph ầ n t ử T(n/2) là thờ i gian th ự c hi ệ n Mergesort 1 danh sách có n/2 ph ầ n t ử Ta có phươ ng trình đ ệ quy : 11
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 C1 nế u n =1 T(n)= 2T(n/2) + C2n nế u n>1 Trong đó: - C1 là thờ i gian ph ả i t ố n khi L có đ ộ dài b ằ ng 1 - Trườ ng h ợ p n>1 , th ờ i gian Mergesort đ ượ c chia làm 2 ph ầ n: + Phầ n g ọ i đ ệ quy Mergesort 1 danh sách có đ ộ dài n/2 là T(n/2) + Phầ n th ứ 2 bao g ồ m phép th ử n>1, chia danh sách thành 2 n ử a và Merge, ba thao tác này có thờ i gian không đ ổ i⇒ Thờ i gian th ự c hi ệ n là C2n b. Giả i ph ươ ng trình đ ệ quy: Phươ ng pháp truy h ồ i: Dùng đệ quy đ ể thay th ế b ấ t kì T(m) v ớ i m 1 đ ượ c thay th ếởểứủ b i bi u th c c a T(1). Vì T(1) luôn là hằ ng nên ta có công th ứ c c ủ a T(n) ch ứ a các s ố h ạ ng ch ỉ liên quan t ớ i n và các h ằ ng số . *Ví dụ 7: Gi ả i ph ươ ng trình: C1 nế u n=1 T(n)= 2T(n/2) + C2n nế u n>1  n  Ta có T ( n) = 2T  + C n  2  2   n  n  n  T ( n) = 22T  + C  + C n = 4T  + 2C n   4  2 2 2  4  2   n  n  n  T ( n) = 42T  + C  + 2C n = 8T  + 3C n   8  2 4 2  8  2  n  T ( n) = 2i T  + iC n  2i  2 k ⇒ ( ) = k ( ) + Giả s ử n=2 quá trình suy rộ ng này s ẽ k ế t thúc khi i=k T n 2 T 1 kC2 n k ⇒ ⇒ ( ) = + Vì 2 =n k=logn và vớ i T(1) = C1 T n C1n C2nlog n ) Vậ y th ờ i gian th ự c hi ệ n thu ậ t toán là O(nlogn) 12
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Đị nh lý: (Về nghi ệ m c ủ a ph ươ ng trình truy h ồ i) Cho a, b, c nguyên, dươ ng. Khi đó nghi ệ m c ủ a ph ươ ng trình truy h ồ i: b =  nÕ u n 1 T(n) =  n aT( ) + bn nÕ u n> 1, n = ck  c Có dạ ng: O(n) nÕ u a c 1.5. Thuậ t toán không đ ơ n đ ị nh đa th ứ c(Nodeterministic Polynomial NP) Vớ i nhi ề u bài toán t ố i ư u t ổ h ợ p v ẫ n ch ư a tìm đ ượ c các thuậ t toán đ ơ n đ ị nh chạ y trong th ờ i gian đa th ứ c, trong khi đó n ế u cho phép dùng thuậ t toán không đ ơ n đị nh thì lạ i d ễ dàng ch ỉ ra các thu ậ t toán ch ạ y trong th ờ i gian đa th ứ c. Ta xét bài toán sau đây: Bài toán xế p balô 0-1(KNASPACK) - Input: 1 balô có thể tích B; n đ ồ v ậ t có th ể tích a1,a2, ,an . - Output: Tìm nhóm đồ v ậ t đ ặ t v ừ a khít balô. *Cách 1: Phươ ng pháp Vét toàn b ộ c ầ n s ố phép th ử các kh ả năng là: 1 + 2 + n−1 + n ≈ n n Cn Cn Cn Cn 2 Độ ph ứ c t ạ p tính toán là O(2 ). *Cách 2: Diễ n t ả thu ậ t toán không đ ơ n đ ị nh ta c ầ n dùng 3 hàm: - CHOICE(a1,a2, an): Chọ n m ộ t trong s ố n giá tr ị . - SUCCESS: Nế u có m ộ t đi ề u ki ệ n th ỏ a mãn. - FAILURE: Nế u đi ề u ki ệ n không th ỏ a mãn. Khi đó bài toán trên có thể di ễ n đ ạ t nh ư sau: = Liệ u có th ể t ồ n t ạ i t ậ p ch ỉ s ố T⊂ {1,2, ,n} mà ∑ai B . i∈T Thuậ t toán: For i:=1 to n do xi:= CHOICE({0,1}); {phép toán lự a ch ọ n m ộ t trong 2 giá tr ị } n if ∑ xi ai =B then SUCCESS i=1 else FAILURE; 13
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Giá phả i tr ả v ề th ờ i gian : + Trườ ng h ợ p SUCCESS: Th ờ i gian ít nh ấ t đ ể th ự c hi ệ n SUCCESS . + Trườ ng h ợ p FAILURE: Chính là th ờ i gian t ố i đa. Thuậ t toán trên tr ở thành không đ ơ n đ ị nh đa th ứ c, s ố phép tính th ự c hi ệ n là 2*n+2. Bài toán Xế p balô m ở r ộ ng (Tên tr ộ m tham lam) Input: Mộ t ba lô có th ể tích B, n đ ồ v ậ t có th ể tích: a1, a2, an , giá trị t ươ ng ứ ng c ủ a các đ ồ v ậ t là: p1, p2, pn ∑ ai ≤ b ∑ p Ouput: Có tồ n t ạ i t ậ p T⊂ {1,2, ,n} sao cho và i đạ t max ?. i∈T i∈T Bài toán xế p balô giá tr ị nguyên: Input: Mộ t ba lô có th ể tích B, n đ ồ v ậ t có th ể tích: a1, a2, an , giá trị t ươ ng ứ ng c ủ a các đ ồ v ậ t là: p1, p2, pn Số l ượ ng m ỗ i lo ạ i đ ồ v ậ t là không h ạ n ch ế , xi nguyên là số l ượ ng lo ạ i đồ v ậ t i. n n ≤ Ouput: Tìm nhóm đồ v ậ t tho ả mãn ∑ai xi B và ∑ pi xi đạ t max ?. i=1 i=1  Mố i quan h ệ v ề tính đa th ứ c gi ữ a mô hình Turing và mô hình t ự a Algol Đị nh lí 1: Thuậ t toán trên máy Turing là đa th ứ c thì thu ậ t toán trên t ự a Algol t ươ ng ứng cũng là đa th ứ c, ng ượ c l ạ i ch ư a ch ắ c. Ví dụ 8: Tính S=2 2n . x:=2; for i:=1 to n do x:=x*x; Ta có i:=1 : x2 i:=2 : x2 * x2 = x 22 i:=3 : x4 * x4 = x 23 − − i:=n : x 2n 1 * x 2n 1 = x 2n . 2n 2n ≈ n + Trên máy Turing : Dữ li ệ u vào 2 mã nhị phân là: [log2 2 ] +1 2 , độ ph ứ c t ạ p là O(2n) + Thuậ t toán t ự a Algol : Đ ộ ph ứ c t ạ p 2n+1 ≈ O(n) . Đị nh lí 2 : Nế u thu ậ t toán t ự a Algol là đa th ứ c và trong thu ậ t toán ch ỉ có các phép toán cơ b ả n( +, -, *, /, so sánh,gán, AND, OR ) và d ữ li ệ u vào ph ả i có đ ộ ph ứ c t ạ p 14
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 đa thứ c theo quan ni ệ m 2(đ ộ dài mã) thì thu ậ t toán (trên máy Turing) t ươ ng ứ ng là đa thứ c. Ví dụ : Input: Dãy s ố a1,a2, an, n. Output: Sắ p x ế p theo chi ề u gi ả m d ầ n. For i:=1 to n do Begin j:=i; for k:=i+1 to n do if ak>aj then j:=k; TAM:=ai; ai:=aj; aj:=TAM; End; Độ ph ứ c t ạ p tính toán: - Dữ li ệ u: n+1 ≈ O(n). - Bộ nh ớ : (n+1)+4=n+5 ≈ O(n) (vào) (i,j,k,tam) n −1 - Thờ i gian: 2((n-1)+(n-2)+ +2+1)+4(n-1) = 2n. +4(n-1) =n2+3n-4 ≈ O(n2). 2 ⇒ Thuậ t toán là đa th ứ c ⇒ Thự c t ế gi ả i đ ượ c. 1.5.1. Sự phân l ớ p các bài toán. Vớ i m ộ t bài toán cho tr ướ c có 2 kh ả năng x ả y ra: + Không giả i đ ượ c ho ặ c + Giả i đ ượ c b ằ ng thu ậ t toán. - Trườ ng h ợ p bài toán gi ả i đ ượ c b ằ ng thu ậ t toán cũng chia làm 2 lo ạ i: + Thựếảượượể c t gi i đ c: Đ c hi u là thu ậ t toán x ử lý trong th ờ i gian đ ủ nhanh, thự c t ế cho phép, đó là thu ậ t toán có đ ộ ph ứ c t ạ p th ờ i gian là đa th ứ c. +Thựế c t khó gi ảượể i: Đ c hi u là thu ậ t toán x ử lý trong nhi ềờ u th i gian, th ựế c t khó chấ p nh ậ n, đó là thu ậ t toán có đ ộ ph ứ c t ạ p th ờ i gian là trên đa th ứ c (hàm mũ). Do đó, ta có sự phân l ớ p các bài toán do 2 tác gi ả Cook và Karp đ ề xu ấ t năm 1970- 1971 như sau: - P : Là lớ p các bài toán có th ể gi ả i đ ượ c b ằ ng thu ậ t toán đ ơ n đ ị nh trong th ờ i gian đa thứ c (Deterministic polynomial). 15
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Ví dụ : Bài toán v ề tính liên thông c ủồịểảợờậ a đ th có th gi i đu c nh thu t toán v ớờ i th i gian tính là O(n2)⇒ Thuộ c l ớ p P NP : Là lớ p các bài toán có th ể gi ả i đ ượ c b ằ ng thu ậ t toán không đ ơ n đ ị nh trong thờ i gian đa th ứ c. Hay, là l ớ p các bài toán mà m ọ i nghi ệ m gi ả đ ị nh đ ề u có th ể đượ c ki ể m ch ứ ng trong th ờ i gian đa th ứ c (Nondeterministic polynomial) Ví dụ : Bài toán ki ể m tra m ộ t dãy đ ỉ nh c ủ a đ ồ th ị G có là chu trình Hamilton hay không có thể th ự c hi ệ n sau th ờ i gian đa th ứ c ⇒ Thuộ c l ớ p NP ⇒ P ⊆ NP Nhưệ ng hi n nay ch ưứ a ch ng minh đ ượ c P là t ậ p con th ựựủ c s c a NP, v ấề n đ P = NP? hiệộ n là m t trong s ốấềởổếấ các v n đ m n i ti ng nh t và cũng đ ắ t giá nh ấ t trong Toán họ c và trong Tin h ọ c lý thuy ế t. 1.5.2. Khái niệ m “d ẫ n v ề đ ượ c” (Phép quy dẫ n): Cho hai bài toán A, B Đị nh nghĩa1: Bài toán A đượ c g ọ i là “d ẫ n v ề đ ượ c” bài toán B sau th ờ i gian đa thứ c n ế u có m ộ t thu ậ t toán đa th ứ c đ ể gi ả i bài toán B thì cũng có m ộ t thu ậ t toán đa thứ c đ ể gi ả i bài toán A. Nghĩa là: Bài toán B “khó hơ n” bài toán A hay A “d ễ h ơ n” B hay A là tr ườ ng h ợ p riêng củ a B. Kí hi ệ u A ∝ B. Phép quy dẫ n có tính ch ấ t b ắ c c ầ u: A∝ B và B∝ C⇒ A∝ C. Tư t ưở ng quy d ẫ n đã gi ả i thích vai trò quan tr ọ ng c ủ a l ớ p bài toán P. N ế u ta có bài toán A thuộ c l ớ p P và m ộ t bài toán B có th ể quy d ẫ n v ề A, th ế thì B cũng thu ộ c vào P. Nghĩa là P là đóng đố i v ớ i phép quy d ẫ n. Đị nh nghĩa 2 : Bài toán A đượ c g ọ i là “khó t ươ ng đ ươ ng” bài toán B n ế u A∝ B và B ∝ A. Kí hiệ u A ~ B. 1.5.3 Lớ p bài toán NP - khó (NP - hard) và NP - đầ y đ ủ (NP – Complate) a) Bài toán quyế t đ ị nh: Bài toán quyế t đ ị nh là bài toán mà đ ầ u ra ch ỉ có th ể là “Yes” hoặ c “No” (Đúng/sai, 0/1, ch ấ p nh ậ n/t ừ ch ố i). Ví dụ : Bài toán v ề tính nguyên t ố : ” H ỏ i s ố nguyên n có là s ố nguyên t ố hay không?”. Khi đó ta có n = 23 là bộ d ữ li ệ u vào “Yes”, còn n = 24 là b ộ d ữ li ệ u vào “ No” c ủ a bài toán. b) Bài toán NP – Khó(NP – Hard) Bài toán A đượọ c g i là NP- khó n ếưồạậ u nh t n t i thu t toán đa th ứểả c đ gi i bài toán A thì kéo theo sự t ồ n t ạ i thu ậ t toán đa th ứ c đ ể gi ả i m ọ i bài toán trong NP. 16
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Hay: A là NP – Khó nế u nh ư B∝ A, vớ i m ọ i bài toán B ∈ NP Mộ t cách không hình th ứểằế c, có th nói r ng n u ta có th ểảượộ gi i đ c m t cách hi ệ u quả m ộ t bài toán NP – Khó c ụ th ể thì ta cũng có th ể gi ả i hi ệ u qu ả b ấ t kỳ bài toán nào trong NP bằ ng cách s ử d ụ ng thu ậ t toán gi ả i bài toán NP-Khó nh ư là m ộ t ch ươ ng trình con. c) Bài toán NP - đầ y đ ủ (NP – complete, NPC) Mộ t bài toán quy ế t đ ị nh A đ ượ c g ọ i là NP - đ ầ y đ ủ n ế u nh ư i) A là bài toán trong NP, ii) Mọ i bài toán trong NP đ ề u có th ể quy d ẫ n v ề A. Lư u ý: Khái ni ệ m NP - đ ầủỏ y đ đòi h i bài toán nh ấếảạếị t thi t ph i có d ng quy t đ nh. Ta có bứ c tranh t ạ m th ờ i đ ầ y đ ủ v ề phân l ớ p các bài toán trên hình sau: Hình 2: Sự phân l ớ p các bài toán c) Phươ ng pháp ch ứ ng minh m ộ t bài toán là NP - đ ầ y đ ủ - Cách 1: Theo đị nh nghĩa (r ấ t khó). NP NP-khó - Cách 2: áp dụ ng b ổ đ ề sau: Bổ đ ề: Giả s ử bài toán A là NP - đ ầNPC y đ ủ , bài toán B thu ộ c NP và bài toán A quy d ẫ n về B. Khi đó bài toán B cũng là NP - đ ầ y đ ủ . P Ví dụ 9: Bài toán x ế p balô(KNASPACK)∈ NPC⇒ Chứ ng minh bài toán l ậ p l ị ch ∈ NPC. °Bài toán lậ p l ị ch (Bài toán PHẠ T): Input: Có n công việ c x ử lý trên m ộ t máy. ri: Thờ i đi ể m b ắ t đ ầ u công vi ệ c x ử lý i di : Hạ n đ ị nh hoàn thành công vi ệ c i. ti : Thờ i gian x ử lý công vi ệ c i, ti ≤ di-ri. bi : Thờ i gian b ắ t đ ầ u x ử lý. ci : Thờ i gian k ế t thúc công vi ệ c i, ti=ci-bi 17
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 ≤ nế u ci di , công việ c i là x ử lý đúng h ạ n. nế u ci>di , công việ c i là x ử lý quá h ạ n(b ị ph ạ t). wi : Tiề n ph ạ t. Output: Hãy sắế p x p các công vi ệ c theo m ộứựấịể t th t nh t đ nh đ theo đó ch ờế đ n lượ t x ử lý, sao cho l ượ ng ti ề n ph ạ t là ít nh ấ t. ≤ Kí hiệ u Ui = 0 nế u ci di (đúng hạ n) 1 nế u ci>di (quá hạ n) n Khi đó yêu cầ u : ∑ UiWi → min i = 1 n Ta có thể vi ế t bài toán trên ng ắ n g ọ n nh ư sau : n1 ∑ UiWi . Kí hiệ u là PH Ạ T. i = 1 Bài toán này rõ ràng là giả i đ ượ c b ằ ng ph ươ ng pháp “vét toàn b ộ ”. Nh ư ng th ự c t ế khó giả i vì nó thu ộ c l ớ p NP_đ ầ y đ ủ . Để ch ứ ng minh bài toán “PH Ạ T” là NP - đ ầ y đ ủ , ch ỉ c ầ n ch ứ ng minh r ằ ng bài toán KNAPSACK∝ PHẠ T vì ta đã bi ế t KNAPSACK là NP_đ ầ y đ ủ . Nói m ộ t cách khác KNAPSACK là trườ ng h ợ p riêng c ủ a PH Ạ T. Nhắ c l ạ i bài toán KNAPSACK: Input: n đồ v ậ t v ớ i th ể tích a1,a2, an cầ n nhét vào balô có th ể tích B. Output: Tìm nhóm đồ v ậ t có th ể nhét v ừ a khít balô trên. = ( ∃ T⊆ {1,2, ,n} mà ∑ai B .) i∈T a)Để ch ứ ng minh KNAPSACK∝ PHẠ T tr ướ c h ế t ta di ễ n đ ạ t nó b ằ ng ngôn ngữủ c a bài toán PH Ạụểỗậở T. C th m i v t i KNAPSACK đ ượ c xem là m ộ t công việ c trong PH Ạ T, chúng đ ồ ng th ờ i đ ượ c nh ậ p vào h ệ th ố ng. M ọ i công việ c có h ạ n đ ị nh nh ư nhau và b ằ ng B. Th ờ i gian ti thự c hi ệ n công vi ệ c i b ằ ng tiề n ph ạ t wi và bằ ng th ể tích ai củ a v ậ t. Tóm lạ i ta có th ể bi ể u di ễ n bài toán nh ư sau: Input: - n công việ c đ ồ ng th ờ i đ ượ c x ử lý ri =0, ∀ i=1,2, ,n. ≤ ≤ - mỗ i công vi ệ c i (1 i n ) đượ c bi ế t di=B, ti=wi=ai, ∀ i=1,2, ,n. - máy làm việ c liên t ụ c cho đ ế n khi m ọ i công vi ệ c đ ượ c x ử lý xong. - tạ i m ỗ i th ờ i đi ể m máy ch ỉ x ử lý đ ượ c m ộ t công vi ệ c. - khi đang xử lý công vi ệ c i, không đ ượ c phép ng ắ t nó đ ể th ự c hi ệ n m ộ t công việ c khác. 18
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Output: Hãy lậ p l ị ch đ ể máy x ử lý các công vi ệ c sao cho l ượ ng ti ề n ph ạ t là ít nh ấ t n ∑ UiWi là nhỏ nh ấ t. i = 1 b) Chứ ng minh: GiảượẠằ i đ c PH T b ng thu ậ t toán đ ơị n đnh đa th ứ c thì cũng gi ảượ i đ c KNAPSACK bằ ng thu ậ t toán đ ơ n đ ị nh đa th ứ c và ng ượ c l ạ i. n n °Giả s ử gi ả i đ ượ c PH Ạ T t ứ c là lch ị bi ể u mà ∑ WiUi là nhỏ nh ấ t, v ậ y thì: ∑ i=1 i=1 n = = ∑ bi ∑ ai ∑ wi WiUi=∑ ai -b. i=1 r =0 b d =b -b i i n n ⊆ ∑ a Suy ra ∃ S {1,2, ,n} mà ∑ UiWi = i =∑ a -b ∈ i i = 1 i S i=1 n ∑ a ∑ ai ∑ai Hay b= i - ∈ = vớ i T={1,2, ,n}- S. Nh ư v ậ y KNAPSACK đã gi ả i i=1 i S i∈T đượ c. = °Ngượ c l ạ i, gi ả s ử KNAPSACK đã gi ả i đ ượ c, t ứ c là ∃ T⊆ {1,2, ,n} mà ∑ai b i∈T hay n n n n n ∑ai ∑ a ∑ ai ∑ a ∑ ⇒ ∑ ∑ a = i - ∈ =b, như v ậ y i - UiWi =b UiWi = i -b , đây là lượ ng i∈T i=1 i S i=1 i = 1 i = 1 i=1 tiề n nh ỏ nh ấ t và PH Ạ T đã gi ả i đ ượ c. n *Chú ý: Nếấả u t t c n công vi ệề c đ u quá h ạ n thì l ượềạớấ ng ti n ph t l n nh t là ∑ ai . i=1 d) Mộ t s ố bài toán đã đ ượ c ch ứ ng minh là NP – khó , NP - đ ầ y đ ủ Để ch ứ ng minh m ộ t bài toán nào đó là NP-đ ầ y đ ủ (NP-khó) công vi ệ c khó khăn nh ấ t là tìm đượ c m ộ t bài toán NP-đ ầ y đ ủ có th ể quy d ẫ n v ề nó. Do đó ta c ầ n bi ế t thêm về nh ữ ng bài toán đ ẫ đ ượ c ch ứ ng minh là NP-đ ầ y đ ủ , cho đ ế n nay danh m ụ c các bài toán NPC trong các lĩnh vự c đa d ạ ng :Logic Bool, đ ồ th ị , s ố h ọ c, l ậ p l ị ch, trò ch ơ i, otomat đã lên đế n hàng nghìn . Sau đây là m ộ t s ố bài toán đã đ ượ c ch ứ ng minh là NPC:  Bµi to¸n 3SAT. 19
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Xét các biểứ u th c Bool là h ộủ i c a các m ệềỗệềểủ nh đ mà m i m nh đ là tuy n c a đúng 3 toán hạ ng, m ỗ i toán h ạ ng là m ộ t bi ế n Bool (x) ho ặ c ph ủ đ ị nh c ủ a nó (x) . Biể u th ứ c Bool có dạ ng nh ư v ậ y đ ượ c g ọ i là công th ứ c 3-CNF (dạ ng chu ẩ n t ắ c h ộ i 3 – conjunctive normal form). Ví dụ . Bi ể u th ứ c (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ z ∨ u) Là mộ t 3-CNF ch ứ a 4 bi ế n Bun x, y, z, u. Bài toán 3-SAT: Cho mộ t công th ứ c 3-CNF, h ỏ i r ằ ng có t ồ n t ạ i m ộ t b ộ giá tr ị c ủ a các biế n sao cho bi ể u th ứ c nh ậ n giá tr ị TRUE hay không?  Bài toán về bè l ớ n nh ấ t c ủ a đ ồ th ị (MaxClique): Cho đồị th vô h ướ ng G = (V, E). M ộồị t đ th con đ ầủủồịượọ y đ c a đ th G đ c g i là bè (clique). Ta gọ i kích th ướủ c c a bè là s ốỉủ đ nh c a nó. Bè c ủồịớ a đ th G v i kích th ướ c lớ n nh ấ t đ ượ c g ọ i là bè l ớ n nh ấ t(MaxClique) Ví dụ : 3 1 5 2 4 Hình 3 : a)MaxClique kích thướ c 3 b)MaxClique kích thướ c 4 Bài toán Clique: Cho đồ th ị vô h ướ ng G = (V, E) và s ố nguyên k. H ỏ i đ ồ th ị G có chứ a bè v ớ i kích th ướ c hay không ? .Bài toán phủ đ ỉ nh(Vertex Cover- VC) : Ta gọ i m ộ t ph ủ đnh ỉ c ủ a đ ồ th ị vô h ướ ng G=(V, E) là mộ t t ậ p con các đ ỉ nh c ủ a đ ồ th ị S ⊆ V sao cho mỗ i c ạ nh c ủ a đ ồ th ị có ít nhấộầ t m t đ u mút trong S. Ta g ọ i kích th ướủộủỉ c c a m t ph đ nh là s ốỉủ đ nh c a nó Bài toán VC : Cho đồ th ị vô h ướ ng G=(V, E) và s ố nguyên k. H ỏ i có ph ủ đ ỉ nh v ớ i kích thướ c k hay không? 20
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Ví dụ : y x b c d w z v e f g u a H×nh 4 a) Phủ đ ỉ nh v ớ i kích th ướ c 2 b) Ph ủ đ ỉ nh v ớ i kích th ướ c 3 1.6. Thuậ t toán x ấ p x ỉ (Heuristic) 1.6.1. Các khái niệ m Ngườ i ta cho r ằ ng ngày nay máy tính v ớ i t ố c đ ộ r ấ t l ớ n, không c ầ n quan tâm nhi ề u tớ i thu ậ t toán nhanh nh ư ng v ớ i s ự ki ể m ch ứ ng sau đây: Bài toán x ử lý v ớ i n đ ố i tượ ng, có 3 thu ậ t toán v ớứứạ i 3 m c ph c t p khác nhau, sau 1 gi ờửẽịậ x lý s ch u 3 h u quả khác nhau. Thuậ t Độ ph ứ c Xử lý/1 gi ờ toán tạ p A O(n) 3,6 triệ u đ ố i tượ ng B O(nlog2n) 0,2 triệ u đ ố i tượ ng Trong khi đó C O(2n) 21 đố i t ượ ng nhiề u bài toán có ý nghĩa th ự c t ế l ạ i thu ộ c l ớ p các bài toán NPC và r ấ t quan tr ọ ng. Nế u m ộ t bài toán là NPC ta ắ t không tìm m ộ t thu ậ t toán th ờ i gian đa th ứ c . Vì v ậ y, có hai cách tiế p c ậ n đ ể có th ể kh ắ c ph ụ c tính NPC: - Nế u d ữ li ệ u đ ầ u vào th ự c t ế là nh ỏ thì m ộ t thu ậ t toán có th ờ i gian thự c hi ệ n hàm mũ có th ể hoàn toàn tho ả mãn. - Tìm các giả i pháp g ầ n t ố i ư u trong th ờ i gian đa th ứ c. Mộậ t thu t toán tr ảề v các k ếủầốưượọ t q a g n t i u đ c g i là m ộậ t thu t toán x ấỉ p x . Ta có các khái niệ m sau đây: • Thuậ t toán t ố i ư u nhanh: Là thuậ t toán tìm nghi ệ m t ố i ư u, nh ư ng nhanh (đ ộ ph ứ c tạ p th ờ i gian là đa th ứ c). • Thuậ t toán t ố i ư u ch ậ m: Là thuậ t toán tìm nghi ệ m t ố i ư u nh ư ng ch ậ m (đ ộ ph ứ c tạ p th ờ i gian là hàm mũ). 21
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 • Thuậ t toán x ấ p x ỉ nhanh (Fasf Approximation Algorithms). Là các thuậ t toán tìm ra nghiệ m g ầ n đúng c ủ a bài toán v ớ i đ ộ chính xác nào đó nh ư ng đ ủ nhanh. Thu ậ t toán như v ậ y còn đ ượ c g ọ i là “Thu ậ t toán x ấ p x ỉ đa th ứ c”. Ví dụ 10: Bài toán phủ đ ỉ nh t ố i ư u Input: Cho đồ th ị vô h ướ ng G = (V, E). Output: Tìm phủ đ ỉ nh t ố i ư u( Ph ủ đ ỉ nh có kích th ứơ c c ự c ti ể u) . Bài toán VC tìm ra phủ đ ỉ nh có kích c ỡ c ự c ti ể u là NPC. Do đó khó có th ể tìm ra 1 phủỉốưư đ nh t i u nh ng không quá khó đ ể tìm ra m ộủỉầốư t ph đ nh g n t i u. Sau đây là mộậ t thu t toán x ấỉếủộủỉ p x cho k t q a là m t ph đ nh có kích c ỡ không l ớ n hơ n 2 l ầ n kích c ỡ m ộ t ph ủ đ ỉ nh t ố i ư u trong th ờ i gian đa th ứ c: Procedure Approx _VertexCover; Begin C:= φ ; { C - tậ p ph ủ g ầ n t ố i ư u} E:= Tậ p c ạ nh c ủ a đ ồ th ị G; While E ≠ φ do Begin Chọ n (u, v) là m ộ t c ạ nh tuỳ ý c ủ a E; C:= C ∪ {u, v}; {Kế t n ạ p hai đ ỉ nh u, v vào ph ủ đ ỉ nh C}; Gỡ b ỏ kh ỏ i E m ọ i c ạ nh liên thu ộ c v ớ i u ho ặ c v; End; Return(C); End; 22
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 b c d b c d a e f g a e f g a) Đồ th ị G b) Ch ọ n c ạ nh (b, c), g ỡ b ỏ (b,a),(c,e),(c,d) Hình 5 b c d b c d a e f g a e f g c) Chän tiÕp (e,f), gì bá (e,d),(d,f) d) Chän c¹nh (d,g), E = φ Kế t qu ả : Ph ủ đ ỉ nh C={b, c, d, e, f, g} g ầ n t ố i ư u có kích th ướ c 6. ( Phủ đ ỉ nh t ố i ư u {b, e, d} có kích th ướ c 3) 1.6.2. Thuậ t toán ε - xấ p x ỉ tuy ệ t đ ố i Cho P là bài toán cự c đ ạ i hóa: Gọ i H là th ủ t ụ c Heuristic, thu ậ t toán tìm m ộ t nghi ệ m nào đó cho P Kí hiệ u OPT(I) là nghi ệ m t ố i ư u c ủ a bài toán P đ ố i v ớ i th ể hi ệ n I. Kí hiệ u H(I) là nghi ệ m g ầ n đúng c ủ a P do thu ậ t toán H tìm ra. Cho ε >0, thủ t ụ c Heuristic H đ ượ c g ọ i là thu ậ t toán ε - xấ p x ỉ tuy ệ t đ ố i khi và ch ỉ khi OPT(I) − H (I) ≤ ε cho mọ i th ể hi ệ n I c ủ a bài toán P (I: instance) v ớ i ∀ bộ d ữ li ệ u. Ví dụ 11: Bài toán lư u tr ữ t ố i đa s ố l ượ ng ch ươ ng trình (maximum program stored) Input : - n chươ ng trình v ớ i dung l ượ ng nh ớ (đ ộ dài) d1,d2, , dn - Hai băng nhớ v ớ i dung l ươ ng (đ ộ dài) m ỗ i băng là L. Output: Hãy ghi các chươ ng trình lên 2 băng nh ớớốượố v i s l ng t i đa, m ỗươ i ch ng trình chỉ đ ượ c ghi trên m ộ t băng nh ớ . 23
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Bài toán này đã đượ c ch ứ ng minh là NP - đ ầ y đ ủ . Vì v ậ y viêc tìm thu ậ t toán đa th ứ c cho nó là ít hi vọ ng. Ngườ i ta đã dùng gi ả i pháp tìm thu ậ t toán x ấ p x ỉ nhanh cho phép tìm đ ượ c nghi ệ m gầ n đúng c ủ a nó nh ư ng ch ỉ m ấ t th ờ i gian đa th ứ c. Sau đây là thuậ t toán 1- x ấỉệố p x tuy t đ i: Cho k ếảệốư t qu nghi m t i u và nghi ệầ m g n đúng chỉ chênh nhau có 1. Thuậ t toán 1- x ấ p x ỉ tuy ệ t đ ố i: Procedure XXTD1; Begin 1. Sắ p x ế p các ch ươ ng trình theo th ứ t ự tăng d ầ n c ủ a d1,d2, , dn; 2. i:=1; For j:=1 to 2 do Begin dodai:=0; While (dodai+di ≤ L) and (i≤ n) do Begin ; dodai:= dodai+di; i:=i+1; End; End; End; Chú ý: Mụ c đích mu ố n ch ỉ trên 2 băng nh ớ có đ ộ dài L mà l ư u tr ữ đ ượ c t ố i đa các chươ ng trình. Theo suy nghĩ thông th ườ ng thì hãy ư u tiên các ch ươ ng trình có đ ộ dài ngắơậầ n h n, vì v y đ u tiên là s ắế p x p các ch ươ ng trình theo th ứựầ t tăng d n các đ ộ dài củ a chúng. Ti ế p theo l ầượế n l t x p theo th ứự t này lên t ừ ng băng nh ớộ m t. Do 2 băng nhớ có đ ộ dài nh ư nhau nên dùng băng nào tr ướ c cũng đ ượ c . Theo thu ậ t toán trên thì dùng băng 1 trướ c. Bi ế n “dodai” ghi l ạ i t ổ ng đ ộ dài băng nh ớ dùng đ ể l ư u các chươ ng trình. Bài toán này còn đượ c g ọ i là bài toán c ắ t n đo ạ n s ắ t t ừ 2 thanh s ắ t có cùng đ ộ dài L sao cho số l ượ ng đo ạ n s ắ t c ắ t ra là nhi ề u nh ấ t (Ch ặ t s ắ t - Cutting problem). Chứ ng minh |OPT(I) - H(I)|≤ 1 24
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Đặ t k = H(I) là nghi ệ m c ủ a thu ậ t toán Heurtstic ⇒ k là số l ượ ng ch ươ ng trình đ ượ c lư u tr ữ trên 2 băng nh ớ theo cách s ắ p đ ặ t c ủ a thu ậ t toán x ấ p x ỉ trên. - Gọ i p là s ốượươ l ng ch ng trình đ ượ c ghi trên 1 băng nh ớộằ có đ dài b ng 2 băng nói trên p ≤ ≤ ≤ Như v ậ y k OPT(I) p và ∑ di 2L (1) i=1 Ta chứ ng minh OPT(I) − H (I) ≤ 1 ⇔ OPT(I) – k ≤ 1 ⇔ OPT(I) ≤ k+1 (2) Theo (1) thì chỉ c ầ n ch ứ ng minh p≤ k+1 là đủ vì khi đó OPT(I) ≤ p ≤ k+1. Chứ ng minh b ằ ng ph ả n ch ứ ng: k+2 p ⇔ ⇔ ≤ ≤ Giả s ử p>k+1 p ≥ k+2 ∑ di ∑ di 2L (3). i=1 i=1 Gọ i m là s ốượươ l ng ch ng trình đ ượ c ghi trên m ộ t băng theo thu ậ t toán x ấỉ p x trên. m m + > ⇒ + > Khi đó : ∑di dm+1 L ∑di dk +1 L (4) i=1 i=1 k k + > ⇒ + > Tươ ng t ự trên băng nh ớ 2 : ∑ di d k+1 L ∑ di d k+2 L (5) i=m+1 i=m+1 k +2 > ⇒ ⇒ ≤ + Từ (4),(5) ta có : ∑ di 2L mâu thuẫ n v ớ i (3) p k 1 (đpcm). i=1 Độ ph ứ c t ạ p th ờ i gian c ủ a thu ậ t toán: Thờ i gian x ử lý c ủ a thu ậ t toán x ấ p x ỉ trên là O(nlog2n) (chủ y ế u là ph ầ n s ắ p xế p các ch ươ ng trình theo th ứ t ự c ủ a đ ộ dài). Trong khi thu ậ t toán chính xác ph ả i cầ n có th ờ i gian hàm mũ, mà hi ệ u qu ả là 2 nghi ệ m ch ỉ chênh nhau có 1. N ế u nh ữ ng bài toán đượ c gi ả i t ố t nh ư ví d ụ trên thì dùng gi ả i pháp ε - xấ p x ỉ tuy ệ t đ ố i. Nh ư ng không phả i khi nào cũng suôn s ẻ nh ư v ậ y vì các thu ậ t toán ε - xấ p x ỉ tuy ệ t đ ố i tìm đượ c không nhi ề u. Hiệ n nay ph ầ n l ớ n các bài toán NP- đ ầ y đ ủ thì vi ệ c tìm thu ậ t toán ε - xấ p x ỉ tuyệ t đ ố i cho chúng cũng l ạ i là NP- đ ầ y đ ủ . Ch ẳ ng h ạ n nh ư bài toán x ế p balô (KNAPSACK), bài toán ngườ i bán hàng (Traverling Salesman Problem), bài toán MaxClique Chính vì lẽ đó ng ườ i ta d ẫ n ra khái ni ệ m y ế u h ơ n g ọ i là Thu ậ t toán ε - xấ p x ỉ . 1.6.3.Thuậ t toán ε - xấ p x ỉ Cho P là bài toán cự c đ ạ i hóa. Gọ i H là th ủ t ụ c Heuristic, thu ậ t toán x ấ p x ỉ tìm m ộ t nghi ệ m nào đó cho P. 25
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Kí hiệ u OPT(I) là nghi ệ m t ố i ư u c ủ a bài toán P đ ố i v ớ i th ể hi ệ n I (Instance). H(I) là nghiệ m g ầ n đúng c ủ a P do H tìm ra. Thủ t ụ c Heuristic H đ ượ c g ọ i là thu ậ t toán ε - xấ p x ỉ khi và ch ỉ khi: OPT(I) − H (I) ≤ ε cho ∀ I. OPT(I) Ví dụ 12: Bài toán xế p balô giá tr ị nguyên (Interger - Valued Knapsack) Input: Mộ t ba lô có th ể tích B, n đ ồ v ậ t có th ể tích: a1, a2, an , giá trị t ươ ng ứ ng c ủ a các đ ồ v ậ t là: p1, p2, pn Số l ượ ng m ỗ i lo ạ i đ ồ v ậ t là không h ạ n ch ế , xi nguyên là số l ượ ng lo ạ i đ ồ vậ t i. n n ≤ Ouput: Tìm nhóm đồ v ậ t tho ả mãn ∑ai xi B và ∑ pi xi đạ t max ?. i=1 i=1 n n   ≤ ∈ ≤ ≤ ≤ B Tóm tắ t: ∑ xi pi → Max vớ i ∑ xi ai B, xi Z,0 xi bi . Ở đây bi   , điề u này i=1 i=1 wi   B  là hiể n nhiên vì   chính là số nguyên đ ồ v ậ t có cùng th ể tích ai có thể nhét wi  đượ c vào ba lô. Trườ ng h ợ p bi=1 ∀ i thì vấ n đ ề trên g ọ i là bài toán x ế p balô 0-1, t ứ c là ch ỉ đ ượ c x ế p nhiề u nh ấ t là 1 đ ồ v ậ t vào balô (0-1 Knapsack) Bài toán này đã đượ c ch ứ ng minh là NP- đ ầ y đ ủ . Vì v ậ y vi ệ c tìm thu ậ t toán đa th ứ c cho nó là rấ t ít hi v ọ ng. Ng ườ i ta đã th ử tìm thu ậ t toán x ấ p x ỉ tuy ệ t đ ố i (nhanh) cho nó như ng cũng không thành công vì vi ệ c tìm m ộ t thu ậ t toán nh ư v ậ y cũng l ạ i là NP- khó. Sau đây là thuậ t toán 1/2 - x ấ p x ỉ cho bài toán x ế p balô tr ị nguyên: Procedure XAPXI12; Begin 1) sắ p x ế p t ỉ s ố pi/ai , i=1,2, ,n theo thứ t ự gi ả m d ầ n; 2) T:=0; for i:=1 to n do begin xi:=[(B-T)/ai]; T:=T+xiai; 26
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 End; End. Chứ ng minh: B   ≤ B ≤ - Vớ i m ỗ i th ể hi ệ n I ta có OPT(I) p1. và p1.  H (I) a1 a1    − B < B Mặ t khác B  .a1 (vì nế u ng ượ c l ạ i thì d ẫ n đ ế n vô lý) a1  2     B − B   B a1   B OPT(I) − H (I) H (I) a  a  1 Khi đó = 1− ≤ 1− 1 = 1 = 2 = . OPT(I) OPT(I) B B B 2 a1 Độ ph ứ c t ạ p th ờ i gian c ủ a thu ậ t toán: Thờ i gian x ửậ lý thu t toán x ấỉ p x trên ch ỉ là O(nlogn) (ch ủếầắếỉ y u là ph n s p x p t số pi/ai), trong khi nế u dùng thu ậ t toán chính xác ph ả i c ầ n th ờ i gian hàm mũ. Ngoài bài toán xế p balô (Knapsack) trên, hi ệ n nay ng ườ i ta đã tìm đ ượ c thu ậ t toán ε - xấ p x ỉ cho nhi ề u bài toán khác, đ ặ c bi ệ t trong các v ấ n đ ề l ậ p l ị ch. Tuy vậ y v ớ i nhi ề u bài toán NP- đ ầ y đ ủ thì vi ệ c tìm thu ậ t toán ε - xấ p x ỉ cho chúng cũng lạ i là NP- đ ầ y đ ủ . Ch ẳ ng h ạ n nh ư bài toán Traveling Salesman Problem(TSP), bài toán quy hoạ ch nguyên (Integer programming) 27
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 CHƯƠ NG 2 CÁC THUẬẮẾ T TOÁN S P X P 2.1. Bài toán sắ p x ế p 2.1.1. Tầ m quan tr ọ ng c ủ a bài toán s ắ p x ế p Sắếộ p x p m t danh sách các đ ốượ i t ng theo m ộứự t th t nào đó là m ộ t bài toán th ườ ng đượậụ c v n d ng trong các ứụ ng d ng tin h ọ c, và là m ộầ t yêu c u không th ểế thi u trong khi thiế t k ế các ph ầ n m ề m. 2.1.2. Sắ p x ế p trong và s ắ p x ế p ngoài - Sắế p x p trong là s ựắếữệượổứ s p x p d li u đ c t ch c trong b ộớ nh trong c ủ a máy tính, ở đó ta có th ểửụả s d ng kh năng truy nh ậẫ p ng u nhiên c ủộớ a b nh và do v ậự y s thự c hi ệ n r ấ t nhanh. - Sắế p x p ngoài : S ửụ d ng khi l ượữệầắếớ ng d li u c n s p x p l n không th ểưữ l u tr trong bộ nh ớ trong mà ph ả i l ư u tr ữ trong các t ậ p tin trên b ộ nh ớ ngoài⇒ Chỉ có th ể truy nhậ p tu ầ n t ự , đ ọ c t ừ ng ph ầ n t ử m ộ t vào b ộ nh ớ trong. 2.1.3. Tổ ch ứ c d ữ li ệ u và ngôn ng ữ cài đ ặ t - Các đốượầượắế i t ng c n đ c s p x p là các b ả n ghi g ồộ m m t hay nhi ềườ u tr ng, m ộ t trong các đượọườ c g i là tr ng khóa(Key), ki ểả u cu nó là m ộể t ki u có th ứự t nào đó. Ví dụ :s ố nguyên, s ố th ự c - Danh sách các đốượầắếẽ i t ng c n s p x p s là m ộảủ t m ng c a các b ả n ghi nói trên. Mụ c đích c ủ a vi ệ c s ắ p x ế p là t ổ ch ứ c l ạ i các b ả n ghi sao cho các khóa c ủ a chúng đượắ c s p th ứựươứ t t ng ng v ớ i quy lu ậắế t s p x p. - Để trình bày ta s ử d ụ ng khai báo sau: const N=100; type Keytype=Integer; Othertype=real; Recordtype=Record Key:Keytype; OtherField: Othertype; End; Var a:array[1 N] of Recordtype; Procedure SWAP(var x,y:Recordtype); 28
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Var Temp: Recordtype; Begin Temp:=x; x:=y; y:=Temp; End; - Ta thấủụ y th t c SWAP l ấ y O(1) th ờ i gian vì ch ỉựệệ th c hi n 3 l nh gán n ốế i ti p nhau. - Dãy đích phả i th ỏ a mãn a1 .key≤ a2 .key≤ ≤ an . key hoặ c ng ượ c l ạ i. 2.1.4. Thuậ t toán s ắ p x ế p - Thuậ t toán s ắếọổịế p x p g i là n đnh n u nó không đ ảộậự o l n tr t t ban đ ầủ u c a các khóa cùng giá trị : n ế u ai=aj , i<j. - Các thuậ t toán s ắ p x ế p trong c ầ n đ ả m b ả o: + Chỉ s ử d ụ ng b ộ nh ớ trong + Có hiệ u qu ả , ti ế t ki ệ m b ộ nh ớ và th ờ i gian. - Hai phép toán cơ s ở khi th ự c hi ệ n s ắ p x ế p là so sánh và đ ổ i ch ỗ . - Thờ i gian th ựệậảẽằổốầựệ c hi n thu t gi i s đo b ng t ng s l n th c hi n phép so sánh c ộ ng vớ i s ố l ầ n th ự c hi ệ n phép đ ổ i ch ỗ . 2.2. Các phươ ng pháp s ắ p x ế p đ ơ n gi ả n 2.2.1. Sắ p x ế p ch ọ n (Selection Sort) Đây là phươ ng pháp đ ơ n gi ả n nh ấ t đ ượ c ti ế n hành nh ư sau: a)Giả i thu ậ t: - Đầ u tiên ch ọ n ph ầ n t ử có khóa nh ỏ nh ấ t trong n ph ầ n t ử a[1] đ ế n a[n] và hoán v ị nó vớ i ph ầ n t ử a[1]. - Chọầử n ph n t có khóa nh ỏấ nh t trong n-1 ph ầửừếồ n t t a[2] đ n a[n] r i hoán v ị nó vớ i a[2] - Ởướọầử b c i, ch n ph n t có khóa nh ỏấ nh t trong n-i+1 ph ầửừế n t t a[i] đ n a[n] r ồ i hoán vị nó v ớ i a[i]. - Sau n-1 bướ c thì m ả ng đã đ ượ c s ắ p. *Ví dụ : Ban đ ầ u: 5 6 2 2 10 12 9 10 9 3 Bướ c 1: 2 | 6 5 2 10 12 9 10 9 3 Bướ c 2: 2 2 | 5 6 10 12 9 10 9 3 Bướ c 3: 2 2 3 | 6 10 12 9 10 9 5 Bướ c 4: 2 2 3 5 | 10 12 9 10 9 6 Bướ c 5: 2 2 3 5 6 | 12 9 10 9 10 29
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Bướ c 6: 2 2 3 5 6 9 | 12 10 9 10 Bướ c 7: 2 2 3 5 6 9 9 | 10 12 10 Bướ c 8: 2 2 3 5 6 9 9 10 | 12 10 Kế t qu ả : B ướ c 9: 2 2 3 5 6 9 9 10 10 | 12 b)Chươ ng trình: Procedure SelectionSort; Var i,j,k:Integer; min:Real; Begin 1.for i:=1 to n-1 do Begin 2. k:=i ; min:=a[i]; 3. for j:=i+1 to n do 4. If a[j]<min then {duyệ t các ph ầ n t ử 2 → n } Begin 5. min:=a[j]; {phầ n t ử nh ỏ nh ấ t t ừ j → n } 6. k:=j ; {vị trí ph ầ n t ử nh ỏ nh ấ t} End; 7. Swap(a[i],a[k]); {Đổ i ch ỗ ph ầ n t ử nh ỏ nh ấ t tìm đ ượ c v ớ i a[i]} End; End; c)Đánh giá : Các lệ nh gán l ấ y O(1) th ờ i gian, Swap ~ O(1), vòng l ặ p for 4 th ự c hi ệ n n-i lầ n (j ch ạ y i+1 → n) mỗ i l ầ n l ấ y O(1)⇒ Lấ y O(n-i) th ờ i gian n−1 n( n −1) ⇒ Thờ i gian tính toán là T ( n) = ∑ ( n − i) = ≈ O(n 2 ) i=1 2 2.2.2. Sắ p x ế p chèn (InsertionSort) a)Giả i thu ậ t: Ý tưở ng : Lấ y d ầ n t ừ ng ph ầ n t ử t ừ dãy ngu ồ n, chèn vào dãy đích sao cho đ ả m b ả o dãy đích có thứ t ự . Xem phầ n t ử a[1] là m ộ t dãy đã có th ứ t ự . - Bướ c 1: Chèn ph ầ n t ử a[2] vào danh sách đã có th ứ t ự a[1] sao cho a[1], a[2] là m ộ t danh sách có thứ t ự . - Bướ c 2: Chèn ph ầ n t ử a[3] vào danh sách đã có th ứ t ự a[1], a[2] sao cho a[1], a[2], a[3] là mộ t danh sách có th ứ t ự , 30
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Bướ c i: Chèn ph ầ n t ử a[i+1] vào danh sách đã có th ứ t ự a[1], a[2], ,a[i] sao cho a[1],a[2], ,a[i+1] là mộ t danh sách có th ứ t ự . Phầ n t ử đang xét a[j] s ẽ đ ượ c chèn vào v ị trí thích h ợ p trong danh sách các ph ầ n t ử đã đượ c s ắ p tr ướ c đó a[1], a[2], a[j-1] b ằ ng cách so sánh a[j] v ớ i a[j-1] đ ứ ng ngay trướ c nó. N ế u a[j] 1) and (a[j]<a[j-1]) do Begin 4.Swap (a[j],a[j-1]); 5.j:=j-1; End; End; End; c)Đánh giá: - Các lệ nh (4), (5) đ ề u l ấ y O(1). 31
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Vòng lặ p (3) ch ạ y nhi ề u nh ấ t i-1 l ầ n, m ỗ i l ầ n t ố n O(1) ⇒ (3) lấ y i-1 thờ i gian. - Lệ nh (2), (3) n ố i ti ế p nhau, l ệ nh (2) l ấ y O(1)⇒ Cả 2 l ệ nh l ấ y i-1 - Vòng lặ p (1) có i ch ạ y t ừ 2 → n⇒ nế u g ọ i T(n) là th ờ i gian đ ể s ắ p n n n( n −1) phầ n t ử⇒ T ( n) = ∑ ( i −1) = ≈ O(n 2 ) i=2 2 2.2.3. Sắ p x ế p n ổ i b ọ t(Bubble Sort) a) Giảậ i thu t: Coi các b ảượư n ghi đ c l u trong m ộảọ t m ng d c. Qua quá trình s ắả p, b n ghi nào có khóa “nhẹ ” h ơ n s ẽ n ổ i lên trên. Duy ệ t toàn m ả ng, t ừ d ướ i lên trên. N ế u 2 phầửởạ n t c nh nhau mà không đúng th ứựứ t t c là ph ầửẹơởướ n t “nh h n” d i thì ph ả i cho nó “nổ i lên” b ằ ng cách đ ổ i ch ỗ 2 ph ầ n t ử này cho nhau. C ụ th ể : + Bướ c 1: Xét các ph ầửừế n t t a[n] đ n a[2], v ớỗầử i m i ph n t a[j] so sánh khóa c ủ a nó vớ i khóa c ủầử a ph n t a[j-1] đ ứ ng ngay tr ướ c nó. N ế u khóa c ủ a a[j] nh ỏơ h n khóa củ a a[j-1] thì đ ổ i ch ỗ c ủ a a[j] và a[j-1]. + Bướ c 2: Xét các ph ầ n t ử t ừ a[n] đ ế n a[3], làm t ươ ng t ự + Bướ c i: Xét các ph ầ n t ử t ừ a[n] đ ế n a[i+1] Sau n bướ c ta đ ượ c m ả ng đ ẫ s ắ p th ứ t ự . b)Ví dụ : Ban đầ u B ướ c 1 B ướ c 2 B ướ c 3 B ướ c 4 5 2 2 2 2 6 5 2 2 2 2 6 5 3 3 2 2 6 5 5 10 3 3 6 6 12 10 9 9 9 9 12 10 9 9 10 9 12 10 10 9 10 9 12 10 3 9 10 10 12 c)Chươ ng trình: Procedure BubbleSort; Var i,j: Integer; Begin 32
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 {1} For i:=1 to n-1 do {2} For j:= n downto i+1 do {3} if a[j] ch ố t sang ph ả i ch ố t, các thành phầ n có khóa ≤ chố t sang trái ch ố t⇒ Kế t qu ả c ủ a phân ho ạ ch, ch ố t đ ứ ng ở v ị trí k và mọ i thành ph ầ n c ủ a m ả ng con bên trái ch ố t A[1 k-1] có khóa ≤ chố t, m ọ i thành phầ n c ủ a m ả ng con bên ph ả i ch ố t A[k+1 n] có khóa > ch ố t. - Sắ p x ế p đ ộ c l ậ p 2 m ả ng con A[1, k-1], A[k+1, ,n] b ằ ng cách g ọ i đ ệ quy thu ậ t toán trên. 2.3.2. Thiế t k ế gi ả i thu ậ t Procedure Quicksort( i,j:Integer); Var k:Integer; Begin If i<j then Begin Partition(i,j,k); {phân hoạ ch 2 m ả ng con A[i, ,k-1] và A[k+1, ,j]} Quicksort(i,k-1); Quicksort(k+1,j); End; End; Xây dự ng th ủ t ụ c Partition: 33
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Vấềọốếọượầử n đ ch n ch t: N u ch n đ c ph n t làm ch ố t sao cho k ếả t qu phân hoach nhậượả n đ c 2 m ng con cân b ằốưẽốềờ ng là t t nh ng s tiêu t n nhi u th i gian không c ầ n thiế t⇒ Thườ ng ch ọầửầ n ph n t đ u tiên c ủả a m ng làm ch ốứấ t, t c là l y p=A[1] làm chố t. - Vấ n đ ề phân ho ạ ch: S ử d ụ ng 2 bi ế n : + Biế n L ch ạ y t ừ trái sang ph ả i b ắ t đ ầ u t ừ i. + Biế n R ch ạ y t ừ ph ả i sang trái b ắ t đ ầ u t ừ j+1. Biế n L đ ượ c tăng cho t ớ i khi A[L] > p, còn bi ế n R đ ượ c gi ả m cho t ớ i khi A[R]≤ p. Nế u L R. Cuố i cùng đ ổ i ch ỗ A[i] và A[R] đ ể đ ặ t ch ố t vào đúng v ị trí. Procedure PARTITION ( i,j:Integer; var R:Real); Var L:Integer; P: kiể u ph ầ n t ử m ả ng; Begin P:=A[i]; L:=i; R:=j+1; Repeat L:=L+1 until (A[L] > p) or (L > j); Repeat R:=R-1 until A[R]≤ p; While L p; Repeat R:=R-1 until A[R]≤ p; End; SWAP(A[i],A[R]); End; Ví dụ : Phân ho ạ ch m ả ng các s ố nguyên A[1 8] nh ư sau: 1 2 3 4 5 6 7 8 10 15 4 11 6 3 5 14 Lấ y ch ố t p=A[1]=10, L=1, R=9 Tăng L:=L+1 , giả m R:=R-1 cho t ớ i khi A[L] >10 và A[R]≤ 10 → Ta có L=2 và R=7. Vì L <R ⇒ Đổ i ch ỗ A[2] cho A[7] ta đ ượ c. 1 2 3 4 5 6 7 8 34
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 10 5 4 11 6 3 15 14 L R Tiế p t ụ c tăng L và gi ả m R cho t ớ i khi A[L] >10 và A[R]≤ 10. ⇒ Ta có L=4 và R=6. Vì L 10 và A[R]≤ 10 ⇒ Ta có L=6 và R=5 . Vì L>R, đổ i ch ỗ A[1] và A[5] Đặ t ch ố t p=A[1] vào v ị trí R=5 , ta đ ượ c: 1 2 3 4 5 6 7 8 6 5 4 3 10 11 15 14 R L Như v ậ y m ả ng A[1 8] đ ượ c phân ho ạ ch thành 2 m ả ng con A[1 R-1] và A[R+1 8] tứ c A[1 4] và A[6 8]. Sau đó ti ế p t ụ c QUICKSORT 2 m ả ng con trên ta s ẽ đ ượ c mả ng đã s ắ p x ế p. 2.3.3. Đánh giá độ ph ứ c t ạ p - Thờ i gian th ự c hi ệ n th ủ t ụ c Partition là thờ i gian đi qua m ả ng(hai bi ế n L,R ch ạ y t ừ 2 đầ u cho t ớ i khi chúng g ặ p nhau) và so sánh khóa c ủ a m ỗ i thành ph ầ n m ả ng v ớ i khóa củ a ch ố t. Do đó đ ể phân ho ạ ch m ả ng n ph ầ n t ử ta c ầ n th ờ i gian O(n)=P(n) - Gọ i T(n) là th ờ i gian th ự c hi ệ n Quicksort thì T(n) ph ả i là t ổ ng c ủ a P(n) và th ờ i gian đệ qui Quicksort cho 2 m ả ng, còn trong tr ườợấấọảầử ng h p x u nh t là ch n ph i ph n t có khóa lớ n nh ấ t làm ch ố t ⇒ Việ c phân ho ạ ch b ị l ệ ch, t ứ c là m ả ng bên ph ả i ch ỉ g ồ m mộ t ph ầ n t ử ch ố t, còn m ả ng bên trái g ồ m n-1 ph ầ n t ử còn l ạ i. Khi đó ta có th ể thành lậ p ph ươ ng trình đ ệ qui : 1 nế u n=1 1 nế u n=1 T(n)= ⇔ T(n)= O(n)+T(n-1) +T(1) nế u n>1 T(n-1)+T(1)+n nế u n>1 Giả i ph ươ ng trình đ ệ qui này b ằ ng ph ươ ng pháp truy h ồ i: 35
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Ta có: T ( n) = T ( n −1) + T (1) + n = T ( n −1) + ( n +1) = [T ( n − 2) + T (1) + n −1] + n +1 = T ( n − 2) + n + ( n +1) = [T ( n − 3) + T (1) + ( n − 2)] + n + ( n +1) = T ( n − 3) + ( n −1) + n + ( n +1) = T ( n − i) + ( n − i + 2) + ( n − i + 3) + + n + ( n +1) n+1 = T ( n − i) + ∑ j j =n−i+2 Quá trình trên kế t thúc khi i=n-1, khi đó ta có: n+1 ( n −1)( n + 4) n 2 + 3n − 2 T ( n) = T (1) + ∑ j = 1+ = = O(n 2 ) j=3 2 2 Trườợốấ ng h p t t nh t khi ch ọố n ch t sao cho 2 m ả ng con có kích th ướằ c cân b ng. ⇒ Phươ ng trình đ ệ quy: 1 n ế u n=1 T(n)= 2T(n/2) + n nế u n>1 Giả i ph ươ ng trình đ ệ quy trên ta đ ượ c T(n) = O(nlogn). Như v ậ y trong tr ườ ng h ợ p trung bình T(n)=O(nlogn) ⇒ Khá hơ n các gi ả i thu ậ t tr ướ c. 2.4. Sắ p x ế p ki ể u vun đ ố ng (Heapsort) 2.4.1. Đị nh nghĩa HEAP HEAP là mộ t cây nhi phân đ ầ y đ ủ trái mà m ỗ i nút đ ượ c gán m ộ t giá tr ị khóa sao cho giá trị khóa ở nút cha bao gi ờ cũng nh ỏ h ơ n ho ặ c b ằ ng giá tr ị khóa ở 2 nút con. Do đó trong HEAP ta có : - Nút gố c có khóa bé nh ấ t - Dãy khóa nhậ n đ ượ c khi đi theo m ộ t đ ườ ng b ấ t kì là dãy có th ứ t ự tăng d ầ n Ngườ i ta còn g ọ i HEAP là cây nh ị phân có th ứ t ự b ộ ph ậ n, HEAP - ti ế ng Anh có nghĩa là “đố ng”. Có th ể minh h ọ a HEAP b ằ ng hình ả nh “vun đ ố ng” m ộ t đ ố ng đ ấ t đá chẳ ng h ạ n, nh ữụỏẹẽằ ng c c nh nh s n m trên, nh ữụặ ng c c n ng h ơẽởướ n s d i. Ví dụ : M ộ t HEAP 1 0 1 2 5 1 5 4 7 4 36
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Cấ u trúc m ả ng thích h ợ p đ ể bi ể u di ễ n cây nh ị phân ki ể u HEAP vì HEAP là cây nh ị phân đầ y đ ủ trái. Khi đó ta nói m ả ng th ỏ a mãn đi ề u ki ệ n HEAP n ế u m ả ng bi ể u di ễ n cây nhị phân là HEAP. Ví dụ : M ả ng bi ể u di ễ n cây trên 10 15 12 54 17 91 - Nhưậớốếỉịủ v y v i “đ ng”: n u j ch vào v trí c a nút con thì [j/2] ch ỉịủ vào v trí c a nút cha, hay con củ a nút i là các nút th ứ 2i ( con trái) và 2i+1( con ph ả i). - Nút ứ ng v ớ i ch ỉ s ố [n/2] tr ở xu ố ng m ớ i có th ể là cha c ủ a các nút khác. Ví dụ : n=10⇒ các nút 5, 4, 3, 2, 1 mớ i có th ể là cha. 2.4.2. Sắ p x ế p ki ể u vun đ ố ng Đượ c chia thành 2 giai đo ạ n: Giai đoạ n 1 : Tạ o đ ố ng Từ cây nh ị phân đã cho ta bi ế n đ ổ i đ ể nó tr ở thành m ộ t “đ ố ng”. Giai đoạ n 2 : Sắ p x ế p. Nhiềượử u l t x lý đ ượ c th ự c hi ệ n, m ỗượứ i l t ng v ớ i hai phép: - Đư a khóa nh ỏ nh ấ t v ề v ị trí th ự c c ủ a nó b ằ ng cách đ ổ i ch ỗ A[1] và A[n]. - “Vun lạ i thành đ ố ng” đ ố i v ớ i cây g ồ m các khóa còn l ạ i (sau khi lo ạ i khóa nh ỏ nhấ t ra ngoài) *Ví dụ : V ớ i dãy khóa 42 23 74 11 65 58 94 36 99 87 thì cấ u trúc ban đ ầ u là cây có d ạ ng: 4 1 2 1 2 5 2 7 3 8 3 4 Tạ o đ ố ng 3 6 7 9 1 6 5 9 0 5 4 4 1 5 8 4 4 9 8 3 9 8 2 9 7 0 9 7 37
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Đổ i ch ỗ 1 và 8 ,sau đó nút ứ ng v ớ i v ị trí cu ố i cùng b ị lo ạ i kh ỏ i cây. 1 7 8 2 7 3 Vun đố ng m ớ i v ớ i 2 5 3 5 3 8 6 8 các nút còn lạ i 3 6 7 9 4 6 7 9 6 5 4 4 2 5 4 4 4 9 1 8 9 2 9 1 7 9 Dãy đ c s p S=(11) ượ ắ 9 9 Đổ i ch ỗ 2 v ớ i 9 3 5 3 9 6 8 4 6 7 9 2 5 4 4 S = (23, 11) 8 2 7 3 Thiế t k ế gi ả i thu ậ t: Vấềầả n đ c n gi i quy ếướế t tr c h t là: Bi ếổả n đ i m ng ban đ ầ u A[1 n] thành mảểễ ng bi u di n cây th ứựộậ t b ph n(“vun đ ố ng”) nh ưế th nào. Ta có nh ậằ n xét r ng: vớ i i>n div 2 thì đi ề u ki ệ n “đ ố ng” xem nh ư th ỏ a mãn vì 2i và 2i+1 >n. Nh ư v ậ y n ế u ta chỉ xét i ch ạ y t ừ n div 2 gi ả m xu ố ng 1, đ ẩ y A[i] xu ố ng v ị trí thích h ợ p trong m ả ng A[1 n] thì cuố i cùng s ẽ nh ậ n đ ượ c A[1 n] th ỏ a mãn đi ề u ki ệ n “vun đ ố ng”. ⇒ Xây dự ng th ủ t ụ c Pushdown(a,b) th ự c hi ệ n vi ệ c đ ẩ y A[a] xu ố ng v ị trí thích h ợ p trong mả ng A[a b] đ ể th ỏ a mãn đi ề u ki ệ n “đ ố ng” v ớ i ∀ i≥ a. +Thủ t ụ c Pushdown: Các phầ n t ử thu ộ c n ử a sau c ủ a m ả ng không có con⇒ không phạ m đi ề u ki ệ n HEAP⇒ Chỉ c ầ n xét t ừ gi ữ a m ả ng tr ở v ề tr ướ c. Procedure PUSHDOWN(a,b:Integer); Var i.j: integer; {lư u v ị trí c ủ a nút cha, con} 38
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 OK: Boolean; {đánh dấ u nh ữ ng nút th ỏ a mãn đi ề u ki ệ n HEAP } Begin i:=a; OK:=False; 1.While (i≤ b div 2) and not OK do { chỉ xét các nút có con và ch ư a th ỏ a mãn đi ề u ki ệ n đ ố ng} Begin 2. If i=b div 2 then j:=2*i { chỉ có con trái} else if A[2*i] A[j] then Begin { nế u con <cha thì đ ổ i ch ỗ con v ớ i cha} Swap(A[i],A[j]) ; i:=j; {đẩ y xu ố ng xét ti ế p} End; Else OK:=True; End; End; *Sử d ụ ng Pushdown trong th ủ t ụ c HEAPSORT. K ế t qu ả đ ượ c m ả ng A[1 n] s ắ p xế p gi ả m d ầ n. Procedure HEAPSORT; Var i: integer; Begin 1) for i:=n div 2 downto 1 do PUSHDOWN(i,n); { biế n đ ổ i m ả ng A[1 n] thành mả ng HEAP} 2) for i:=n downto 2 do Begin Swap (A[1],A[i]); { đổ i ch ỗ g ố c xu ố ng d ướ i cùng} PUSHDOWN(1,i-1); {vun lạ i thành đ ố ng các ph ầ n t ử còn l ạ i} End; End; 2.4.3. Độ ph ứ c t ạ p tính toán - Thờ i gian th ự c hi ệ n Pushdown 39
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 + Thân củ a vòng l ặ p (1) là các l ệ nh (2) và (3), m ỗ i l ệ nh c ầ n O(1) ⇒ Thân (1) cầ n O(1). + Sau mỗ i l ầ n l ặ p, bi ế n i tăng ít nh ấ t 2 l ầ n, giá tr ị ban đ ầ u c ủ a i là a⇒ gọ i k là s ố  b  lầ n l ặ p ⇒ a.2 k ≤ b ⇒ k ≤ log  ⇒ thờ i gian th ự c hi ệ n Pushdown(a,b) là O(log(b/a))  a  - Thờ i gian th ự c hi ệ n Heapsort n + Vòng (1) lặ p lầ n, m ỗ i l ầ n g ọ i Pushdown c ầ n nhi ề u nh ấ t là O(logn) ⇒ thờ i 2 gian thự c hi ệ n (1) là O(nlogn); + Vòng (2) lặ p n-1 l ầ n, m ỗ i l ầ n l ặ p c ầ n th ự c hi ệ n Swap và g ọ i Pushdown ⇒ Cầ n nhiề u nh ấ t O(logn)⇒ Thờ i gian th ự c hi ệ n (2) nhi ề u nh ấ t O(nlogn)⇒ Thờ i gian th ự c hiệ n Heapsort là t ổ ng hai vòng l ặ p For⇒ O(nlogn). 2.5. Sắ p x ế p hòa nh ậ p (Merge Sort) 2.5.1. Ý tưở ng: Xuấ t phát t ừỗ ch các ph ươ ng pháp s ắế p x p đã xét th ườượ ng đ c làm vớ i các file d ữ li ệ u không l ớ n. V ớ i các file l ớ n ng ườ i ta th ườ ng phân ra thành các file nhỏơểửụ h n đ s d ng các thu ậ t toán trên. Nh ưậếảẽ v y k t qu s có nhi ềầửượ u ph n t đ c sắ p x ế p theo cùng m ộ t th ứ t ự . Thu ậ t toán Merge s ẽ hòa nh ậ p các file này thành m ộ t file có độ dài nh ư file ban đ ầ u, b ằ ng cách ti ế n hành t ừ ng 2 file m ộ t, k ế t qu ả hòa ti ế p vớ i file th ứ 3 và ti ế p t ụ c nh ư v ậ y đ ế n h ế t. Giả s ử có 2 dãy X={x1,x2, ,xt} đã sắ p x ế p tăng dãy Y={y1,y2, ,ys} đã sắ p x ế p tăng Thự c hi ệ n hòa nh ậ p X và Y sao cho v ẫ n th ỏ a mãn đi ề u ki ệ n (tăng d ầ n) - So sánh giữ a 2 khóa nh ỏ nh ấ t c ủ a 2 dãy X và Y, ch ọ n khóa nh ỏ h ơ n đ ư a vào dãy mớ i Z, đ ồ ng th ờ i lo ạ i b ỏ nó kh ỏ i dãy ban đ ầ u. - Quá trình so sánh lặ p l ạ i cho đ ế n khi 1 trong 2 dãy X và Y c ạ n. Ph ầ n còn l ạ i c ủ a dãy kia xế p n ố t vào ph ầ n sau c ủ a dãy Z. *Ví dụ : X={15, 20, 50, 76} Y={8, 17, 92} +Bướ c 1: Z={8} , X={15, 20, 50, 76} Y={ 17, 92} +Bướ c 2: Z={8,15}, X={ 20, 50, 76} Y={ 17, 92} +Bướ c 3: Z={8,15,17} , X={20, 50, 76} 40
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Y={92} +Bướ c 4: Z={8,15,17,20}, X={50, 76} Y={92} +Bướ c 5: Z={8,15,17,20,50} , X={76} Y={92} +Bướ c 6: Z={8,15,17,20,50,76} . 2.5.2. Thiế t k ế gi ả i thu ậ t a) Thủ t ụ c MERGE đ ể hòa nh ậ p 2 dãy khóa đã s ắ p x ế p X={x1,x2, ,xm}, Y={y1,y2, ,yn}, Z là dãy kế t qu ả có đ ộ dài không l ớ n h ơ n n+m. Procedure MERGE (X,Y,Z,m,n); Var i,j,k : integer; Begin i:=1 ; j:=1 ; k:=1 ; While (i m then Begin { hế t dãy X,n ố i ph ầ n còn l ạ i c ủ a dãy Y vào Z} Z[k]:=Y[j]; For q:=1 to n-j do Z[k+q]:=Y[j+q]; End; Else 41
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Begin { hế t dãy Y,n ố i ph ầ n còn l ạ i c ủ a dãy X vào Z} Z[k]:=X[i]; For q:=1 to m-i do Z[k+q]:=X[j+q]; End; End; b) Thủ t ụ c MERGESORT: A là dãy khóa, B là dãy chứếảắế a k t qu đã s p x p, p, q t ươứ ng ng là hai ch ỉốầ s đ u và cuố i c ủ a dãy A. Procedure MERGESORT (A,B,p,q); Var t : integer; Begin If p<q then Begin t:= [(p+q)/2]; MERGESORT (A,B1,p,t); MERGESORT (A,B2,t+1,q); MERGE (B1,B2,B,t-p+1,q-t); End; End; * Ví dụ : S ắ p x ế p danh sách A g ồ m 8 ph ầ n t ử 7, 4, 8, 9, 3, 1, 6, 2. Mergesort như sau: 7 4 8 9 3 1 6 6 3 1 6 2 7 4 8 9 7 4 8 9 3 1 6 2 7 4 8 9 3 1 6 2 4 7 8 9 1 3 2 6 42 4 7 8 9 1 2 3 4 6 7 8 1 9 2 3 6
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 2.5.3. Đánh giá độ ph ứ c t ạ p: O(nlogn) (Đã đánh giá ở ph ầ n tr ướ c). 2.6. Cấ u trúc d ữ li ệ u và gi ả i thu ậ t x ử lý ngoài 2.6.1. Mô hình xử lý ngoài Khi sốượữệượ l ng d li u v t quá kh ả năng l ưữủộớ u tr c a b nh trong (x ử lý phiếề u đi u tra dân s ố toàn qu ốảấ c, qu n lý đ t đai ), ta ph ả i dùng b ộớ nh ngoài đ ểư l u trữử và x lý. Các thi ếịưữ t b l u tr ngoài nh ư băng t ừừề , đĩa t đ u có kh ả năng l ưữ u tr lớ n nh ư ng đ ặ c đi ể m truy nh ậ p hoàn toàn khác b ộ nh ớ trong. Do đó, ph ả i tìm CTDL> thích hợ p cho vi ệ c x ử lý d ữ li ệ u l ư u tr ữ trên b ộ nh ớ ngoài. - Kiểữệậ u d li u t p tin là ki ể u thích h ợấ p nh t cho vi ệểễữệượư c bi u di n d li u đ c l u trên bộ nh ớ ngoài. H ệ đi ề u hành chia b ộ nh ớ ngoài thành các kh ố i (block) có kích thướ c b ằ ng nhau (t ừ 512 bytes đ ế n 4096 bytes). - Trong quá trình xử lý vi ệ c chuy ể n giao d ữ li ệ u gi ữ a b ộ nh ớ trong và b ộ nh ớ ngoài đượ c ti ế n hành thông qua vùng nh ớ đ ệ m (buffer). B ộ đ ệ m là m ộ t vùng dành riêng cho bộớ nh trong có kích th ướằ c b ng kích th ướộốủộớ c m t kh i c a b nh ngoài. - Có thể xem 1 t ậ p tin bao g ồềẩượư m nhi u m u tin đ c l u trong các kh ốỗốư i. M i kh i l u mộ t s ố nguyên v ẹ n các m ẩ u tin. - Trong thao tác đọ c, nguyên m ộ t kh ố i c ủ a t ậ p tin đ ượ c chuy ể n vào trong b ộ đ ệ m, lầượọ n l t đ c các m ẩ u tin có trong b ộệ đ m cho t ớ i khi b ộệỗ đ m r ng thì l ạể i chuy n mộ t kh ố i t ừ b ộ nh ớ ngoài vào b ộ đ ệ m. - Để ghi thông tin ra b ộ nh ớ ngoài, các m ẩ u tin đ ượ c x ế p vào b ộ đ ệ m cho đ ế n khi đầộệ y b đ m thì m ộốượ t kh i đ c chuy ể n ra b ộớ nh ngoài, khi b ộệỗ đ m r ng thì x ế p tiế p các m ẩ u tin vào. ⇒ Đơị n v giao ti ếữộớ p gi a b nh trong và b ộệ đ m là m ẩ u tin, còn gi ữộệ a b đ m và b ộ nhớ ngoài là kh ố i. Ghi(mẩ u tin) Ghi(khố i) Bộ Bộ nhớ Bộ đ ệ m nhớ trong Đọ c(m ỗ i l ầ n Đọ c(m ỗ i l ầ n ngoài 1 m ẩ u tin) ghi(khố i) 1 khố i) 43
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Hình: Mô hình giao tiế p gi ữ a b ộ nh ớ trong, b ộ nh ớ ngoài và vùng nh ớ đ ệ m 2.6.2. Đánh giá các giả i thu ậ t x ử lý ngoài - Đốớộớ i v i b nh ngoài, th ờ i gian tìm m ộốểọ t kh i đ đ c vào b ộớ nh trong là r ấớ t l n so vớ i th ờ i gian thao tác trên d ữ li ệ u trong kh ố i đó. Ví dụảửộốư : Gi s m t kh i l u 1000 s ố nguyên đ ượư c l u trên đĩa quay v ớậố i v n t c 1000 v/phút thì thờ i gian đ ể đ ư a đ ầ u t ừ vào rãnh ch ứ a kh ố i và quay đĩa đ ể đ ư a kh ố i đếỗầừếả n ch đ u t h t kho ng 100 miligiây. V ớờ i th i gian này máy có th ểựệ th c hi n 100000 lệ nh, đ ủ đ ể s ắ p x ế p các s ố nguyên này theo gi ả i thu ậ t Quicksort ⇒ Khi đánh giá các giả i thu ậ t thao tác trên b ộ nh ớ ngoài, ta t ậ p trung vào vi ệ c xét s ố l ầ n đ ọ c khốộớ i vào b nh trong và s ốầ l n ghi kh ốộớ i ra b nh ngoài g ọ i là phép truy xu ấố t kh i (block access). Vì kích thướ c các kh ố i là c ố đ ị nh nên ta không th ể tìm cách tăng kích thướ c m ộ t kh ố i mà ph ả i tìm cách gi ả m s ố l ầ n truy xuấ t kh ố i. 2.6.3. Sắ p xêp ngoài - MergeSorting Sắếữệượổứưộậ p x p d li u đ c t ch c nh m t t p tin ho ặổ c t ng quát h ơắếữ n, s p x p d liệ u đ ượ c l ư u trên b ộ nh ớ ngoài g ọ i là s ắ p x ế p ngoài. a)Khái niệ m đ ườ ng - Đườộ ng đ dài k là m ộậợ t t p h p k m ẩ u tin đ ượắứự c s p th t theo khóa t ứế c là n u các mẩ u tin r1, r2, , rk lầ n l ượ t có khóa là k1, k2, , kk tạ o thành m ộ t đ ườ ng thì ≤ ≤ ≤ k1 k2 kk . - Cho tậ p tin ch ứ a các m ẩ u tin r1, r2, , rn, ta nói tậ p tin đ ượ c t ổ ch ứ c thành đ ườ ng có độ dài k n ế u ta chia t ậ p tin thành các đo ạ n k m ẩ u tin liên ti ế p và m ỗ i đo ạ n là m ộ t đườ ng, đo ạ n cu ố i có th ể không đ ủ k m ẩ u tin, ta g ọ i đo ạ n này là đuôi (tail). *Ví dụ : T ậ p tin g ồ m 14 m ẩ u tin có khóa là các s ố nguyên đ ượ c t ổ ch ứ c thành 4 đườ ng đ ộ dài 3 và 1 đuôi đ ộ dài 2 : 5 6 9 13 26 17 1 5 8 12 14 27 23 25 b)Giả i thu ậ t Để s ắ p t ậ p tin F có n m ẩ u tin ta s ử d ụ ng 4 t ậ p tin F1, F2, G1, G2. - Phân phố i các m ẩ u tin c ủ a t ậ p tin đã cho F luân phiên vào 2 t ậ p tin F1, F2. Như v ậ y 2 tậ p tin này đ ượ c xem nh ư t ổ ch ứ c thành đ ườ ng đ ộ dài 1. + Bướ c 1 : Đ ọ c 2 đ ườ ng, m ỗườ i đ ng có đ ộ dài 1 t ừậ 2 t p tin F1,F2 và trộ n 2 đ ườ ng nay thành mộ t đ ườ ng có đ ộ dài 2 và ghi luân phiên vào 2 t ậ p tin G1, G2. Đổ i vai trò F1 cho G1, F2 cho G2. 44
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 + Bướ c 2 : Đ ọ c 2 đ ườ ng, m ỗườ i đ ng có đ ộ dài 2 t ừậ 2 t p tin F1, F2 và trộ n hai đ ườ ng này thành mộ t đ ườ ng có đ ộ dài 4 và ghi luân phiên vào 2 t ậ p tin G1, G2 . Đổ i vai trò củ a F1 cho G1, F2 cho G2. Quá trình trên tiế p t ụ c và sau i b ướ c thì đ ộ dài m ộ t đ ườ ng là 2i. Nế u 2i ≥ n thì giả i thu ậ t k ế t thúc, lúc đó t ậ p tin G2 rỗ ng và G1 chứ a các m ẩ u tin đã đ ượ c s ắ p. c)Độ ph ứ c t ạ p tính toán Giả i thu ậ t k ế t thúc sau i b ướ c v ớ i i≥ logn. Mỗ i b ướ c ph ả i đ ọ c t ừ 2 t ậ p tin và ghi vào 2 tậ p tin, m ỗậ i t p tin có trung bình n/2 m ẩ u tin. Gi ảửỗốưượ s m i kh i l u đ c b mẩ u tin thì m ỗ i b ướ c c ầ n đ ọ c và ghi (2*2*n)/(2*b) = 2n/b kh ố i, mà c ầ n logn b ướ c 2n ⇒ Cầ n log n phép truy nhậ p kh ố i (block access). b Ví dụ : Cho t ậ p tin F có 23 m ẩ u tin v ớ i khóa là các s ố nguyên F : 28, 31, 3, 5, 93, 27, 15, 10, 40, 65, 9, 30, 39, 13, 90, 8, 10, 77, 8, 20, 69, 23 Phân phố i các m ẩ u tin c ủ a F luân phiên vào 2 t ậ p tin F1, F2 tổ ch ứ c thành các đ ườ ng dộ dài 1 : 28 3 93 15 40 9 39 90 10 8 22 23 F1 31 5 27 10 65 30 13 8 77 20 69 F2 +Bướ c 1 : Tr ộ n các đ ườ ng có đ ộ dài 1 c ủ a F1, F2, đượ c các đ ườ ng có đ ộ dài 2, ghi luân phiên vào 2 tậ p G1, G2 G1 28 31 27 93 40 65 13 39 10 77 22 69 F1 G2 3 5 10 15 9 30 8 90 8 20 23 F2 +Bướ c 2 : Đ ổ i vai trò G1cho F1, G2 cho F2. Trộ n các đ ườ ng đ ộ dài 2 trong F1, F2 đượ c các đườ ng đ ộ dài 4 ghi luân phiên vào G1, G2. 45
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 3 5 28 31 9 30 40 65 8 10 20 77 F1 G1 10 15 27 93 8 13 39 40 22 23 69 F2 G2 +Bướ c 3 : 3 5 10 15 27 28 31 93 8 10 20 22 23 69 77 F1 G1 8 9 13 30 39 40 65 90 F2 G2 +Bướ c 4 : 3 5 8 9 10 13 15 27 28 30 31 39 40 65 90 93 F1 G1 8 10 20 22 23 69 77 F2 G2 +Bướ c 5 : 3 5 8 8 9 10 13 15 20 22 23 27 28 30 31 39 40 65 Procedure MERGE (K : integer; f1,f2,g1,g2 : file of Recordtype); {Trộ n cac đ ườ ng có đ ộ dài k trong F1,F2 thành các đườ ng có đ ộ dài 2k và ghi luân phiên vào 2 tậ p G1,G2} Var Ghitậ p: Boolean; {nế u Ghit ậ p=True thì ghi vào G1, ngượ c l ạ i ghi vào G2} Ghimẩ u : Integer; {mẩ u tin hi ệ n hành nào trong 2 t ậ p F1,F2 sẽ đ ượ c ghi ra G1 hoặ c G2} Used: array[1 2] of Integer;{ghi số m ẩ u tin đã đ ượ c đ ọ c trong đ ườ ng hi ệ n t ạ i củ a Fj} Fin: array[1 2] of Boolean; {Fin(j)=True nế u đã đ ọ c h ế t các m ẩ u tin trong đ ườ ng hiệ n hành c ủ a Fj hoặ c đã đ ế n cu ố i Fj } Current: array[1 2] of Recordtype; {Current(j) lư u m ẩ u tin hi ệ n hành c ủ a t ậ p F[j]} 46
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Procedure GetRecord(i:Integer); { Nế u đã đ ọ c h ế t các m ẩ u tin trong đ ườ ng hi ệ n hành c ủ a fi hoặ c cu ố i fi thì đặ t Fin[i]=True nế u không thì đ ọ c m ộ t m ẩ u tin c ủ a t ậ p fi vào Current[i]} Begin Used[i]:=Used[i]+1; If(Used[i]=k+1) or (i =1) and (eof(f1)) or (i=2) and (eof(f2)) then Fin[i]:=True Else if i =1 then Read(f1, current[2]); Else Read(f2, current[2]); End; Begin {Khở i t ạ o} Ghitậ p:=True; {ghi vào tậ p F1} Reset(f1); Reset(f2); Rewrite(g1); Rewrite(g1); While (not eof(f1)) or (not eof(f2)) do { Bắ t đ ầ u đ ọ c các m ẩ u tin t ừ trong 2 đ ườ ng hi ệ n hành c ủ a f1,f2} Begin Used[1]:=0 ; Used[2]:=0; Fin[1]:=False ; Fin[2]:=False; Getrecord(1); Getrecord(2); While ( not fin[1]) or (not fin[2]) do Begin { trộ n 2 đ ườ ng , ch ọ n m ẩ u tin s ẽ đ ượ c ghi } If Fin[1] then Ghimẩ u:=2 Else if Fin[2] then Ghimẩ u:=1 Else if current[1].Key< current[2].Key then Ghimẩ u:=1 Else Ghimẩ u:=2; If Ghitậ p then Write(g1,current(Ghimẩ u)) Else Write(g2,current(Ghimẩ u)); Getrecord(Ghimẩ u); End; Ghitậ p:=Not Ghitậ p; End; End; 2.6.4. Cả i ti ế n s ắ p x ế p tr ộ n 47
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 - Quá trình sắếộ p x p tr n nói trên b ắầừườộ t đ u t các đ ng đ dài 1 nên sau logn b ướ c giả i thu ậ t m ớ i k ế t thúc. - Ta có thể ti ế t ki ệ m th ờ i gian b ằ ng cách ch ọ n m ộ t s ố k thích h ợ p sao cho k m ẩ u tin có thểủứ đ ch a trong b ộớ nh trong. M ỗầọ i l n đ c vào b ộớ nh trong k m ẩ u tin, dùng sắ p x ế p trong (Quicksort, ) đ ể s ắ p x ế p k m ẩ u tin này và ghi luân phiên vào 2 t ậ p F1,F2 sau đó tiế n hành s ắếộớ p x p tr n v i các t ậ p tin đ ượổứ c t ch c thành các đ ườộ ng đ dài k. - Sau i bướ c thì đ ộ dài m ỗ i đ ườ ng là k.2i . Giả i thu ậ t k ế t thúc khi k.2i ≥ n hay i≥ 2nlog(n / k) 2nlog n log(n/k) ⇒ Số phép truy xu ấ t kh ố i là < ⇒ Tăng tố c đ ộ s ắ p x ế p b b trộ n. *Ví dụ : Lấ y t ậ p tin F nh ư ví d ụ 1 Giảửộớ s b nh trong có th ểứượ ch a đ c 3 m ẩ u tin, đ ọầượ c l n l t 3 m ẩ u tin c ủ a F vào bộ nh ớ trong, dùng m ộ t s ắ p x ế p trong đ ể s ắ p x ế p và ghi luân phiên vào F1 và F2. 3 28 31 10 15 40 13 39 90 8 20 22 F1 5 27 93 9 30 65 8 10 77 23 69 F2 +Bướ c 1 : Tr ộ n các đ ườ ng đ ộ dài 3 c ủ a F1 và F2 đượ c các đ ườ ng đ ộ dài 6, ghi luân phiên vào G1, G2. G1 3 5 27 28 31 93 8 10 13 39 77 90 F1 G1 9 10 15 30 40 65 8 20 22 23 69 F2 +Bướ c 2 : Đ ổ i vai trò F1 cho G1, F2 cho G2, trộ n 2 đ ườ ng G1 3 5 9 10 15 27 28 30 31 40 65 93 F1 G2 8 8 10 13 20 22 23 39 69 77 90 F2 +Bướ c 3 : G1 3 5 8 8 9 10 10 13 2.6.5. Trộ n nhi ề u đ ườ ng(Multiway Merge) a) Giả i thu ậ t 48
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Để s ắ p x ế p t ậ p F có n m ẩ u tin ta s ử d ụ ng m t ậ p tin (m ch ẵ n): F[1], F[2], , F[m] (nế u m = 4 ta có gi ả i thu ậ t s ắ p x ế p tr ộ n bình th ườ ng). Đặ t h = m/2, gi ả s ử b ộ nh ớ trong có th ể ch ứ a k m ẩ u tin. - Khởầỗầọừậ i đ u: M i l n đ c t t p tin F vào b ộớ nh trong k m ẩ u tin s ửụộ d ng m t sắ p x ế p trong đ ể s ắ p x ế p k m ẩ u tin này thành đ ườ ng r ồ i ghi luân phiên vào các tậ p tin F[1], F[2], , F[h]. - Bướ c 1: Tr ộ n các đ ườ ng đ ộ dài k c ủ a h t ậ p tin F[1], F[2], , F[h] thành đườ ng có đ ộ dài k.h ghi luân phiên vào h t ậ p tin F[h+1], F[h+2], F[m]. Đ ổ i vai trò củ a F[i] và F[h+i] (1≤ i ≤ h). Sau i bướ c thì đ ộ dài m ỗ i đ ườ ng là k.hi và giả i thu ậ t k ế t thúc khi k.hi ≥ n ⇒ Tậ p tin đã đ ượ c s ắ p là m ộ t đ ườ ng ghi trong F[h+1]. b) Độ ph ứ c t ạ p tính toán i Giả i thu ậ t k ế t thúc sau i b ướ c, k.h ≥ n hay i ≥ logh(n/k). Mỗ i b ướ c ta ph ả i đ ọ c từ h t ậ p tin và ghi vào h t ậ p tin, trung bình m ỗ i t ậ p tin có n/h m ẩ u tin. 2.2.n 2n Giảửỗốưượ s m i kh i l u đ c b m ẩ u tin thì m ỗướả i b c ph i truy xu ấ t = 2.b b n 2nlogh khố i. Vì c ầ n logh(n/k) bướ c ⇒ cầ n k phép truy xuấ t kh ố i, rõ ràng logh(n/ b k) < log(n/k) và thủ t ụ c Mergesort là m ộ t tr ườ ng h ợ p đ ặ c bi ệ t khi h = 2. Ví dụ : Cho t ậ p tin F nh ư ví d ụ trên Sửụ d ng 6 t ậ p tin đ ểắế s p x p F. Gi ảửộớ s b nh trong có th ểứẩ ch a 3 m u tin, đ ọ c lầượẩ n l t 3 m u tin c ủ a F vào b ộớ nh trong, dùng m ộắế t s p x p trong đ ểắế s p x p và ghi luân phiên vào 3 tậ p tin F[1], F[2], F[3] F1 3 28 31 9 30 65 8 20 22 F2 5 27 93 13 39 90 23 69 F3 10 15 40 8 10 77 Bướ c 1: Tr ộ n các đ ườ ng đ ộ dài 3 trong F1, F2, F3 thành các đườ ng đ ộ dài 9 ghi vào F4, F5, F6. 49
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 F4 3 5 10 15 27 28 31 40 93 F1 F5 8 9 10 13 30 39 65 77 90 F2 F6 8 20 22 23 69 F3 Bướ c 2: Đ ổ i vai trò F1 cho F4, F2 cho F5, F3 cho F6 . Trộ n các đ ườ ng đ ộ dài 9 trong F1, F2, F3 thành đườ ng đ ộ dài 23 ghi vào F4. F4 3 5 8 8 9 10 10 Chươ ng 3 KỸẬẾẾẬ THU T THI T K THU T TOÁN Mặ c dù không t ồạộươ n t i m t ph ng pháp v ạ n năng có th ể giúp ta thi ếếượậ t k đ c thu t toán giảếọấềư i quy t m i v n đ , nh ng các nhà nghiên c ứ u đã tìm ra m ộốươ t s ph ng pháp thiếếậ t k thu t toán c ơả b n còn g ọ i là các chi ếượếếậ n l c thi t k thu t toán. Đó là các phươ ng pháp: Chia đ ể tr ị (Divide – and - Conquer), quy hoạ ch đ ộ ng (dynamic programming), kỹ thu ậ t tham ăn (greedy method), quay lui (backtracking), nhánh và cậ n (branch – and – bound), tìm kiế m đ ị a ph ươ ng (local search) Các kỹ thu ậ t này đ ượ c áp d ụ ng vào m ộ t l ớ p r ộ ng các bài toán trong đó có nh ữ ng bài toán nổ i ti ế ng nh ư : Bài toán tìm đ ườ ng đi ng ắ n nh ấ t c ủ a ng ườ i đi giao hàng, bài toán về các chu trình Tuy nhiên c ầ n l ư u ý r ằ ng, các ph ươ ng pháp trên ch ỉ là các chiếượ n l c có tính đ ịướự nh h ng s tìm tòi thu ậ t toán. Vi ệ c áp d ụộốếượ ng m t s chi n l c nào đó để tìm ra thu ậ t toán cho m ộ t bài toán còn đòi h ỏ i nhi ề u sáng t ạ o. 3.1. Chia để tr ị 3.1.1. Nộ i dung: Đây là kỹ thu ậ t t ừ trên xu ố ng (top – down), là k ỹ thu ậ t quan tr ọ ng nhấượ t, đ c áp d ụộ ng r ng rãi nh ấểếế t đ thi t k các gi ảậ i thu t có hi ệả u qu . Bài toán A (kích thướ c n) A ( Kt< n) A (Kt <n) A (Kt <n) 1 2 m a b 50
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Trong đó: - A1, A2, là các bài toán con cùng dạ ng v ớ i bài toán A, kích th ướ c nh ỏ h ơ n kích thướ c bài toán A. - a, b, : Các bài toán cơ s ở có l ờ i gi ả i hi ể n nhiên thu ộ c lo ạ i d ễ dàng th ự c hi ệ n. Tóm lạ i k ỹ thu ậ t chia đ ể tr ị g ồ m 2 quá trình: + Phân tích bài toán đã cho thành các bài toán cơ s ở . + Tổợếảừ ng h p k t qu t các bài toán c ơởểờả s đ có l i gi i cho bài toán ban đ ầ u. - Đốớộố i v i m t s bài toán, quá trình phân tích đã ch ứựệổợếả a đ ng vi c t ng h p k t qu ⇒ nế u ta gi ả i xong các bài toán c ơ s ở thì bài toán ban đ ầ u cũng đã đ ượ c gi ả i quy ế t. Ngượ c l ạ i có nh ữ ng bài toán mà quá trình phân tích thì đ ơ n gi ả n nh ư ng vi ệ c t ổ ng hợ p k ế t qu ả l ạ i r ấ t ph ứ c t ạ p. - Kỹậ thu t này s ẽ cho ta m ộảậệ t gi i thu t đ quy mà vi ệ c xác đnh ịộứạả đ ph c t p ph i giả i m ộ t ph ươ ng trình đ ệ quy nào đó. Lượ c đ ồ ph ươ ng pháp chia đ ể tr ị : Procedure DivideConquer(A,x); {Tìm nghiệ m x c ủ a bài toán A} Begin If A đủ nh ỏ then Solve(A) Else begin Phân A thành các bài toán con A1, A2, ,Am; For i:=1 to m do DivideConquer(Ai,xi); Kế t h ợ p các nghi ệ m xi (i = 1, 2, , m) củ a các bài toán con Ai để nhậ n đ ượ c nghi ệ m x c ủ a bài toán A End; End; 3.1.2. Mộ t s ố bài toán áp d ụ ng a) Giả i thu ậ t Mergesort và Quicksort - Vớ i Mergesort, k ỹ thu ậ t “Divide and conquer” thể hi ệ n ở quá trình chia đôi m ộ t danh sách, quá trình này sẽ d ẫ n đ ế n bài toán s ắ p x ế p m ộ t danh sách có đ ộ dài b ằ ng 1 (bài toán cơ s ở). Việ c t ổ ng h ợ p k ế t qu ả ở đây là “trộ n” 2 danh sách đã sắ p đ ể đ ượ c mộ t danh sách có th ứ t ự . - Vớ i Quicksort, k ỹ thu ậ t “Divide and conquer” thể hi ệ n ở quá trình phân ho ạ ch danh sách thành 2 danh sách con “bên trái” và “bên phả i”, sắ p x ế p “bên trái” và “bên phả i” 51
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 để đ ượ c danh sách có th ứ t ự . Quá trình phân chia d ẫ n đ ế n các bài toán s ắ p x ế p m ộ t danh sách chỉồộầửặềầử g m m t ph n t ho c nhi u ph n t có khóa b ằ ng nhau (bài toán c ơ sở ). V ớ i Quicksort không ph ả i t ổ ng h ợ p k ế t qu ả vì vi ệ c đó đã th ự c hi ệ n trong quá trình phân hoạ ch. b) Bài toán nhân các số nguyên l ớ n: Cho 2 số nguyên n ch ữ s ố X, Y, - Theo giả i thu ậ t nhân 2 ch ữ s ố thông th ườ ng c ầ n n2 phép nhân và n phép cộ ng ⇒ Tố n O(n2) thờ i gian. - Sử d ụ ng k ỹ thu ậ t “Divide and conquer”: + Chia mỗ i s ố nguyên X và Y thành các s ố nguyên có n/2 ch ữ s ố n X = A.10 2 + B trong đó A, B, C, D là các s nguyên có n/2 ch s . n ố ữ ố Y = C.10 2 + D (Ví dụ X=1234 thì A=12 và B= 34 vì X= 12.102 + 34) ⇒ X . Y = A.C.10n + (AD + BC).10n/2 + BD (1) + Vớ i m ỗ i s ố có n/2 ch ữ s ố , ti ế p t ụ c phân tích theo cách trên, quá trình phân tích s ẽ dẫếộ n đ n m t bài toán c ơở s là nhân các s ố nguyên ch ỉồộữố g m m t ch s mà ta d ễ dàng thự c hi ệ n. Vi ệ c t ổ ng h ợ p k ế t qu ả là vi ệ c th ự c hi ệ n các phép toán theo công thứ c (1). + Theo (1) phả i th ự c hi ệ n 4 phép nhân các s ố nguyên n/2 ch ữ s ố (AC, AD, BC, BD), tổ ng h ợ p k ế t qu ả b ằ ng 3 phép c ộ ng các s ố nguyên n ch ữ s ố và 2 phép nhân v ớ i 10n và 10n/2. Phép cộ ng các s ố nguyên n ch ữ s ố ch ỉ c ầ n O(n), phép nhân v ớ i 10n có thể thự c hi ệ n b ằ ng cách thêm vào n ch ữ s ố 0⇒ O(n). Gọ i T(n) là th ờ i gian nhân 2 s ố nguyên, m ỗ i s ố có n ch ữ s ố . Ta có phươ ng trình đ ệ quy: 1 =  neu n 1 T(n) =  n 4T( ) + Cn neu n > 1  2 Giả i T(n) đ ượ c T(n) = O(n2)⇒ Chư a c ả i ti ế n h ơ n so v ớ i gi ả i thu ậ t nhân 2 s ố thông thườ ng. Do đó: + Viế t (1) thành d ạ ng XY = AC10n + [(A-B)(D-C) + AC + BD].10n/2 + BD (3) 52
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 (3) chỉ c ầ n 3 phép nhân các s ố nguyên n/2 ch ữ s ố AC, BD và (A-B)(D-C), 6 phép cộ ng tr ừ và 2 phép nhân v ớ i 10n ⇒ lấ y O(n)⇒ phươ ng trình đ ệ quy 1 =  nÕ u n 1 T(n) =  n 3T( ) + Cn nÕ u n > 1  2 Giả i ph ươ ng trình đ ệ quy đ ượ c T(n) = O(nlog3) = O(n1.59)⇒ Giả i thu ậ t này c ả i thi ệ n hơ n r ấ t nhi ề u. Function Mult(x,y: integer; n: integer) : integer; Var m1,m2,m3,A,B,C,D : integer; dấ u : integer; {lư u tr ữ d ấ u c ủ a tích xy} 53
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Begin 1 nế u x>0 dấ u :=sign(x)*sign(y); sign(x) = -1 nế u x<0 x:=ABS(x); y:=ABS(y) if n=1 then Mult:=x*y*dấ u else Begin A:=Left(x, n div 2); {A: số nguyên có n/2 ch ữ s ố bên trái} B:=Right(x, n div 2); C:=Left(y, n div 2); D:=Right(y, n div 2); m1:=Mult(A,C,n div 2); m2:=Mult(A-B,D-C,n div 2); m3:=Mult(B,D,n div 2); Mult:=dấ u*[(m1*10n)+(m1+m2+m3)*10n div 2+m3]; End; End; c)Xế p l ị ch thi đ ấ u th ể thao Kỹ thu ậ t “Divide and conquer” không ch ỉ có ứ ng d ụ ng trong thi ế t k ế gi ả i thu ậ t mà còn trong nhiềứụ u ng d ng khác c ủộốưếị a cu c s ng nh : x p l ch thi đ ấể u th thao theo thểứấ th c đ u vòng tròn m ộượ t l t cho n c ầủỗầủảấớ u th . M i c u th ph i đ u v i các c ầ u thủ khác và m ỗ i c ầ u th ủ ch ỉ đ ấ u nhi ề u nh ấ t 1 tr ậ n m ộ t ngày. Yêu cầ u : X ế p 1 l ị ch thi đ ấ u sao cho s ố ngày thi đ ấ u là ít nh ấ t. n(n −1) - Dễ th ấ y, t ổ ng s ố tr ậ n đ ấ u c ủ a toàn gi ả i là 2 ⇒ nế u n ch ẵ n⇒ Sắ p n/2 c ặ p thi đ ấ u m ộ t ngày⇒ cầ n ít nh ấ t n-1 ngày. nế u n l ẻ⇒ n-1 là chẵ n⇒ sắ p (n-1)/2 c ặ p thi đ ấ u trong m ộ t ngày⇒ cầ n n ngày. Gi ả sử n=2k thì n chẵ n⇒ cầ n t ố i thi ể u n-1 ngày. - Lị ch thi đ ấộả u là m t b ng n dòng, n-1 c ộ t, dòng i bi ểễầủộểễ u di n c u th i, c t j bi u di n ngày thi đấ u j, ô (i,j) th ể hi ệ n c ầ u th ủ ph ả i thi đ ấ u v ớ i c ầ u th ủ i trong ngày j. - Xây dự ng l ị ch thi đ ấ u theo k ỹ thu ậ t “Divide and conquer” nh ư sau : Đ ể s ắ p l ị ch cho n cầủắị u th , ta s p l ch cho n/2 c ầủểắị u th ; đ s p l ch cho n/2 c ầủắị u th , ta s p l ch cho n/4 54
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 cầủẫế u th d n đ n bài toán c ơởắị s là s p l ch thi đ ấ u cho 2 c ầủầủẽ u th , 2 c u th này s thi đấ u 1 tr ậ n trong m ộ t ngày. - Tổợị ng h p l ch thi đ ấ u cho 4 c ầủầủừị u th , 8 c u th , t l ch thi đ ấủầủư u c a 2 c u th nh sau: Xuấ t phát t ừ l ị ch thi đ ấ u c ủ a 2 c ầ u th ủ⇒ lị ch thi đ ấ u cho 4 c ầ u th ủ là m ộ t b ả ng 4 dòng, 3 cộ t. L ị ch thi đ ấ u cho 2 c ầ u th ủ 1 và 2 trong ngày 1 chính là l ị ch thi đ ấ u cho 2 cầ u th ủ (bài toán c ơ s ở )⇒ ô (1,1)=”2” ; ô (2,1)=”1”, tươ ng t ự ta có l ị ch thi đ ấ u cho 2 cầ u th ủ 3 và 4 trong ngày 1⇒ ô (3,1)=”4”, ô (4,1)=”3”. Nhậ n xét: ô (3,1)=ô (1,1)+2 và ô (4,1)=ô (2,1)+2 Để hoàn thành l ị ch thi đ ấ u cho 4 c ầ u th ủ ta l ấ y góc trên bên trái c ủ a b ả ng l ắ p vào cho góc dướ i bên ph ả i và l ấ y góc d ướ i bên trái l ắ p cho góc trên bên ph ả i 1 1 2 3 1 2 1 2 3 4 2 1 2 1 4 3 3 4 1 2 4 3 2 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 2 cầ u th ủ 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 6 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 4 cầ u th ủ Vớỹậ i k thu t “chia đ ểị tr ” nói chung s ẽốơế t t h n n u ta chia bài toán c ầả n gi i thành 8 cầ u th ủ các bài toán con có kích thướ c g ầ n b ằ ng nhau Ví dụ : Mergesort phân chia bài toán thành 2 bài toán con có cùng kích th ướ c n/2 => Thờ i gian th ựệ c hi n là O(nlogn). Ng ượạ c l i trong tr ườợấấủ ng h p x u nh t c a QuickSort, khi mả ng b ị phân ho ạ ch l ệ nh thì th ờ i gian là O(n2). Nguyên tắ c chung là tìm cách phân chia bài toán thành các bài toán con có kích th ướ c xấ p x ỉ b ằ ng nhau thì hi ệ u qu ả s ẽ cao h ơ n => G ọ i là bài toán con cân b ằ ng(Balancing Subproblems). 3.2. Quy hoạ ch đ ộ ng (Dynamic) 55
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 3.2.1. Nộ i dung Tưưởủạủươ t ng ch đ o c a ph ng pháp quy ho ạộự ch đ ng d a trên nguyên lí t ốưủ i u c a Bellman : “Nế u m ộ t dãy các l ự a ch ọ n là t ố i ư u thì m ọ i dãy con c ủ a nó cũng t ố i ư u”. Ta biế t kĩ thu ậ t chia đ ểịườẫớộảậệ tr th ng d n t i m t gi i thu t đ quy. Trong các gi ả i thuậ t đó, có th ểộốảậờ có m t s gi i thu t th i gian mũ. Tuy nhiên, th ườỉộố ng ch có m t s đa thứ c các bài toán con, đi ề u đó có nghĩa là ta ph ả i gi ả i m ộ t s ố bài toán con nào đó trong nhiề u l ầ n. Thu ậ t toán nh ậ n đ ượ c s ẽ kém hi ệ u qu ả . Vì v ậ y, để tránh vi ệ c gi ả i dưừộố th a m t s bài toán con, ta dùng k ỹậừướ thu t t d i lên (bottom – up) đ ểạ t o ra mộảưấảếảủ t b ng l u t t c các k t qu c a các bài toán con và khi c ầỉầ n ch c n tham kh ả o tớếảượư i k t qu đó đ c l u trong b ả ng mà không ph ảảạ i gi i l i bài toán đó. L ấầ p đ y bảếả ng k t qu các bài toán con theo m ộ t quy lu ậ t nào đó đ ểậượếảủ nh n đ c k t qu c a bài toán ban đầ u (cũng đã đ ượ c l ư u trong m ộ t ô nào đó c ủ a b ả ng) đ ượ c g ọ i là quy hoạ ch đ ộ ng. Các thao tác tổ ng quát c ủ a quy ho ạ ch đ ộ ng: - 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 - Xây dự ng hàm quy ho ạ ch đ ộ ng (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) - Lậ p b ả ng l ư u l ạ i các giá tr ị c ủ a hàm. - Dùng bả ng l ư u đ ể truy xu ấ t l ờ i gi ả i t ố i ư u (tìm nghiệ m c ủ a bài toán). Hạ n ch ế c ủ a quy ho ạ ch đ ộ ng: Phươ ng pháp quy ho ạ ch đ ộ ng không hi ệ u qu ả trong các tình hu ố ng sau: - Sựếợờảủ k t h p l i gi i c a các bài toán con ch ưắ a ch c đã cho ta l ờảủ i gi i c a các bài toán lớ n h ơ n. - Sốượ l ng các bài toán con c ầảếưữếả n gi i quy t và l u tr k t qu có th ểấớ r t l n, không thể ch ấ p nh ậ n đ ượ c. 3.2.2. Ví dụ áp d ụ ng a) Bài toán tính số t ổ h ợ p Ta biế t công th ứ c tính s ố t ổ h ợ p ch ậ p k c ủ a n là k Cn =1 nế u k = 0 ho ặ c k = n k = k−1 + k Cn Cn−1 Cn−1 nế u 0<k<n ° Giả i thu ậ t đ ệ quy Function Tohop(k,n : Integer): integer; 56
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Begin If (k=0) or (k=n) then Tohop:=1 Else Tohop:=Tohop(k-1,n-1)+Tohop(k,n-1); End; k - Độ ph ứ c t ạ p tính toán: Gọ i T(n) là th ờ i gian tính Cn , Ta có phươ ng trình đ ệ quy C1 nế u k=0 ho ặ c k=n T(n) = 2T(n-1) + C2 nế u 0<k<n Giả i ph ươ ng trình đ ệ quy ta đ ượ c T(n) ~ O(2n). Như v ậ y gi ả i thu ậ t đ ệ quy trên có th ờ i gian th ự c hi ệ n là hàm mũ trong khi ch ỉ có m ộ t đa thứ c các bài toán con, ch ứ ng t ỏ có nh ữ ng bài toán con đ ượ c gi ả i nhi ề u l ầ n. Ví dụ : Tohop (2,4) Tohop (1,3) Tohop (2,3) Tohop (0,2) Tohop (1,2) Tohop (1,2) Tohop (2,2) Như v ậ y đ ể tính Tohop(2,4) ph ả i tính Tohop(1,2) 2 l ầ n Quy ho ạ ch đ ộ ng s ẽ kh ắ c phụ c tình tr ạ ng trên b ằ ng cách xây d ự ng m ộ t b ả ng g ồ m n+1 dòng (t ừ 0 n) và n+1 c ộ t từ (0 n) và đi ề n giá tr ị ô O(i,j) theo qui t ắ c tam giác Pascal: j 0 1 2 3 4 i 0 1 O(0,0)=1; O(i,0)=1; 1 1 1 2 1 2 1 O(i,i)=1 vớ i 0<i≤ n 3 1 3 3 1 O(i,j)=O(i-1,j-1) + O(i-1,j) 4 1 4 6 4 1 vớ i 0 <j<i ∀ n Giá trị ở ô O(n,k) chính là Tohop(n,k); Function TOHOP(n,k : integer) : integer; Var C: array[0 n,0 n] of integer; 57
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 i,j: integer; Begin C[0,0]:=1; For i:=1 to n do Begin C[i,0]:=1; C[i;i]:=1; For j:= 1 to i-1 do C[i,j]:=C[i-1,j-1]+C[i-1,j]; End; TOHOP:=Tohop[n,k]; End; Độ ph ứ c t ạ p: T(n) = O(n2). b) Xâu con chung Bài toán: Cho hai xâu ký tự x và y, hãy tìm xâu lý t ự c là xâu con chung c ủ a x và y và c có độ dài l ớ n nh ấ t có th ể đ ượ c. Ví dụ : x = ab132sc và y = 1abdc thì c = abc Nhậ n xét: Nế u x và y có đ ộ dài đ ủ nh ỏ thì có th ể gi ả i bài toán b ằ ng cách duy ệ t m ọ i xâu con chung và lư u l ạ i xâu có đ ộ dài l ớ n nh ấ t. Tuy nhiên cách làm này không th ể đáp ứ ng v ề m ặ t th ờ i gian khi x và y có đ ộ dài l ớ n. Vì v ậ y ta s ẽ dùng ph ươ ng pháp quy hoạ ch đ ộ ng đ ể gi ả i quy ế t bài toán trên nh ư sau: Gọ i m và n l ầ n l ượ t là đ ộ dài c ủ a các xâu x và y. - Nế u m ộ t trong hai s ố m = 0 ho ặ c n = 0 thì c là xâu r ỗ ng. - Xét các đoạ n đ ầ u c ủ a 2 xâu x và y có đ ộ dài i và j t ươ ng ứ ng (x1,x 2, ,xi) và ≤ ≤ ≤ ≤ (y1, y2, , yj) vớ i 0 i m,0 j n . Gọ i L(i,j) là đ ộ dài l ớ n nh ấ t xâu con chung củ a hai xâu này. Khi đó L(m,n) s ẽ là đ ộ dài l ớ n nh ấ t c ủ a hai xâu x và y. Ta có cách tính L(i,j) thông qua L(s,t) vớ i s ≤ i,t ≤ j theo quy tắ c sau: + nế u i=0 ho ặ c j=0 thì L(i,j)=0. ≠ + nế u i >0 và j >0 và xi yj thì L(i,j) = Max{L(i,j-1), L(i-1,j)} + nế u i >0 và j >0 và xi =yj thì L(i,j)=1+L(i-1,j-1). - Lư u các giá tr ị L(i,j) vào m ả ng L[0 m, 0 n]. T ừ quy t ắ c trên ta th ấ y n ế u bi ế t L[i,j- 1], L[i-1,j], L[i-1,j-1] ta tính ngay đượ c L[i,j]⇒ Có thể tính đ ượ c các ph ầ n t ử c ủ a mả ng L[0 m,0 n] t ừ góc trên trái l ầ n l ượ t theo các đ ườ ng chéo song song. Procedure Xau_con_chung; Var x, y, c:String; 58
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 I, j: Byte; L: array[0 250,0 250] of byte; Begin For i:= 1 to length(x) do L[0,i]:=0; For j:= 0 to length(y) do L[j,0]:=0; For i:=1 to length(x) do For j:=1 to length(y) do If x[i] = y[j] then L[i,j]:= L[i-1,j-1] + 1 Else If L[i-1,j] > L[i,j-1] then L[i,j]:= L[i-1,j] Else L[i,j]:= L[i,j-1] End; *Vấ n đ ề truy xu ấ t k ế t qu ả : Từ m ả ng L đã đ ượ c làm đ ầ y, ta xây d ự ng xâu con chung dài nh ấ t có đ ộ dài là k = L[m,n]. Ta xác đị nh các thành ph ầ n c ủ a c = (c1,c2, ,ck) lầ n l ượ t t ừ bên ph ả i. Trong bả ng L xu ấ t phát t ừ ô L[m,n], đ ặ t c =’ ’ , gi ả s ử đang ở ô L[i,j] : - Nế u xi=yj thì gán c = xi + c, và đi lên ô L[i-1,j-1]. ≠ - Nế u xi yj thì : + hoặ c L[i,j] =L[i,j-1] thì đi t ớ i ô L[i,j-1] + hoặ c L[i,j] =L[i-1,j] thì đi t ớ i ô L[i-1,j]. Quá trình cứ ti ế p t ụ c khi ta xác đ ị nh đ ượ c t ấ t c ả các thành ph ầ n c ủ a c (nghĩa là khi gặ p ô L[i,j] nào đó có giá tr ị 0). Procedure Truy_vet; Var i,j: byte; Begin C:=’’; i:=length(x); j:=length(y); While L[i,j]<>0 do If x[i] = y[j] then Begin C:=x[i]+c; dec(i); dec(j); End Else If L[i,j] = L[i-1,j] then dec(j) Else dec(i); Return(c); 59
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 End; *Ví dụ : Xây d ự ng b ả ng L[6,7] x = abd4eb y = 1ab4cde x y 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 1 1 1 1 1 1 3 0 1 2 2 2 2 2 4 0 1 2 2 3 3 3 5 0 1 2 2 3 3 3 6 0 1 2 3 3 3 3 7 0 1 2 3 3 4 4 C = ‘a b 4 e’ Chú ý: - Trên bả ng l ư u, khi truy v ế t có th ể có nhi ề u xâu con chung có đ ộ dài l ớ n nhấ t. - Sửụậ d ng thu t toán trên k ếợớấ t h p v i c u trúc d ữệể li u ki u con tr ỏ ta có th ể mở r ộ ng bài toán cho tr ườ ng h ợ p tìm dãy con chung c ủ a hai dãy s ố nguyên có độ dài lên t ớ i hàng ngàn đ ơ n v ị . 3.3. Phươ ng pháp tham lam (Greedy Method) 3.3.1. Bài toán tố i ư u t ổ h ợ p Có dạ ng t ổ ng quát: n f(x) = ∑ Cixi xác đị nh trên m ộ t t ậ p h ữ u h ạ n các ph ầ n t ử D. Hàm f(x) đ ượ c i=1 gọ i là hàm m ụ c tiêu. ∈ Mỗ i ph ầ n t ử X D có dạ ng X=(x1,x2, xn) đượ c g ọ i là m ộ t ph ươ ng án. Cầ n tìm m ộ t ph ươ ng án X∈D sao cho hàm f(x) đạ t Min(max). Ph ươ ng án X như th ế g ọ i là ph ươ ng án t ố i ư u. Có thể tìm ph ươốưằươ ng án t i u b ng ph ng pháp “vét c ạ n” nghĩa là xét t ấả t c các phươ ng án trong t ậ p D (h ữạể u h n) đ xác đ ịươ nh ph ng án t ốấặ t nh t. M c dù D là hữạưể u h n nh ng đ tìm m ộươ t ph ng án t ốư i u cho m ộ t bài toán kích th ướằ c n b ng phươ ng pháp “vét c ạ n” ta có th ểẽốờ s t n th i gian hàm mũ. V ớề i nhi u bài toán t ốư i u hoá, quả là quá th ừ a khi dùng quy ho ạ ch đ ộ ng đ ể xác đ ị nh các ph ươ ng án t ố i ư u, thay vì thế ta có th ể dùng các thu ậ t toán đ ơ n gi ả n và hi ệ u qu ả h ơ n. 60
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Phươ ng pháp Greedy Method s ẽ gi ả i bài toán t ố i ư u t ổ h ợ p mà th ờ i gian có th ể chấậượ p nh n đ c, tuy nhiên có th ểỉạượươ ch đ t đ c ph ng án t ốứ t ch không ph ảố i là t i ưu. 3.3.2. Nộ i dung Khác vớ i quy ho ạộườảế ch đ ng, th ng gi i quy t các bài toán con t ừướ d i lên, m ộ t chiế n l ượ c tham lam th ườ ng ti ế n tri ể n theo cách t ừ trên xu ố ng, ph ươ ng án X đ ượ c xây dự ng b ằ ng cách l ự a ch ọ n t ừ ng thành ph ầ n xi củ a X cho đ ế n khi hoàn ch ỉ nh (đ ủ n thành phầ n). V ớ i m ỗ i xi, ta sẽ ch ọ n xi tố i ư u. V ớ i cách này thì có th ể ở b ướ c cu ố i cùng ta không còn gì để ch ọ n mà ph ả i ch ấ p nh ậ n m ộ t giá tr ị cu ố i cùng còn l ạ i. Lượ c đ ồ c ủ a ph ươ ng pháp tham lam: Procedure Greedy_Method(A,X); {Xây dự ng ph ươ ng án X t ừ t ậ p các đ ố i t ượ ng A} Begin X:=φ ; While A <>φ do Begin x:= Select(A); {Hàm chọ n x t ố t nh ấ t trong A}; A:=A-{x}; If X∪{x} chấ p nh ậ n đ ượ c then X:=X∪{x}; End; Return (X); {phươ ng án t ố i ư u} End; Ta có thể d ễ dàng th ấ y t ạ i sao các thu ậ t toán nh ư th ế đ ượ c g ọ i là “tham lam”. Tạ i mỗ i b ướ c, nó ch ọ n “miế ng ngon nh ấ t” (đượ c xác đ ị nh b ở i hàm ch ọ n), n ế u th ấ y có thểốượ nu t đ c (có th ểư đ a vào nghi ệ m) nó s ẽơ x i ngay, n ế u không nó s ẽỏ b đi, sau này không bao giờ xem xét l ạ i. Cầ n l ư u ý r ằ ng, thu ậ t toán tham lam trong m ộ t s ố bài toán, n ế u xây d ự ng đ ượ c hàm chọ n thích h ợ p có th ể cho nghi ệ m t ố i ư u. Trong nhi ề u bài toán, thu ậ t toán tham lam chỉ tìm đ ượ c nghi ệ m g ầ n đúng v ớ i nghi ệ m t ố i ư u. 3.3.3.Các ví dụ áp d ụ ng: a)Bài toán đổ i ti ề n Input : - Có n loạ i ti ề n, m ỗ i lo ạ i ti ề n có giá tr ị t ươ ng ứ ng là d1,d2, ,dn. - Lượ ng ti ề n M đ ồ ng. 61
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 Output : Đổ i M đ ồ ng ra ti ề n l ẻ sao cho s ố lo ạ i ti ề n đ ổ i là ít nh ấ t. *Phân tích : Cầ n ph ả i tìm 1 nghi ệ m X = (x1,x2, xm) vớ i xi là số lo ạ i ti ề n th ứ i có giá m ⇒ trị di sao cho M=∑ xi di Tìm cách đổ i sao cho t ổ ng lo ạ i ti ề n c ầ n đ ổ i là ít nh ấ t. V ậ y i=1 ta sẽắầổừồ b t đ u đ i t đ ng xu có giá tr ịớấ l n nh t và c ứảầ gi m d n cho đ ế n khi s ốề ti n M đã đượ c đ ổ i h ế t thì thông báo là tìm đ ượ c nghi ệ m, ng ượ c l ạ i thì thông báo không đổ i đ ượ c. Áp dụ ng t ư t ưở ng c ủ a thu ậ t toán tham lam , ta có th ể vi ế t nh ư sau: Function Đổ iti ề n_Thamlam(M); Const D={d1,d2, ,dn} { mả ng l ư u giá tr ị t ừ ng lo ạ i ti ề n} Var x, sum, i; {x là nghiệ m bài toán} Begin - Sắ p x ế p D gi ả m d ầ n X=φ ; sum:=φ ; i:=1; While (sum≠ M) and (i ; End; Nhậ n xét: - Tính ch ấ t tham lam th ểệởỗạỗướ hi n ch , t i m i b c luôn ch ọế n “mi ng ăn ngon nhấ t” mà không đ ểậả ý h u qu sau này. Cho nên, v ớộốườợậ i m t s tr ng h p thu t toán cho ta nghiệốưư m t i u, nh ng trong nhi ềườợ u tr ng h p nghi ệ m tìm đ ượ c không phả i là nghi ệốư m t i u mà ch ỉầ g n đúng v ớ i nghi ệốưậ m t i u, th m chí còn không tính đượ c nghi ệ m đúng. Ví d ụ : N ế u M=13 và các lo ạ i ti ề n có m ệ nh giá là: d1=3, d2=4, 62
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010 d3=6. Cầ n tìm cách đ ổ i 13 đ ồ ng sao cho s ố ti ề n đ ổ i là ít nh ấ t. V ớ i thu ậ t toán trên ta cầờồưồ n 2 t 6 đ ng d 1 đ ng. Nh ưậốề v y s ti n này s ẽ không đ ổượư i đ c, nh ng trong thựế c t , ta có th ểổượễ đ i đ c d dàng v ớờồ i 1 t 6 đ ng, 1 t ờồ 4 đ ng và m ộờồ t t 3 đ ng. - Tuy nhiên ta hoàn toàn có thể s ử d ụ ng ph ươ ng pháp tham lam đ ể đ ạ t nghi ệ m t ố i ư u vớ i m ộ t s ố bài toán nh ư : Thu ậ t toán Kruskal tìm cây khung nh ỏ nh ấ t, b) Bài toán đườ ng đi c ủ a ng ườ i giao hàng (TSP - Traveling Salesman Problem) Mộ t ng ườ i giao hàng c ầ n đi giao hàng t ạ i n thành ph ố . Xu ấ t phát t ừ m ộ t thành ph ố nào đó, đi qua các thành phố khác đ ể giao hàng và tr ở v ề thành ph ố ban đ ầ u. M ỗ i thành phố ch ỉ đ ế n m ộ t l ầ n, kho ả ng cách t ừ 1 thành ph ố t ớ i các thành ph ố khác là xác địượịờ nh đ c (đ a lí, th i gian, c ướ c phí) đ ộ dài. Hãy l ậộ p m t chu trình sao cho t ổộ ng đ dài các cạ nh là nh ỏ nh ấ t. - Vớ i ph ươ ng pháp “vét c ạ n”, ta xét t ấ t c ả các chu trình, m ỗ i chu trình tính t ổ ng đ ộ dài các cạồọộ nh r i ch n m t chu trình có t ổộỏấ ng đ dài nh nh t, do đó c ầấả n xét t t c là ( n −1)! chu trình ⇒ Độ ph ứ c t ạ p O(n!). Vì v ậ y, ta có th ể s ử d ụ ng ph ươ ng pháp tham 2 lam sẽ cho ph ươ ng án t ố t (không ph ảươ i ph ng án t ốưưỉốờ i u) nh ng ch t n th i gian đa thứ c nh ư sau: *Thuậ t toán TSP_Greedy:  Tính độ dài c ủ a t ấ t c ả các c ạ nh (có t ấ t c ả n(n-1)/2 c ạ nh).  Xét các cạ nh có đ ộ dài t ừ nh ỏ đ ế n l ớ n đ ể đ ư a vào chu trình.  Mộạẽượư t c nh s đ c đ a vào chu trình n ếạ u c nh đó tho ả mãn hai đi ềệ u ki n sau: Không tạ o thành m ộ t chu trình thi ế u(Không đi qua đ ủ n đ ỉ nh). Không tạ o thành m ộ t đ ỉ nh có c ấ p ≥ 3(tứ c là không đ ượ c có nhi ề u h ơ n hai cạ nh xu ấ t phát t ừộỉ m t đ nh, vì m ỗ i thành ph ốỉượếộầ ch đ c đ n m t l n).  Lặ p l ạ i b ướ c 3 cho đ ế n khi xây d ự ng đ ượ c m ộ t chu trình. Vớ i ph ươ ng pháp này ta ch ỉ c ầ n n(n-1)/2 phép ch ọ n nên ta có m ộ t gi ả i thu ậ t c ầ n O(n2) thờ i gian. Mộ t cách ti ế p c ậ n khác c ủ a k ỹ thu ậ t tham lam vào bài toán này là:  Xuấ t phát t ừộỉấ m t đ nh b t kỳ, ch ọộạ n m t c nh có đ ộ dài nh ỏấ nh t trong t ấả t c các cạ nh đi ra t ừ đ ỉ nh đó đ ể đ ế n đ ỉ nh k ế ti ế p.  Từỉếếạọộạ đnh k ti p ta l i ch n m t c nh có đ ộ dài nh ỏấ nh t đi ra t ừỉ đnh này tho ả mãn hai điề u ki ệ n nói trên đ ể đi t ớ i đ ỉ nh k ế ti ế p. 63
Giáo trình Lý thuyế t thu ậ t toán-B ộ môn Khoa h ọ c máy tính-2010  Lặạướ p l i b c 2 cho đ ế n khi đi t ớỉ i đ nh n thì quay tr ởềỉấ v đ nh xu t phát. Ví dụ : Cho bài toán TSP 5 đ ỉ nh đ ượ c bi ể u di ễ n nh ư m ộ t đ ồ th ị G = (V, E), và quá trình thự c hi ệ n gi ả i bài toán b ằ ng thu ậ t toán tham lam th ể hi ệ n trong hình sau: Hình : Quá trình tìm hành trình theo nguyên lý Greedy, đỉ nh s ố 1 là đ ỉ nh xu ấ t phát Kế t qu ả : Hành trình tìm đ ượ c có chi ề u dài 14 (Hành trình tố i ư u là 13). Độ ph ứ c t ạ p O(n2). c) Bài toán xế p ba lô (xế p balô giá tr ị nguyên) - Input: Mộ t ba lô có th ể tích B, n đ ồ v ậ t có th ể tích: a1, a2, an , Giá trị t ươ ng ứ ng c ủ a các đ ồ v ậ t là: p1, p2, pn Số l ượ ng m ỗ i lo ạ i đ ồ v ậ t là không h ạ n ch ế , xi nguyên là số l ượ ng loạ i đ ồ v ậ t i. 64