Giáo trình Thuật toán | Đại học Phenika
Giáo trình Thuật toán | Đại học Phenika. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem.
Môn: Cấu trúc dữ liệu và thuật toán (Phenika) 12 tài liệu
Trường: Đại học Phenika 1.3 K tài liệu
Tác giả:
Preview text:
MỤC LỤC 1. THU T Ậ TOÁN 2. CÁC PHƯ N Ợ G PHÁP BI U
Ể DIỄN THUẬT TOÁN
3. ĐỘ PHỨC T P Ạ C A Ủ THU T Ậ TOÁN 4.PHÂN LOẠI V N
Ấ ĐỀ - BÀI TOÁN 5. THU T
Ậ TOÁN ĐỆ QUY 6.THU T Ậ GI I Ả 5.1.GIỚI THI U Ệ NGÔN NG Ữ PASCAL 5.2. CÁC PH N
Ầ TỬ CƠ BẢN C A
Ủ NGÔN NGỮ PASCAL 5.3. C U Ấ TRÚC CHUNG C A Ủ CHƯ N Ơ G TRÌNH PASCAL 5.4. SỬ D N Ụ G PH N Ầ M M Ề TURBO PASCAL
5.5 CÂU HỎI TRẮC NGHIỆM 5.6. BÀI T P Ậ
6.1. KHÁI NIỆM VỀ KIỂU DỮ LI U Ệ
6.2. KIỂU SỐ NGUYÊN
6.3. KIỂU SỐ TH C Ự 6.4. KIỂU KÝ T Ự (CHAR)
6.5. KIỂU LÔGIC (BOOLEAN) 6.6. CHUỖI KÝ T Ự (STRING) 6.7. CÂU HỎI TR C Ắ NGHIỆM 7.1. H N Ằ G, BI N
Ế và BIỂU THỨC
7.2. CÂU LỆNH và LỜI CHÚ GIẢI 7.3.1. NH P
Ậ DỮ LIỆU, TH Ủ T C Ụ “READLN” 7.3.2. XU T Ấ DỮ LI U Ệ , TH Ủ T C
Ụ “WRITE” và “WRITELN”
7.4. KIỂU LIỆT KÊ và KI U Ể ÐO N Ạ CON 7.5. CÂU HỎI TR C Ắ NGHIỆM 7.6. BÀI T P Ậ Trang 1/268 8.1. CÂU LỆNH IF 8.2. CÂU LỆNH CASE 8.3. CÂU HỎI TR C Ắ NGHIỆM 8.4. BÀI T P Ậ 9.1. CÂU LỆNH L P Ặ FOR 9.2. CÂU LỆNH L P Ặ WHILE 9.3. CÂU LỆNH L P Ặ REPEAT 9.4. CÂU HỎI TR C Ắ NGHIỆM 9.5. BÀI T P Ậ 10.1. M N
Ả G MỘT CHI U Ề 10.2. M N
Ả G HAI CHIỀU (MA TRẬN) 10.3. CÂU HỎI TR C Ắ NGHIỆM 10.4. BÀI T P Ậ 11.1. CÁC VÍ D
Ụ NÂNG CAO VỀ CÂU LỆNH LẶP 11.2. CÁC VÍ D
Ụ NÂNG CAO VỀ MẢNG 11.3. KI U Ể CHU I Ỗ KÝ TỰ 11.4. CÂU HỎI TR C Ắ NGHIỆM 11.5. BÀI T P Ậ
12.1. KHÁI NIỆM VỀ CHƯ N Ơ G TRÌNH CON 12.2. HÀM (FUNCTION) 1 2.3. TH Ủ T C Ụ (PROCED U RE ) 12.4. CÂU HỎI TR C Ắ NGHIỆM 12.5. BÀI T P Ậ 13.1. THAM SỐ TR Ị VÀ THAM S Ố BI N Ế 13.2. PH M Ạ VI TÁC D N Ụ G C A Ủ CÁC KHAI BÁO 13.3. SỰ THAM KH O Ả TRƯ C
Ớ và SỰ ÐỆ QUI 13.4. CÂU HỎI TR C
Ắ NGHIỆM13.5. BÀI TẬP Trang 2/268 14.1 KI U Ể B N Ả GHI 14.2. CÁC VÍ D Ụ VỀ B N Ả GHI 14.3. CÂU HỎI TR C Ắ NGHIỆM 14.4 .BÀI T P Ậ 15.1. KI U Ể T P Ậ H P Ợ 15.2. DỮ LI U Ệ KIỂU T P Ậ TIN 15.3. CÂU HỎI TR C Ắ NGHIỆM 15.4. BÀI T P Ậ 1. THUẬT TOÁN
Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng
dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một
tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là
một phương pháp thể hiện lời giải của vấn đề - bài toán.
Tại sao lại là "Thuật toán" ?
Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa
al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp
mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là
một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông.
Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề
khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng
được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có
thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. Số bước
hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một
tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề - bài toán có vô số bước giải ? Tính "không mập mờ" và
"có thể thực thi được" gọi chung là tính xác định.
Giả sử khi nhận một lớp học mới, Ban Giám hiệu yêu cầu giáo viên chủ nhiệm chọn lớp trưởng mới theo các bước sau :
1. Lập danh sách tất các học sinh trong lớp.
2. Sắp thứ tự danh sách học sinh.
3. Chọn học sinh đứng đầu danh sách để làm lớp trưởng.
Khi nhận được thông báo này, giáo viên chắc chắn sẽ rất bối rối vì không hiểu là trong danh sách học sinh cần có những
thông tin gì? Danh sách chỉ cần họ tên, hay cần thêm ngày tháng năm sinh? Có cần thêm điểm trung bình không? Yêu
cầu 2 lại càng gây nhiều thắc mắc. Cần phải sắp xếp danh sách theo chiều
tăng dần hoặc giảm dần ? Sắp theo chỉ tiêu gì ? Theo tên, theo ngày tháng năm sinh hay theo điểm trung bình chung,
...Giả sử sắp theo điểm trung bình thì nếu có hai học sinh cùng điểm trung bình thì học sinh nào sẽ sắp trước, học sinh nào sẽ sắp sau ? ... Trang 3/268
Hướng dẫn ở trên vi phạm tính chất "không mập mờ" của thuật toán. Nghĩa là, có quá nhiều thông tin còn thiếu để làm
cho các bước 1,2 được hiểu đúng và hiểu theo một nghĩa duy nhất. Nếu sửa lại một chút ít thì hướng dẫn trên sẽ trở
nên rõ ràng hơn rất nhiều và có thể gọi là một thuật toán chọn lớp trưởng !
1. Lập danh sách tất các học sinh trong lớp theo hai thông tin: Họ và Tên; Ðiểm trung bình cuối năm.
2. Sắp hạng học sinh theo điểm trung bình theo thứ tự giảm dần (từ điểm cao đến điểm thấp). Hai học sinh có cùng
điểm trung bình sẽ có cùng hạng.
3. Nếu chỉ có một học sinh có hạng nhất thì chọn học sinh đó làm lớp trưởng. Trường hợp có nhiều học sinh đồng
hạng nhất thì chọn học sinh có điểm môn Toán cao nhất làm lớp trưởng.
Nếu vẫn còn nhiều hơn một học sinh đồng hạng nhất và có cùng điểm môn Toán cao nhất thì tiến hành bốc thăm.
Ở đây chúng ta cần phân biệt mập mờ và sự chọn lựa có quyết định. Mập mờ là thiếu thông tin hoặc có nhiều chọn lựa
nhưng không đủ điều kiện để quyết định. Còn chọn lựa có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ
thể của vấn đề. Chẳng hạn trong vấn đề chọn lớp trưởng ở trên, bước 3 thể hiện một sự lựa chọn có quyết định. Tất
nhiên, khi chưa lập danh sách, chưa xếp hạng theo điểm trung bình thì giáo viên không thể biết được sẽ chọn lớp trưởng
theo cách nào. Nhưng khi đã sắp xong danh sách thì chỉ có một phương án chọn duy nhất. Tính "thực thi được" cũng là
một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có
được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán.
Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực,
nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ
đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược
chiều thì người đi không thể đi đến bưu điện được.
Tính "dừng" là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều
nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả
mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số
nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : B1. Hỏi giá trị của n. B2. S = 0 B3. i = 1
B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 B5. Cộng thêm i vào S B6. Cộng thêm 2 vào i B7. Quay lại bước B4.
B8. Tổng cần tìm chính là S.
Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là "nếu i lớn hơn n" thì
ta thay bằng điều kiện "nếu i bằng n+1" vì theo toán học "i = n+1" thì suy ra "i lớn hơn n". Nhưng điều kiện "i=n+1"
không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n
là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một
số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn.
Tính "đúng" là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài
toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học Trang 4/268
sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học
sinh nhất định là có khả năng đưa ra lời giải đúng!
Thuật toán thì cứng nhắc !
Các tính chất của thuật toán rất chặt chẽ và cứng nhắc. Nhưng điều đó cũng có nghĩa là khả năng giải quyết vấn đề theo
kiểu thuật toán cũng bị giới hạn. Sau này, người ta đã "làm mềm" đi hai tính chất quan trọng của thuật toán là tính xác
định và tính đúng để giải quyết những vấn đề phức tạp hơn mà với các tính chất chặt chẽ của thuật toán thì không thể
giải quyết được. Ðó là các thuật toán đệ quy và thuật giải. Ta sẽ tìm hiểu về điều này ngay trong các mục 4 và 5 của chương này.
Các đặc trưng khác của thuật toán
Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc trưng phụ khác.
1. Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý
nó và cho ra kết quả cuối cùng.
2. Tính hiệu quả (effectiveness) : tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối
lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết
định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu
quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật
toán. 3. Tính tổng quát (generalliness) : thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường
hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình
bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy
nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật
toán cho một dạng đặc trưng của bài toán mà thôi.
Thuật toán giải phương trình bậc hai ax2+bx+c=0 (a?0)
1. Yêu cầu cho biết giá trị của 3 hệ số a, b, c 2. Nếu a=0 thì
2.1. Yêu cầu đầu vào không đảm bảo.
2.2. Kết thúc thuật toán.
3. Trường hợp a khác 0 thì
3.1. Tính giá trị D = b2-4ac 3.2. Nếu D > 0 thì
3.2.1. Phương trình có hai nghiệm phân biệt x1 và x2
3.2.2. Giá trị của hai nghiệm được tính theo công thức sau
3.2.3. Kết thúc thuật toán. 3.3. Nếu D = 0 thì Trang 5/268
3.3.1. Phương trình có nghiệm kép x0
3.3.2. Giá trị của nghiệm kép là
3.3.3. Kết thúc thuật toán 3.4. Nếu D < 0 thì
3.4.1. Phương trình vô nghiệm.
3.4.2. Kết thúc thuật toán.
Thuật toán tìm hộp có trọng lượng nặng nhất
Vấn đề : Có n hộp có khối lượng khác nhau và một cái cân dĩa. Hãy chỉ ra cách cân để tìm được hộp có trọng
lượng nặng nhất. Vấn đề này là thể hiện của một bài toán tổng quát : Cho một tập hợp A hữu hạn và một thứ tự toàn
phần trên A. Hãy xây dựng thuật toán tìm phần tử lớn nhất của A. Bài toán trong toán học có vẻ rất phức tạp nhưng một
thể hiện trên thực tế lại rất dễ hiểu, và cách giải quyết cũng đơn giản. Từ đó ta có thể dễ dàng suy ra cách giải bài toán tổng quát.
1. Nếu chỉ có 1 hộp (n=1) thì
1.1. Hộp đó chính là hộp nặng nhất.
1.2. Kết thúc thuật toán.
2. Ngược lại nếu có từ hai hộp trở lên (n>1)
2.1. Chọn hai hộp bất kỳ và đặt lên bàn cân.
2.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
3. Nếu còn hộp chưa được cân thực hiện các bước sau, nếu không còn hộp nào nữa, sang bước 5.
3.1. Chọn một hộp bất kỳ và để lên dĩa cân còn trống.
3.2. Giữ lại hộp nặng hơn, cất hộp nhẹ hơn sang chỗ khác.
4. Trở lại bước 3.
5. Hộp còn lại trên cân chính là hộp nặng nhất. Kết thúc.
Thuật toán Euclid tìm ước số chung lớn nhất
Bài toán : Cho hai số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b.
1. Yêu cầu cho biết giá trị của a, b. 2. a0 = a 3. b0 = b Trang 6/268 4. i = 0
5. Nếu ai khác bi thì thực hiện các thao tác sau, ngược lại qua bước 7. 5.1 Tăng i lên 1.
5.2. Nếu ai-1 > bi-1 thì
ai = ai-1 - bi-1 bi = bi-1 5.3. Ngược lại
bi = bi-1 - ai-1 ai = ai-1
6. Trở lại bước 5.
7. Ước số chung lớn nhất của a, b là ai .
2. CÁC PHƯỢNG PHÁP BIỂU DIỄN THUẬT TOÁN
Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ toán học như : "ta có", "điều
phải chứng minh", "giả thuyết", ... và sử dụng những phép suy luận toán học như phép suy ra, tương đương, ...Thuật toán
là một phương pháp thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền đạt
thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật
toán. Có 3 phương pháp biểu diễn thuật toán :
1. Dùng ngôn ngữ tự nhiên.
2. Dùng lưu đồ-sơ đồ khối (flowchart).
3. Dùng mã giả (pseudocode).
2.1. Ngôn ngữ tự nhiên
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước
của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này
không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này
thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như
không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết
các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, ... Bạn có thể tham khảo lại ba ví
dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên.
2.2. Lưu đồ - sơ đồ khối
Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp
người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được
dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý.
Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác. Một thao tác là thao tác chọn lựa dựa theo
một điều kiện nào đó. Chẳng hạn : thao tác "nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao tác chọn Trang 7/268
lựa. Các thao tác còn lại không thuộc loại chọn lựa được xếp vào loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và
để lên dĩa cân còn trống." là một thao tác thuộc loại hành động.
2.2.1. Thao tác chọn lựa (decision)
Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.
2.2.2. Thao tác xử lý (process)
Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.
2.2.3.Ðường đi (route)
Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện sẽ lần lượt đi từ bước trước đến bước sau (trừ khi
có yêu cầu nhảy sang bước khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có thể đặt các hình vẽ
này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình tự thực hiện các thao tác.
Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để chỉ hướng thực hiện. Chẳng hạn trong hình dưới,
trình tự thực hiện sẽ là B1, B2, B3.
Từ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều kiện thỏa và một hướng ứng với điều kiện
không thỏa. Do vậy, ta dùng hai cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes để chỉ
hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi ứng với điều kiện không thỏa. Trang 8/268
2.2.4. Ðiểm cuối (terminator)
Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn bằng hình ovan, bên trong có ghi chữ bắt
đầu/start/begin hoặc kết thúc/end. Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc). Xem
lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách sử dụng của điểm cuối.
2.2.5. Ðiểm nối (connector)
Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với nhau. Bên trong điểm nối, ta đặt một ký hiệu để
biết sự liên hệ giữa các điểm nối.
2.2.6. Ðiểm nối sang trang (off-page connector)
Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu đồ quá lớn, phải vẽ trên nhiều trang. Bên trong
điểm nối sang trang ta cũng đặt một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang. Trang 9/268
Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực tế, lưu đồ còn có nhiều ký hiệu khác nhưng
thường chỉ dùng trong những lưu đồ lớn và phức tạp. Ðối với các thuật toán trong cuốn sách này, ta chỉ cần sử dụng các ký hiệu trên là đủ. 2.3. Mã giả
Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả
một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa
có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp (Chúng ta sẽ tìm hiểu về thao tác lặp trong các bài sau).
Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật
toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận
dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất
nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn
ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý do này, chúng ta chưa vội tìm
hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ lập trình!). Sau khi tìm hiểu xong bài về thủ tục - hàm
bạn sẽ hiểu mã giả là gì !
Một đoạn mã giả của thuật toán giải phương trình bậc hai
if Delta > 0 then begin x1=(-b-sqrt(delta))/(2*a) x2=(-b+sqrt(delta))/(2*a)
xuất kết quả : phương trình có hai nghiệm là x1 và x2 end else
if delta = 0 then
xuất kết quả : phương trình có nghiệm kép là -b/(2*a)
else {trường hợp delta < 0 }
xuất kết quả : phương trình vô nghiệm
* Các từ in đậm là các từ khóa của ngôn ngữ Pascal Trang 10/268
3. ĐỘ PHỨC TẠP CỦA THUẬT TOÁN
Một chương trình máy tính thường được cài đặt dựa trên một thuật toán đúng để giải quyết bài toán hay vấn đề. Tuy
nhiên, ngay cả khi thuật toán đúng, chương trình vẫn có thể không sử dụng được đối với một dữ liệu đầu vào nào đó vì
thời gian để cho ra kết quả là quá lâu hoặc sử dụng quá nhiều bộ nhớ (vượt quá khả năng đáp ứng của máy tính).
Khi tiến hành phân tích thuật toán nghĩa là chúng ta tìm ra một đánh giá về thời gian và "không gian" cần thiết để thực
hiện thuật toán. Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, ... của máy tính để thuật toán có
thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán.
Trong phần này, khi nói đến độ phức tạp của thuật toán, chúng ta chỉ đề cập đến những đánh giá về mặt thời gian mà thôi.
Phân tích thuật toán là một công việc rất khó khăn, đòi hỏi phải có những hiểu biết sâu sắc về thuật toán và nhiều kiến
thức toán học khác. Ðây là công việc mà không phải bất cứ người nào cũng làm được. Rất may mắn là các nhà toán học
đã phân tích cho chúng ta độ phức tạp của hầu hết các thuật toán cơ sở (sắp xếp, tìm kiếm, các thuật toán số học, ...).
Chính vì vậy, nhiệm vụ còn lại của chúng ta là hiểu được các khái niệm liên quan đến độ phức tạp của thuật toán.
Ðánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối (chạy thuật toán mất bao nhiêu giây,
bao nhiêu phút,...) để thực hiện thuật toán mà là xác định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi
phí (số thao tác, số phép tính cộng,trừ, nhân, chia, rút căn,...) để thực hiện thuật toán. Sở dĩ người ta không quan tâm đến
thời gian tuyệt đối của thuật toán vì yếu tố này phụ thuộc vào tốc độ của máy tính, mà các máy tính khác nhau thì có tốc
độ rất khác nhau. Một cách tổng quát, chi phí thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào :T = f(input)
Tuy vậy, khi phân tích thuật toán, người ta thường chỉ chú ý đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi
phí. Trong các thuật toán, độ lớn của dữ liệu đầu vào thường được thể hiện bằng một con số nguyên n. Chẳng hạn : sắp
xếp n con số nguyên, tìm con số lớn nhất trong n số, tính điểm trung bình của n học sinh, ... Lúc này, người ta thể hiện
chi phí thực hiện thuật toán bằng một hàm số phụ thuộc vào n : T = f(n)
Việc xây dựng một hàm T tổng quát như trên trong mọi trường hợp của thuật toán là một việc rất khó khăn, nhiều lúc
không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của
thuật toán, thường là trường hợp tốt nhất và xấu nhất.
Chúng ta trở lại ví dụ về thuật toán tìm hộp nặng nhất trong n hộp cho trước, nhưng lần này ta làm việc trên một thể
hiện khác của vấn đề. Ðây là một thuật toán tương đối đơn giản nên chúng ta có thể tiến hành phân tích được độ phức
tạp. Trước khi phân tích độ phức tạp, ta nhắc lại đôi điều về thuật toán này.
Tìm số lớn nhất trong một dãy số
Bài toán : Cho một dãy số a có n phần tử a1, a2, ...an. Hãy xây dựng thuật toán để tìm con số lớn nhất trong dãy a. Nhận xét
1. Nếu dãy chỉ có 1 phần tử thì phần tử đó là số lớn nhất.
2. Giả sử dãy có n phần tử và ta đã xác định được phần tử lớn nhất là amax . Nếu bổ sung thêm phần tử thứ an+1 vào dãy
mà an+1 > amax thì an+1 chính là phần tử lớn nhất của dãy có n+1 phần tử. Trường hợp ngược lại, nghĩa là an+1 £ amax
thì amax vẫn là phần tử lớn nhất của dãy có n+1 phần tử. Thuật toán 1. Ghi nhớ amax = a1. Trang 11/268 2. i = 2.
3. Nếu (i £ n) thì thực hiện các bước sau, ngược lại sang bước 5.
3.1. Nếu (ai > amax ) thì 3.1.1. Ghi nhớ amax = ai . 3.2. Tăng i lên 1.
4. Trở lại bước 3.
5. Phần tử lớn nhất dãy a chính là amax .Kết thúc.
Trong thuật toán trên, để đơn giản, ta chỉ xem chi phí là số lần so sánh ở bước 3.1 và số lần "ghi nhớ" trong bước
3.1.1. Trường hợp tốt nhất của thuật toán này xảy ra khi con số lớn nhất nằm đầu dãy (amax= a1); trường hợp xấu nhất xảy
ra khi con số lớn nhất nằm ở cuối dãy (amax=an) và dãy được sắp xếp theo thứ tự tăng dần.
Dựa theo sơ đồ khối của thuật toán, ta nhận thấy rằng, trong mọi trường hợp của bài toán, phép "ghi nhớ" ở bước 3.1
luôn được thực hiện và số lần thực hiện là n-1 (ứng với việc xét từ phần tử a2 đến an). Ta gọi đây là chi phí cố định hoặc
bất biến của thuật toán.
Trường hợp tốt nhất : do amax = a1 suy ra, với mọi i ³ 2, ai< amax. Do đó, điều kiện ai>amax ở bước 3.1 luôn không thỏa
nên bước 3.1.1 không bao giờ được thực hiện. Như vậy, chi phí chung cho trường hợp này chính là chi phí cố định của bài toán. T = f(n) = n-1
Trường hợp xấu nhất :
Ta có : với mọi i>1, ai-1< ai (do định nghĩa dãy được sắp xếp tăng dần) nên điều kiện ai>amax ở bước 3.1 luôn thỏa,
bước 3.1.1 luôn được thực hiện. Như vậy, ngoài chi phí chung là n-1 phép so sánh, ta cần phải dùng thêm n-1 phép "ghi
nhớ" ở bước 3.1.1. Như vậy, tổng chi phí của trường hợp này là Trang 12/268 T = f(n) = 2(n-1)=2n-2 Ðịnh nghĩa
Cho hai hàm f và g có miền xác định trong tập số tự nhiên . Ta viết f(n) = O(g(n))
và nói f(n) có cấp cao nhất là g(n) khi tồn tại hằng số C và k sao cho
| f(n) | £ C.g(n) với mọi n > k
Tuy chi phí của thuật toán trong trường hợp tốt nhất và xấu nhất có thể nói lên nhiều điều nhưng vẫn chưa đưa ra được một hình dung tốt nhất
về độ phức tạp của thuật toán. Ðể có thể hình dung chính xác về độ phức tạp của thuật toán, ta xét đến một yếu tố khác là
độ tăng của chi phí khi độ lớn n của dữ liệu đầu vào tăng.
Theo định nghĩa ở trên, ta nhận thấy chi phí thấp nhất và lớn nhất của thuật toán tìm số lớn nhất đều bị chặn bởi O(n)
(tồn tại hằng số C=10, k=1 để 2n-2 < 10n với mọi n>1).
Một cách tổng quát, nếu hàm chi phí của thuật toán (xét trong một trường hợp nào đó) bị chặn bởi O(f(n)) thì ta nói
rằng thuật toán có độ phức tạp là O(f(n)) trong trường hợp đó.
Như vậy, thuật toán tìm số lớn nhất có độ phức tạp trong trường hợp tốt nhất và xấu nhất đều là O(n). Người ta gọi các
thuật toán có độ phức tạp O(n) là các thuật toán có độ phức tạp tuyến tính.
Sau đây là một số "thước đo" độ phức tạp của thuật toán được sử dụng rộng rãi. Các độ phức tạp được sắp xếp theo
thứ tự tăng dần. Nghĩa là một bài toán có độ phức tạp O(nk) sẽ phức tạp hơn bài toán có độ phức tạp O(n) hoặc O(logan).
4. PHÂN LOẠI VẤN ĐỀ - BÀI TOÁN
Ðộ phức tạp của thuật toán chính là yếu tố cơ sở để phân loại vấn đề-bài toán. Một cách tổng quát, mọi bài toán đều
có thể chia làm 2 lớp lớn là : giải được và không giải được. Lớp giải được chia làm 2 lớp con. Lớp con đầu tiên là các
bài toán có độ phức tạp đa thức : nghĩa là bài toán có thể giải được bằng thuật toán có độ phức tạp đa thức (hay nói
ngắn gọn : lớp đa thức) được xem là có lời giải thực tế. Lớp con thứ hai là những bài toán có độ phức tạp không phải là
đa thức mà lời giải của nó được xem là thực tế chỉ cho những số liệu đầu vào có chọn lựa cẩn thận và tương đối nhỏ.
Cuối cùng là những bài toán thuộc loại NP chưa thể phân loại một cách chính xác là thuộc lớp bài toán có độ phức tạp đa
thức hay có độ phức tạp không đa thức.
4.1. Lớp bài toán có độ phức tạp đa thức Trang 13/268
Các bài toán thuộc lớp này có độ phức tạp là O(nk) hoặc nhỏ hơn O(nk). Chẳng hạn như các bài toán có độ phức tạp
là O(nlog2n) được xem là các bài toán thuộc lớp đa thức vì nlog2n bị chặn bởi n2 ( nlog2n £ n2 với mọi n>0). Như vậy
các bài toán có độ phức tạp hằng O(1), phức tạp tuyến tính O(n) và logarith O(nlogan) đều là các bài toán thuộc lớp đa
thức. Còn các bài toán có độ phức tạp lũy thừa O(an) hoặc giai thừa O(n!) là không thuộc lớp đa thức.
Tuy độ phức tạp chỉ là số đo về độ tăng của chi phí ứng với độ tăng của dữ liệu đầu vào nhưng nó cũng cho chúng ta có
một đánh giá tương đối về thời gian thi hành thuật toán. Các thuật toán thuộc lớp đa thức được xem là các bài toán có lời
giải thực tế. Lời giải thực tế được hiểu rằng là chi phí về mặt thời gian và không gian cho việc giải bài toán là chấp nhận
được trong điều kiện hiện tại. Bất kỳ một bài toán nào không thuộc lớp này thì đều có chi phí rất lớn.
Có thể giải được hay không?
Người ta đã ước tính thời gian cần thiết để giải một mật mã được mã hóa bằng khóa 128-bit là trên 1 triệu năm với điều
kiện làm việc trên các siêu máy tính mạnh nhất hiện nay!
Chính vì lý do này, một bài toán được xem là có thể giải được trên thực tế hay không phụ thuộc vào độ phức tạp của bài
toán đó có phải là đa thức hay không.
4.2. Lớp bài toán có độ phức tạp không đa thức
Thật không may mắn, nhiều bài toán thực sự có lời giải lại không thuộc lớp của bài toán đa thức. Ví dụ : cho một tập
hợp có n phần tử, hãy liệt kê tất cả các tập con khác trống của tập hợp này. Bằng toán học, người ta đã chứng minh
được rằng số tập con của một tập hợp có n phần tử là 2n-1. Lời giải tuy đã có nhưng khi thể hiện lời giải này bằng bất kỳ
thuật toán nào thì phải tốn ít nhất 2n-1 bước. Dễ thấy rằng độ phức tạp của bài toán này cũng cỡ O(2n). Như vậy bài toán
này không thuộc lớp của bài toán đa thức. Với n vào khoảng 16, số bước cần thiết chỉ khoảng vài chục ngàn là hoàn toàn
giải được trên các máy tính hiện nay. Nhưng khi số phần tử lên đến 32 thì ta đã tốn một số bước lên đến 4 tỷ, chỉ thêm
một phần tử nữa thôi, chúng ta đã tốn 8 tỷ bước! Với số lượng bước như vậy, dù chạy trên một siêu máy tính cũng phải
tốn một thời gian đáng kể! Các bài toán không thuộc lớp đa thức chỉ giải được với một độ lớn dữ liệu đầu vào nhất định.
4.3. Lớp bài toán NP Chúng ta đều biết rằng tính xác định là một trong ba đặc tính quan trọng của thuật toán. Nghĩa
là mỗi bước của thuật toán phải được xác định duy nhất và có thể thực thi được. Nếu có sự phân chia trường hợp tại một
bước thì thông tin tại bước đó phải đầy đủ để thuật toán có thể tự quyết định chọn lựa trường hợp nào. Trong mục 4.3
này, ta tạm gọi các thuật toán thỏa mãn tính xác định là các thuật toán tự quyết.
Vậy thì điều gì sẽ xảy ra nếu ta đưa ra một "thuật toán" có tính không tự quyết? Nghĩa là tại một bước của "thuật
toán", ta đưa ra một số trường hợp chọn lựa nhưng không cung cấp đầy đủ thông tin để "thuật toán" tự quyết định? Thật
ra, trong cuộc sống, những "thuật toán" thuộc loại này rất hay được áp dụng. Chẳng hạn ta có một lời chỉ dẫn khi đi du
lịch : "Khi đi hết khu vườn này, bạn hãy chọn một con đường mà bạn cảm thấy thích. Tất cả đều dẫn đến bảo tàng lịch
sử.". Nếu là khách du lịch, bạn sẽ cảm thấy bình thường. Nhưng máy tính thì không! Nó không thể thực thi những hướng
dẫn không rõ ràng như vậy! Ðến đây, lập tức sẽ có một câu hỏi rằng "Tại sao lại đề cập đến những thuật toán có tính
không tự quyết dù máy tính không thể thực hiện một thuật toán như vậy?". Câu trả lời là, khi nghiên cứu về thuật toán
không tự quyết, dù không dùng để giải bài toán nào đi nữa, chúng ta sẽ có những hiểu biết về hạn chế của những thuật
toán tự quyết thông thường.
Ðến đây, ta hãy xem sự khác biệt về độ phức tạp của một thuật toán tự quyết và không tự quyết để giải quyết cho cùng một vấn đề.
Bài toán người bán hàng
Một nhân viên phân phối hàng cho một công ty được giao nhiệm vụ phải giao hàng cho các đại lý của công ty, sau đó trở
về công ty. Vấn đề của người nhân viên là làm sao đi giao hàng cho tất cả đại lý mà không tiêu quá số tiền đổ xăng mà
công ty cấp cho mỗi ngày. Nói một cách khác, làm sao đừng đi quá một số lượng cây số nào đó.
Một lời giải cổ điển cho bài toán này là liệt kê một cách có hệ thống từng con đường có thể đi, so sánh chiều dài mỗi con
đường tìm được với chiều dài giới hạn cho đến lúc tìm được một con đường phù hợp hoặc đã xét hết tất cả các con
đường có thể đi. Tuy nhiên, cách giải quyết này có độ phức tạp không phải đa thức. Bằng toán học, người ta đã chứng Trang 14/268
minh được rằng độ phức tạp của thuật toán này là O(n!). Như vậy, với số đại lý lớn thì thuật toán trên được xem là không
thực tế. Bây giờ, chúng ta xem qua một thuật toán không tự quyết.
1. Chọn một con đường có thể và tính chiều dài của nó.
2. Nếu chiều dài này không lớn hơn giới hạn thì báo là thành công, ngược lại báo chọn lựa sai.
Quan điểm của ta trong cách giải quyết này là nếu chọn sai thì là do lỗi của người chọn chứ không phải lỗi của thuật toán !.
Theo thuật toán này thì chi phí để tính chiều dài của con đường được chọn sẽ tỷ lệ với số đại lý; chi phí để so sánh chiều
dài quãng đường với giới hạn cho phép thì không liên quan đến số thành phố. Như vậy, chi phí của thuật toán này là một
hàm có dạng T = an+b với n là số đại lý và a,b là các hằng số. Ta kết luận rằng, độ phức tạp của thuật toán này là O(n)
hay độ phức tạp thuộc lớp đa thức.
Như vậy, nếu dùng thuật toán tự quyết thì bài toán người bán hàng sẽ có độ phức tạp không thuộc lớp đa thức, còn nếu
dùng thuật toán không tự quyết thì bài toán sẽ có độ phức tạp đa thức. Ðịnh nghĩa
Một bài toán khi được giải bằng một thuật toán không tự quyết mà có độ phức tạp thuộc lớp đa thức thì được gọi là một
bài toán đa thức không tự quyết hay viết tắt là bài toán NP.
Theo định nghĩa trên thì bài toán người bán hàng là bài toán thuộc lớp NP.
Cho đến nay người ta chưa chứng minh được rằng tồn tại hay không một thuật toán tự quyết có độ phức tạp đa thức cho
bài toán người bán hàng rong. Vì vậy, bài toán này (là một bài toán NP) chưa thể xếp được vào lớp đa thức hay không đa
thức. Do đó, lớp bài toán NP chưa thể phân loại là thuộc lớp đa thức hay không.
Dĩ nhiên, lớp bài toán NP cũng chứa những bài toán thuộc lớp đa thức thực sự, bởi vì nếu một bài toán được giải bằng
thuật toán tự quyết có độ phức tạp đa thức thì chắc chắn khi dùng thuật toán không tự quyết thì cũng sẽ có độ phức tạp đa thức.
5. THUẬT TOÁN ĐỆ QUY
Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã biết, một thuật toán
cần phải thỏa mãn 3 tính chất : – Tính hữu hạn. – Tính xác định – Tính đúng đắn Trang 15/268
Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất khó khăn. Trong khi đó,
nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách giải lại trở nên đơn giản hơn nhiều và có thể chấp
nhận được. Một trong những trường hợp đó là thuật toán đệ quy.
Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (hay
nói một cách nôm na là đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ lớn dữ liệu nhập nhỏ hơn, giá trị cần tính
toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ
kết quả ở cấp độ này, ta sẽ lần ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu.
Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa trên chính những đối tượng, khái niệm đó.
Ðịnh nghĩa giai thừa
Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là : 0! = 1
n! = (n-1)!n với mọi n>0
Ðịnh nghĩa dãy số Fibonacci f0 = 1 f1 = 1
fn = fn-1 + fn-2 với mọi n>1
Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp. Chính vì vậy, đệ quy có
sự liên hệ rất chặt chẽ với quy nạp toán học.
Ðệ quy mạnh ở điểm nó có thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy
nhiên, đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong thuật toán phải
được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ quy, bước thứ n không được xác định
ngay trong ngữ cảnh của nó mà phải xác định thông qua một bước thấp hơn. Chẳng hạn, để tính được giá trị phần tử thứ
5 của dãy Fibonacci theo định nghĩa ở trên, ta phải tính f3+f4, nhưng ta chưa biết giá trị f3 và f4 tại thời điểm này. Ðến
đây, ta phải lùi lại để tính f3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2,...Tất nhiên, là quá trình tính lùi này phải dừng sau
một số hữu hạn bước. Trong trường hợp này, điểm dừng chính là giá trị f1 và f0. Trang 16/268
Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn gọi là trường hợp
dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua trường hợp đặc biệt này. Ðối với việc tính
dãy Fibonacci, trường hợp dừng chính là giá trị của f0 và f1.
Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần:
Phần cơ sở Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu thuật toán đệ
quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý do này mà người ta đôi lúc còn gọi
phần cơ sở là trường hợp dừng. Phần đệ quy
Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với một cấp độ dữ liệu thấp hơn. Trang 17/268 6.THUẬT GIẢI
6.1. Mở rộng khái niệm thuật toán : thuật giải
Trong quá trình nghiên cứu giải quyết các vấn đề - bài toán, người ta đã đưa ra những nhận xét như sau :
Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không.
Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn
hoặc các điều kiện cho thuật toán khó đáp ứng.
Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được.
Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng
hai tiêu chuẩn của thuật toán : tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể
hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách
giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn, có nhiều trường hợp người ta chấp nhận các cách giải
thường cho kết quả tốt (nhưng không phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài
toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp
gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ.
Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi
là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở rộng cửa cho chúng ta trong việc tìm kiếm phương pháp
để giải quyết các bài toán được đặt ra.
Một trong những thuật giải thường được đề cập đến và sử dụng trong khoa học trí tuệ nhân tạo là các cách giải theo kiểu Heuristic.
6.2. Thuật giải Heuristic
Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau :
Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)
Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.
Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. Trang 18/268
Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ sở như sau:
Nguyên lý vét cạn thông minh :
Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm
hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam (Greedy):
Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của
từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
Nguyên lý thứ tự :
Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt. Hàm Heuristic:
Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Ðó là các hàm đánh giá thô, giá
trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách
hành động tương đối hợp lý trong từng bước của thuật giải.
Bài toán hành trình ngắn nhất - ứng dụng nguyên lý Greedy
Bài toán : Chúng ta trở lại với bài toán người bán hàng. Nhưng ở đây, yêu cầu bài toán hơi khác là làm sao tìm được
hành trình ngắn nhất có thể được.
Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường có thể đi, tính chiều dài của mỗi con đường đó rồi
tìm con đường có chiều dài ngắn nhất. Tuy nhiên, cách giải này lại có độ phức tạp O(n!) (tổng số hành trình có thể có là
n!). Do đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.
Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng một thuật giải Heuristic ứng dụng nguyên
lý Greedy. Tư tưởng của thuật giải như sau :
1. Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n đại lý rồi chọn đi theo con đường ngắn nhất.
2. Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên. Nghĩa là liệt kê tất cả con đường từ đại
lý ta đang đứng đến những đại lý chưa đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi.
Bạn có thể quan sát hình 2.14 để thấy được quá trình chọn lựa.
Theo nguyên lý Greedy, ta lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn chọn lựa cục bộ. Ta hy vọng
rằng, khi đi trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất. Ðiều này không phải lúc nào
cũng đúng. Với điều kiện trong hình 2.14 thì thuật giải cho chúng ta một hành trình có chiều dài là 14 trong khi hành
trình tối ưu là 13. Kết quả của thuật giải Heuristic trong trường hợp này chỉ lệch 1 đơn vị so với kết quả tối ưu. Trong khi
đó, độ phức tạp của thuật giải Heuristic này chỉ là O(n2). Tất nhiên, thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết
quả không tốt, thậm chí rất tệ như trường hợp ở hình 2.15. Trang 19/268
Bài toán phân việc – ứng dụng của nguyên lý thứ tự
Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2,...,Jm. Công ty có n máy gia công lần lượt là P1, P2, ...Pn.
Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ
tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang. Ðể gia công một công việc Ji trên một máy bất kỳ ta cần dùng
một thời gian tương ứng là ti. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất.
Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1.
Ta có một phương án phân công (L) như hình sau :
Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2,
công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực
hiện công việc đầu tiên mình...Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Theo lược đồ này, ta thấy Trang 20/268
Tài liệu liên quan:
-
Đề CTDL cuối kì - Đề thi cuối kì tham khảo. Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
150 75 -
Algorithm VN C5 Graph - cấu trúc dữ liệu thuật toán, Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
107 54 -
Đề thi cuối kỳ học phần Cấu trúc dữ liệu và Thuật toán - 132247. Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
119 60 -
Đề thi và đáp án môn DASA240179: Cấu trúc dữ liệu - HK I/2014. Môn Cấu trúc dữ liệu và thuật toán (Phenika) | Đại học Trường Đại học Phenika.
115 58