Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng thuật toán di truyền giải bài toán đóng thùng

Chia sẻ: Sơ Dương | Ngày: | Loại File: PDF | Số trang:123

Thêm vào BST

Báo xấu

29
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn "Ứng dụng thuật toán di truyền giải bài toán đóng thùng" tập trung vào xây dựng một thuật toán di truyền để giải bài toán đóng thùng (bin packing problem), một bài toán tối ưu tổ hợp thuộc lớp bài toán NP – khó có nhiều ứng dụng trong thực tế như thiết kế lập lịch tối ưu cho công việc; sắp xếp hàng hóa kho chứa và container tối ưu; cấp phát bộ nhớ hiệu quả; hỗ trợ thiết kế các vi mạch điện tử.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng thuật toán di truyền giải bài toán đóng thùng

bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi --------------------------------------- NGUYỄN NGỌC DƯƠNG NGUYỄN NGỌC DƯƠNG ngµnh CNTT ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v¨n th¹c sÜ NGµNH C¤NG NGHÖ TH¤NG TIN kho¸ 2007-2009 Hµ néi – 2009
bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi --------------------------------------- NGUYỄN NGỌC DƯƠNG ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v¨n th¹c sÜ C¤NG NGHÖ TH¤NG TIN Ngêi híng dÉn khoa häc : PGS.TS. NGUYÔN §øC NGHÜA Hµ Néi – 2009
Lời cảm ơn Đầu tiên tôi xin bày tỏ sự biết ơn sâu sắc PGS. TS. Nguyễn Đức Nghĩa, thầy đã tận tình giảng dạy chúng tôi các môn học chuyên ngành và nhiệt tình hướng dẫn, giúp đỡ tôi hoàn thành luận văn này. Tôi cũng muốn bày tỏ lòng biết ơn các thầy cô khoa Công nghệ Thông tin trường Đại học Bách khoa Hà Nội đã giảng dạy cho chúng tôi các môn học chuyên đề trong khóa học. Cuối cùng gia đình, đặc biệt người bạn đời của tôi, là những người rất quan trọng đã một lòng động viên và tạo điều kiện giúp tôi tập trung hoàn thành luận văn này. Mặc dù đã có nhiều cố gắng, nhưng vì kiến thức và thời gian hạn chế nên chắc chắn luận văn này còn nhiều thiếu sót. Tôi xin chân thành cảm ơn và rất mong nhận được những ý kiến đóng góp từ các thầy cô và các bạn. Những góp ý xin gửi về địa chỉ: Nguyễn Ngọc Dương Bộ môn Khoa học máy tính, khoa Công nghệ thông tin, trường Đại học Bách Khoa Hà Nội. Email: duongnn@it-hut.edu.vn hoặc nguyenngocduong@gmail.com Hà Nội, ngày 21 tháng 7 năm 2009 Nguyễn Ngọc Dương Học viên cao học Lớp Công nghệ thông tin 2007 – 2009 Trường Đại học Bách Khoa Hà Nội
MỤC LỤC Danh mục hình vẽ.....................................................................................................iv Danh mục bảng.........................................................................................................vi Danh mục thuật ngữ tiếng Anh............................................................................. vii Chương 1. MỞ ĐẦU .................................................................................................1 1.1. Lời mở đầu .......................................................................................................1 1.2. Các khái niệm và thuật ngữ cơ sở ....................................................................3 1.2.1. Bài toán tính toán, thuật toán và độ phức tạp tính toán của thuật toán .3 1.2.2. Các kí hiệu tiệm cận ...............................................................................6 1.2.3. Độ phức tạp tính toán của bài toán ........................................................8 1.2.4. NP- đầy đủ (NP – completeness) .........................................................11 1.3. Một số cách tiếp cận giải các bài toán NP-khó ..............................................18 1.3.1. Phương pháp xấp xỉ .............................................................................18 1.3.2. Phương pháp xác xuất ..........................................................................19 1.3.3. Phương pháp heuristic..........................................................................20 1.4. Bài toán đóng thùng .......................................................................................21 1.4.1. Phát biểu bài toán .................................................................................21 1.4.2. Các biến thể của bài toán đóng thùng ..................................................23 1.4.3. Ứng dụng của bài toán đóng thùng ......................................................25 Chương 2 MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐÓNG THÙNG ..... 27 2.1. Tổng quan các phương pháp giải bài toán đóng thùng ..................................27 2.2. Các phương pháp heuristic đơn giản .............................................................27 2.2.1. Các thuật toán trực tiếp ........................................................................27 2.2.2. Các phương pháp không trực tiếp ........................................................ 34 2.3. Phương pháp xấp xỉ .......................................................................................37 Chương 3 THUẬT TOÁN DI TRUYỀN...............................................................43 3.1. Sơ lược về tính toán tiến hóa và thuật toán di truyền .................................... 43 3.1.1. Lịch sử phát triển .................................................................................43 3.1.2. Đặc điểm và khả năng ứng dụng của tính toán tiến hóa ...................... 45 3.2. Sơ đồ hoạt động của thuật toán di truyền ......................................................46 3.2.1. Giới thiệu một số khái niệm .................................................................46
3.2.2. Sơ đồ chung của thuật toán di truyền ...................................................50 3.3. Các thành phần trong thuật toán di truyền .....................................................53 3.3.1. Mã hóa lời giải .....................................................................................53 3.3.2. Toán tử chọn lọc ..................................................................................56 3.3.3. Toán tử lai ghép ...................................................................................59 3.3.4. Toán tử đột biến ...................................................................................63 3.3.5. Một số tham số quan trọng khác ..........................................................65 3.4. Một số cơ sở toán học của thuật toán di truyền .............................................67 3.4.1. Định lý về các schemata....................................................................... 67 3.4.2. Giả thuyết về các building block và cơ chế song song ngầm. ............. 69 3.5. Đặc điểm và khả năng ứng dụng của thuật toán di truyền ............................70 3.5.1. Đặc điểm của thuật toán di truyền .......................................................70 3.5.2. Ứng dụng của thuật toán di truyền .......................................................70 Chương 4 THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG ...72 4.1. Mô tả cách tiếp cận bài toán đóng thùng theo thuật toán di truyền ............... 72 4.1.1. Biểu diễn lời giải ..................................................................................72 4.1.2. Mô tả sơ đồ thực hiện của thuật toán ................................................... 74 4.1.3. Xác định các thông số cho thuật toán ..................................................75 4.2. Kết quả thực nghiệm ......................................................................................98 4.2.1. Bộ dữ liệu thực nghiệm được sử dụng .................................................98 4.2.2. Kết quả chạy thực nghiệm ...................................................................99 4.2.3. Nhận xét và đánh giá ..........................................................................103 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ...........................................................109 Tài liệu tham khảo ................................................................................................111
Danh mục hình vẽ Hình 1. 1 Giải thích các kí hiệu tiệm cận O, Ω, Θ...................................................... 7 Hình 1. 2 Mối quan hệ giữa 3 lớp bài toán P, NP và Co-NP. ..................................14 Hình 1. 3 Sơ đồ phép quy dẫn ...................................................................................15 Hình 1. 4 Minh họa mối quan hệ giữa các lớp bài toán ........................................... 17 Hình 1. 5 Danh sách một số bài toán NP-khó và sơ đồ quy dẫn giữa chúng ........... 18 Hình 2. 1 Ví dụ về bộ dữ liệu trong đó thuật toán NF hoạt động tồi nhất ................29 Hình 2. 2 Ví dụ một bộ dữ liệu trong đó FF hoạt động tồi .......................................32 Hình 2. 3 Ví dụ về bộ dữ liệu trong đó FFD và BFD hoạt động tồi ........................ 35 Hình 2. 4 Minh họa các nhóm các đồ vật trong bài toán RBP .................................40 Hình 3. 1 Ví dụ mã hóa cây .......................................................................................56 Hình 3. 2 Minh họa lai ghép 1 điểm cắt....................................................................59 Hình 3. 3 Minh họa lai ghép 2 điểm cắt....................................................................60 Hình 3. 4 Minh họa lai ghép đồng bộ .......................................................................60 Hình 3. 5 Minh họa phép lai ghép theo thứ tự ..........................................................62 Hình 3. 6 Minh họa phép lai ghép đồng bồ theo thứ tự ............................................ 62 Hình 4. 1 Khảo sát sự phụ thuộc của thuật toán di truyền vào tham số kích thước quần thể .............................................................................................................82 Hình 4. 2 Khảo sát sự phụ thuộc của giải thuật vào tham số xác suất lai ghép....... 86 Hình 4. 3 Khảo sát sự phụ thuộc của giải thuật vào xác suất đột biến .................... 91
Hình 4. 4 Khảo sát sự phụ thuộc của giải thuật vào số vòng lặp và định mức rút gọn ...........................................................................................................................96 Hình 4. 5 So sánh chung các thuật toán trên toàn bộ 60 bộ test ............................ 103 Hình 4. 6 So sánh các thuật toán về số lượng bộ test giải tối ưu ...........................104 Hình 4. 7 So sánh trên các bộ test có 60 đồ vật ......................................................104 Hình 4. 8 So sánh trên các bộ test có 120 đồ vật ....................................................105 Hình 4. 9 So sánh trên các bộ test có 200 đồ vật ....................................................105 Hình 4. 10 So sánh trên các bộ test có khoảng 250 đồ vật ..................................... 106 Hình 4. 11 So sánh trên các bộ test có khoảng 500 đồ vật ....................................106 Hình 4. 12 So sánh hiệu quả của việc cài đặt thêm thủ tục leo đồi ........................ 107 Hình 4. 13 So sánh chi phí thời gian của việc cài đặt thêm thủ tục leo đồi............ 108
Danh mục bảng Bảng 4. 1 Kết quả thực nghiệm khi kích thước quần thể thay đổi ............................79 Bảng 4. 2 Tổng hợp đánh giá ảnh hưởng của kích thước quẩn thể ..........................81 Bảng 4. 3 Kết quả thực nghiệm khi xác suất lai ghép thay đổi .................................83 Bảng 4. 4 Tổng hợp đánh giá ảnh hưởng của xác suất lai ghép ..............................86 Bảng 4. 5 Kết quả thực nghiệm khi xác suất đột biến thay đổi .................................87 Bảng 4. 6 Tổng hợp đánh giá ảnh hưởng của xác suất đột biến .............................. 90 Bảng 4. 7 Kết quả thực nghiệm khi thay đổi số vòng lặp và định mức rút gọn ........93 Bảng 4. 8 Tổng hợp đánh giá ảnh hưởng của số vòng lặp và định mức rút gọn...... 95 Bảng 4. 9 Kết quả thực nghiệm giải thuật GA trên các bộ test ..............................100 Bảng 4. 10 Kết quả thực nghiệm giải thuật GA + R trên các bộ test .....................101 Bảng 4. 11 Kết quả thực nghiệm giải thuật GA + R + H trên một số bộ test......... 102
Danh mục thuật ngữ tiếng Anh STT Thuật ngữ Viết tắt Đề nghị dịch tiếng Việt 1 Approximation scheme Thuật toán xấp xỉ, sơ đồ xấp xỉ 2 Probabilistic method Phương pháp xác xuất 3 Evolutionary computation Tính toán tiến hóa 4 Local search Tìm kiếm cục bộ 5 Genetic algorithm GA Thuật toán di truyền Hybrid GA Thuật toán di truyền lai 6 Bin packing problem BPP Bài toán đóng thùng 7 Relative performance ration Đảm bảo về tỷ số chênh lệch tương đối Absolute performance 8 Đảm bảo về sai số tuyệt đối guarantee Polynomial time 9 PTAS Sơ đồ xấp xỉ trong thời gian đa thức approximation schemes Asymptotic worst-case 10 R ∞A Chỉ số hiệu năng tiệm cận tồi nhất performance ratio Absolute worst-case 11 RA Chỉ số hiệu năng tuyệt đối tồi nhất performance ratio 12 Dynamic bin packing Bài toán đóng thùng động 13 Bin covering problem Bài toán phủ thùng Bài toán đóng thùng với dung lượng thùng 14 Variable-sized bin packing chứa thay đổi 15 Multi-dimensional bin packing Bài toán đóng thùng đa chiều 16 Restricted Bin Packing - RBP Bài toán đóng thùng có ràng buộc 17 Online algorithms Thuật toán tức thì, thuật toán trực tiếp 18 Off-line algorithms Thuật toán không trực tiếp, không tức thì 19 Next fit NF Thuật toán khớp kế tiếp 20 First fit FF Thuật toán khớp đầu tiên 21 Best fit BF Thuật toán khớp nhiều nhất 22 Worst fit WF Thuật toán khớp ít nhất 23 First fit decreasing FFD Thuật toán khớp đầu tiên giảm dần 24 Best fit decreasing BFD Thuật toán khớp nhiều nhất giảm dần
STT Thuật ngữ Viết tắt Đề nghị dịch tiếng Việt 25 Next fit decreasing NFD Thuật toán khớp kế tiếp giảm dần 26 Population Quần thể 27 Chromosomes Nhiễm sắc thể 28 Individual Cá thể 29 Genetic-inspired operators Toán tử di truyền 30 Selection Chọn lọc tự nhiên 31 Crossover, Recombination Lai ghép – hay còn gọi là ghép chéo 32 Mutation Hiện tượng đột biến 33 Inversion Đảo đoạn 34 Fitness Độ thích nghi Evaluation function 35 Hàm mục tiêu Object function 36 Fitness landscape Không gian thích nghi 37 Generation Thế hệ 38 Roulette wheel selection Cơ chế lựa chọn theo bánh xe Roulette 39 Stochastic universal sampling Cơ chế lấy mẫu ngẫu nhiên toàn phần 40 Rank selection Chọn lọc xếp hạng 41 Tournament selection Chọn lọc theo giao đấu 42 K-point crossover Lai ghép theo điểm cắt 43 Uniform crossover Lai ghép đồng bộ 44 Order-based crossover Lai ghép theo thứ tự Uniform order-based 45 Lai ghép đồng bộ theo thứ tự crossover 46 Partially Matched Crossover PMC Lai ghép tương hợp bộ phận 47 Hill climbing Kỹ thuật leo đồi 48 Reduction Size Kỹ thuật rút gọn kích thước lời giải Đơn vị cấu tạo lời giải 49 Building blocks Bộ phận lời giải hữu ích 50 Elitism Cơ chế bảo toàn một số cá thể ưu tú 51 Triplet Phân bố theo bộ 3
Chương 1. MỞ ĐẦU 1.1. Lời mở đầu Phát triển các thuật toán giải các bài toán NP – khó (NP – hard) luôn là hướng quan tâm của nhiều nhà khoa học nghiên cứu về máy tính. Nhiều bài toán NP – khó là các bài toán tối ưu tổ hợp nổi tiếng có nhiều ứng dụng trong thực tiễn như bài toán người du lịch, bài toán đóng thùng, bài toán cây Steiner, bài toán người đưa thư Trung Hoa, … xong cho đến nay chưa thể giải được chính xác bằng các thuật toán hiệu quả. Người ta thường lựa chọn cách tiếp cận giải gần đúng đối với các bài toán thuộc lớp này. Có thể nêu tên các phương pháp giải như vậy như: các thuật toán xấp xỉ (approximation schemes), các phương pháp xác xuất (probabilistic methods), tính toán tiến hóa (evolutionary computation), tìm kiếm cục bộ (local search), … Thuật toán di truyền (genetic algorithm) là một nhánh quan trọng của tính toán tiến hóa gần đây được quan tâm nhiều khi tỏ ra hiệu quả trong việc giải một số bài toán thuộc lớp bài toán NP – khó. Nội dung của luận văn này tập trung vào xây dựng một thuật toán di truyền để giải bài toán đóng thùng (bin packing problem), một bài toán tối ưu tổ hợp thuộc lớp bài toán NP – khó có nhiều ứng dụng trong thực tế như thiết kế lập lịch tối ưu cho công việc; sắp xếp hàng hóa kho chứa và container tối ưu; cấp phát bộ nhớ hiệu quả; hỗ trợ thiết kế các vi mạch điện tử, … Thuật toán đề xuất được chạy thử trên các bộ dữ liệu thử nghiệm được lấy từ OR – library và một số nguồn khác để đánh giá. Lời giải thu được là khá tốt khi so sánh với một số thuật toán khác và lời giải tối ưu đã
biết. Qua đó phần nào cho thấy khả năng ứng dụng của thuật toán di truyền vào việc tìm lời giải cho các bài toán thuộc lớp bài toán NP – khó nói chung. Nội dung của luận văn được bố cục như sau: Chương 1: Mở đầu Chương này trình nhắc lại một số kiến thức cơ sở trong lý thuyết tính toán và các khái niệm về bài toán, bài toán NP – đầy đủ, NP – khó, … Một số phương pháp giải các bài toán NP – khó cũng được giới thiệu sơ qua. Tiếp theo là phát biểu bài toán đóng thùng, mô hình toán học của bài toán và một số ứng dụng của bài toán. Chương 2: Một số phương pháp giải bài toán đóng thùng Trong chương này sẽ giới thiệu tổng quan chung về các kết quả nghiên cứu bài toán đóng thùng, đặc biệt là các thuật toán đã đề xuất và đánh giá hiệu quả của chúng. Một số thuật toán quan trọng sẽ được đề cập chi tiết hơn. Chương 3: Thuật toán di truyền Chương 3 nhắc lại một chút về lịch sử thuật toán di truyền, mô tả sơ đồ hoạt động chung và một số nền tảng lý thuyết khác của thuật toán di truyền. Chương 4: Thuật toán di truyền giải bài toán đóng thùng Chương này sẽ trình bày cụ thể cách tiếp cận theo hướng thuật toán di truyền để giải bài toán đóng thùng, các mô tả chi tiết thiết kế của thuật toán, trình bày các kết quả thực nghiệm và đánh giá kết quả thực nghiệm thu được. Chương 4 là nội dung chính của luận văn. Kết luận và hướng phát triển Phần kết luận chung đánh giá tổng quan lại những kết quả đã thực hiện được trong luận văn, những hạn chế của luận văn và một số vấn đề mở cần tiếp tục giải quyết sau này.
1.2. Các khái niệm và thuật ngữ cơ sở Nội dung phần này được trình bày dựa vào các tài liệu tham khảo [1], [9]. 1.2.1. Bài toán tính toán, thuật toán và độ phức tạp tính toán của thuật toán Các vấn đề kĩ thuật thường được khái quát dưới dạng bài toán tính toán để tiện cho việc nghiên cứu và xây dựng cách giải quyết. Bài toán tính toán là mối quan hệ giữa đầu vào (những yếu tố cho trước của bài toán) và đầu ra (những kết quả tính toán cần đạt được) của bài toán. Một cách hình thức, ta có thể định nghĩa bài toán tính toán như sau: Định nghĩa 1.1. Bài toán tính toán F là ánh xạ từ các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F: {0,1} * → {0,1}*. Ở đây, các yếu tố dữ liệu là đầu vào và đầu ra của bài toán được biểu diễn bằng xâu nhị phân. Mọi dạng dữ liệu (số, kí tự, xâu, mảng, tập hợp…) đều có thể mã hóa được bằng xâu nhị phân, hay nói cách khác ta có thể dùng xâu nhị phân để biểu diễn mọi dạng dữ liệu. Ví dụ:  Một số nguyên z có biểu diễn dưới dạng xâu nhị phân chính là cách viết trong hệ đếm cơ số 2 của số nguyên đó.  Một kí tự có biểu diễn nhị phân là biểu diễn nhị phân của số nguyên là số thứ tự của kí tự đó trong một bảng mã nào đó (ASCII, Unicode …)  Vector có biểu diễn là ghép nối biểu diễn nhị phân (mảng – array) của các thành phần tọa độ của các chiều.  Xâu kí tự có biểu diễn là ghép nối biểu diễn của các kí tự thành phần  Ma trận được biểu diễn bởi ghép nối các biểu diễn của các vector thành phần hoặc ma trận thành phần cấp thấp hơn nó một đơn vị.
 Một hệ phương trình tuyến tính dạng A.x = b có thể biểu diễn dưới dạng nhị phân là ghép nối của các xâu biểu diễn nhị phân của các thành phần trong ma trận A và vector b.  Đa thức một biến dạng P(x) = a0 + a 1x + …+anxn được đặc trưng bởi dãy các hệ số a 0, a 1,…, a n và số mũ n. Do đó dùng các xâu nhị phân biểu diễn dãy hệ số a i và xâu nhị phân biểu diễn n là tao có thể tạo thành một biểu diễn hợp lệ cho P(x).  Đồ thị thì có biểu diễn bởi ma trận kề  Các dữ liệu phức hợp thì được tổ chức dưới dạng tổ hợp cấu trúc của các dữ liệu cơ bản, ví dụ như mảng, bản ghi, cây … Các dữ liệu trong các bài toán tổng quát thì có thể là không hữu hạn (số vô cùng lớn chẳng hạn) nhưng khi đã chuyển sang dạng bài toán tính toán để phục vụ cho việc ứng dụng thực tế thì yếu tố vô hạn cần phải được thay thế bằng yếu tố hữu hạn, vì vậy các xâu nhị phân là hữu hạn. Bài toán chỉ ra mối quan hệ giữa đầu vào và đầu ra, nhưng làm thế nào để đạt được đầu ra từ đầu vào cho trước thì ta cần thuật toán (algorithm – thuật toán). Định nghĩa 1.2. Thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm một dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán. Thuật toán có những đặc trưng là:  Có đầu vào (Input): là tập các dữ liệu cần cung cấp thuật toán từ lúc đầu để xử lý.  Có đầu ra (Output): với mỗi một bộ dữ liệu vào, thuật toán sẽ cho ra một bộ các dữ liệu ra tương ứng với lời giải của bài toán cho bộ dữ liệu vào.  Chính xác (Precision): Các bước của thuật toán cần phải được mô tả chính xác và rõ ràng để có thể khi cài đặt trên máy tính có thể thực hiện được.  Hữu hạn (Finiteness): với mọi đầu vào thì thuật toán vẫn cần phải đưa được đầu ra sau một số hữu hạn (có thể rất lớn) bước thực hiện.
 Đơn trị (Uniqueness): đơn trị có nghĩa là các kết quả trung gian trong quá trình thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào cũng như kết quả ở những bước trước.  Tổng quát (Generality): Tức là thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. Với mọi thuật toán, bên cạnh tính đúng đắn người ta còn quan tâm đến một yếu tố khác là độ phức tạp tính toán của thuật toán đó. Định nghĩa 1.3. Độ phức tạp tính toán của một thuật toán là lượng tài nguyên tính toán mà thuật toán đó sử dụng để thực hiện công việc. Có 2 loại tài nguyên cần quan tâm khi đánh giá độ phức tạp tính toán của thuật toán là bộ nhớ và thời gian. Ngày nay, do sự phát triển mạnh của công nghệ chế tạo bộ nhớ và thiết bị lưu trữ, người ta ít phải quan tâm đến vấn đề tài nguyên không gian nhớ thuật toán sử dụng hơn so với trước kia và tập trung quan tâm thiết kế để tiết kiệm thời gian tính toán cần thiết thuật toán đòi hỏi để thực hiện công việc, và ta vẫn thường gọi là thời gian tính. Thời gian tính cụ thể trên máy tính của 1 thuật toán phụ thuộc vào nhiều yếu tố: cấu hình máy, ngôn ngữ cài đặt và cách thức cài đặt thuật toán của lập trình viên, trình biên dịch và dữ liệu vào, trong đó dữ liệu vào là yếu tố quan trọng và đặc trưng nhất. Và để tạo ra sự thống nhất trong cách đánh giá thời gian tính của một thuật toán, ta sẽ không xét đến các yếu tố như cấu hình máy, kỹ thuật lập trình, chương trình dịch … mà chỉ xét đến yếu tố kích thước dữ liệu vào khi đánh giá thời gian tính của thuật toán. Kích thước dữ liệu vào (hay độ dài dữ liệu vào) được định nghĩa là số bit cần thiết để biểu diễn dữ liệu vào đó (ta đã biết rằng các dữ liệu đều có thể được biểu diễn bằng xâu nhị phân). Nhưng từ đó thì làm thế nào để đo được thời gian tính? Để đo thời gian tính của một thuật toán, người ta tiến hành đếm số phép toán cơ bản mà nó phải thực hiện. Phép toán cơ bản được định nghĩa là những phép toán có thể được thực hiện với thời gian bị chặn bởi một hằng số không phụ thuộc vào kích thước dữ liệu. Các phép tính toán học thông thường không là các phép tính cơ bản, ví dụ nhân hay cộng hai số nguyên thì thời gian tính toán kết quả rõ ràng phụ thuộc vào độ lớn (cũng như độ dài biểu diễn) của 2 số nguyên đó. Nhưng với những phép toán thực hiện trên một ngôn ngữ lập trình nào đó thì do kích thước của các kiểu dữ liệu do ngôn ngữ đó cung cấp là bị chặn cho nên thời gian thực hiện các thao tác với các dữ liệu này là bị chặn. Các phép toán số học, logic .. trên một ngôn ngữ lập trình cụ thể là các phép toán cơ bản.
Đánh giá thời gian tính của thuật toán theo kích thước dữ liệu vào thường được thể hiện dưới dạng các hàm số quan hệ giữa chúng. Mục tiếp theo sẽ trình bày về các ký hiệu tiệm cận (asymptotic notation) dùng để biểu diễn những mối quan hệ hàm này. 1.2.2. Các kí hiệu tiệm cận Các kí hiệu tiệm cận thường hay sử dụng khi đánh giá độ phức tạp tính toán của thuật toán gồm có: Θ, Ο, Ω và ο, ω. Các kí hiệu này được định nghĩa sử dụng như sau: Định nghĩa 1.4. Cho các hàm f(n) và g(n) là các hàm số của n nguyên dương.  Kí hiệu Θ(g(n)) biểu diễn tập các hàm Θ(g(n)) = {f(n) : tồn tại các hằng số dương c 1, c2 và n0 sao cho 0 ≤ c1g(n) ≤ f(n) ≤ c2 g(n), với mọi n ≥ n0.} Ta nói g(n) là đánh giá tiệm cận đúng của f(n) hay f(n) có bậc là g(n)  Kí hiệu Ο(g(n)) biểu diễn tập các hàm Ο(g(n)) = {f(n) : tồn tại các hằng số dương c và n 0 sao cho f(n) ≤ cg(n), với mọi n ≥ n0.} Ta nói g(n) là cận trên tiệm cận của f(n) hay f(n) có bậc không quá g(n)  Kí hiệu Ω(g(n)) biểu diễn tập các hàm Ω(g(n)) = {f(n) : tồn tại các hằng số dương c và n 0 sao cho cg(n) ≤ f(n), với mọi n ≥ n0.} Ta nói g(n) cận dưới tiệm cận của f(n) hay f(n) có bậc ít nhất là g(n).  Kí hiệu ο(g(n)) biểu diễn tập các hàm ο(g(n)) = {f(n) : với mọi hằng số c > 0, ta luôn tìm được một hằng số n0 sao cho 0 ≤ f(n) < cg(n), với mọi n ≥ n0.} Ta nói f(n) có bậc thấp hơn g(n)  Kí hiệu ω(g(n)) biểu diễn tập các hàm ω(g(n)) = {f(n) : với mọi hằng số c > 0, ta luôn tìm được một hằng số n0 sao cho f(n) > cg(n) ≥ 0, với mọi n ≥ n0.} Ta nói f(n) có bậc cao hơn g(n) Hình 1.1 minh hoạ cho các kí hiệu O, Ω, Θ.
Hình 1. 1 Giải thích các kí hiệu tiệm cận O, Ω, Θ. Ta cũng thấy rằng f(n) = Θ(g(n)) khi và chỉ khi đồng thời f(n) = Ω(g(n)) và f(n) = Ο(g(n)). Ta xét một số ví dụ minh họa:  6n2 - 3n = Θ(n 2). Thực vậy, với mọi n ≥ 3, c 1 = 5, c 2 = 6 ta luôn có c1n2 ≤ 6n2 - 3n ≤ c2 n 2. Hiển nhiên ta cũng có 6n2 - 3n = Ο(n 2) và 6n2 - 3n = Ω(n2)  3n2 + 3n + 10 = ο(n 3). Thực vậy, với mọi n ≥ 5, c = 1, ta luôn có 3n 2 + 3n + 10 < cn 3.  n2 – 6n – 9 = ω(n). Thực vậy, với mọi n ≥ 10, c = 2, ta luôn có n 2 – 6n – 9 > cn. Ta nhận thấy khi đánh giá tiệm cận thì người ta hay bỏ qua có hệ số và bỏ qua các số hạng có số mũ nhỏ. Sở dĩ như vậy là vì tốc độ tăng của hàm số khi n lớn phụ thuộc chủ yếu vào số mũ của số hạng có số mũ cao nhất. Để sử dụng các kí hiệu tiệm cận ở trên trong việc đánh giá thời gian tính của các thuật toán, ta có định nghĩa các quy ước như sau: Định nghĩa 1.5. • Nếu thuật toán có thời gian tính trong tình huống nhanh nhất (tốt nhất – best case) là t(n) với kích thước dữ liệu đầu vào là n và t(n) = Ω(g(n)) thì thời gian tính tốt nhất của thuật toán có bậc không nhỏ hơn g(n) hay thời gian tính tốt nhất của thuật toán là Ω(g(n)). • Nếu thuật toán đòi hỏi thời gian tính trong tình huống chậm nhất (tồi nhất – worst case) là t(n) với n là kích thước dữ liệu đầu vào và t(n) = O(g(n)) thì thời gian tính tồi nhất của thuật toán sẽ có bậc không quá g(n) hay thời gian tính tồi nhất của thuật toán là O(g(n)). • Nếu thuật toán đòi hỏi thời gian tính trung bình là t(n) với n là kích thước dữ liệu vào và t(n) = O(g(n)) thì thời gian tính trung bình của thuật toán có bậc không quá g(n) hay thời gian tính trung bình của thuật toán là O(g(n)).
Thông thường khi nói thuật toán có thời gian tính là O(f(n)), ta hiểu là thời gian tính của thuật toán đánh giá trong tình huống tồi nhất là O(f(n)). Còn khi nói thuật toán có thời gian tính là Ω(f(n)) thì ta hiểu đánh giá thời gian tính của thuật toán trong tình huống tốt nhất Ω(f(n)) 1.2.3. Độ phức tạp tính toán của bài toán Ở phần trên ta đã xét đến khái niệm độ phức tạp tính toán của một thuật toán. Với một bài toán thì có thể có nhiều thuật toán giải bài toán đó theo những hướng khác nhau. Vậy độ phức tạp tính toán của bài toán sẽ được xét như thế nào? Định nghĩa 1.6. Độ phức tạp tính toán của một bài toán là thời gian tính (ở đây ta chỉ quan tâm đến đánh giá thời gian thực hiện, bỏ qua đánh giá về yêu cầu bộ nhớ) của thuật toán tốt nhất trong số tất cả các thuật toán giải bài toán đó. Nhưng một vấn đề được đặt ra ngay sau định nghĩa trên đó là với một bài toán chắc chắn sẽ còn những thuật toán ta chưa biết, vậy làm thế nào để biết được thời gian tính của thuật toán tốt nhất. Có 2 cách để giải quyết vấn đề này  Cách thứ nhất là ta tìm cách để đưa ra cận dưới cho độ phức tạp tính toán của bài toán.  Cách thứ hai là ta tìm cách chỉ ra rằng bài toán đang xét có mức độ khó (tức là độ phức tạp tính toán) không thua kém gì bất kì một bài toán khó nào hiện biết. Sau đây ta sẽ trình bày về cách tiếp cận thứ nhất, còn cách tiếp cận thứ 2 sẽ được trình bày ở mục sau, trong phần về NP-đầy đủ. Định nghĩa 1.7. Gọi T A(X) là thời gian tính của thuật toán A đối với đầu vào X. Khi đó, thời gian tính trong tình huống tồi nhất của thuật toán A đối với dữ liệu đầu vào kích thước n được định nghĩa là thời gian tính lâu nhất của thuật toán A trong số tất cả các thời gian tính của A trên mọi bộ dữ liệu X có kích thước bằng n ( ) = max A ( ) . A = T n |X | T X Định nghĩa 1.8. Độ phức tạp trong tình huống tồi nhất của bài toán P là thời gian tính trong tình huống tồi nhất của thuật toán nhanh nhất để giải nó. Tức là TP ( n) = min TA ( n) = min (max TA ( X )) , A∈ ∆ A∈ ∆ X =n trong đó ∆ là tập tất cả các thuật toán giải bài toán P.
Thông thường do tính phức tạp của bài toán cũng như các thuật toán giải nó nên không dễ dàng gì để đưa ra một đánh giá chính xác cho thời gian tính của nó. Do đó thay vì đi tìm đánh giá đúng cho độ phức tạp tính toán của một bài toán, người ta có thể đi đánh giá phạm vi của độ phức tạp tính toán của bài toán đó, tức là đi tìm cận trên và cận dưới của nó. Định nghĩa 1.9. Nếu A là một thuật toán để giải bài toán P và A có thời gian tính trong tình huống tồi nhất là T A(n) = O(f(n)) thì rõ ràng TP (n) ≤ TA(n) = O(f(n)), tức là ta có cận trên cho độ phức tạp của bài toán P là O(f(n)). Định nghĩa 1.10. Để chỉ ra cận dưới của độ phức tạp tính toán của bài toán P là Ω(f(n)) TP (n) = Ω(f(n)) Thì ta cần phải chỉ ra được rằng mọi thuật toán giải bài toán P đều đòi hỏi thời gian tính trong tình huống tồi nhất là Ω(f(n)). Định nghĩa 1.11. Để chỉ ra rằng TP (n) = Θ(f(n)) Thì ta cần có đồng thời 2 điều kiện sau: i) Có thuật toán với thời gian tính Ο(f(n)) để giải bài toán P; ii) Mọi thuật toán giải bài toán P đều đòi hỏi thời gian tính trong tình huống tồi nhất là Ω(f(n)). Điều kiện ii) có thể thay bởi điều kiện ii *) Cận dưới cho độ phức tạp tính toán của bài toán P là Ω(f(n)) Vấn đề là làm sao để đánh giá được cận dưới của bài toán. Ta xét một ví dụ sau. Bài toán tìm số lớn nhất: cho dãy số gồm n số khác nhau từng đôi một (x 1, x2, …, xn). Chỉ dùng phép so sánh hãy tìm số lớn nhất trong dãy số trên. Ta sẽ chứng minh là mọi thuật toán A giải bài toán tìm số lớn nhất chỉ dùng phép so sánh sẽ phải dùng ít nhất n-1 phép so sánh mới có thể đưa ra câu trả lời chính xác. Thực vậy. Trước tiên ta coi mỗi phép so sánh 2 số xi và xj tương đương với một câu hỏi “xi nhỏ hơn xj phải không?”. Và ta chọn bộ dữ liệu vào là dãy số x1 , x2 , …, xn. Mỗi khi gặp câu hỏi “xi nhỏ hơn xj có phải không?” thì câu trả lời sẽ là đúng nếu i < j và là sai nếu i > j. Và khi một phần tử được xác định là nhỏ hơn một phần tử khác trong một lượt hỏi bất kì nào đó thì nó sẽ được coi là mất quyền ứng cử làm phần tử lớn nhất trong dãy số. Nếu tồn tại một thuật toán A* nào đó thực hiện ít hơn n-1 câu hỏi “xi nhỏ hơn xj phải không?” mà lại có thể đưa
ra chính xác phần tử lớn nhất của dãy số thì điều đó là vô lý. Đó là bởi vì chỉ bằng ít hơn n- 1 (hay tối đa là n-2) câu hỏi như vậy, thì thuật toán đó mới chỉ có thể loại bỏ tối đa n-2 phần tử làm ứng cử viên cho phần tử lớn nhất trong dãy số. Và sẽ còn 2 phần tử trong dãy số có quyền ứng cử làm phần tử lớn nhất là xj và xk với j ≠ k. a) Nếu thuật toán kết luận phần tử xi với i ≠ j và i ≠ k là phần tử lớn nhất thì rõ ràng điều này tự nó đã mâu thuẫn với quá trình hoạt động của chính thuật toán. b) Nếu thuật toán kết luận phần tử lớn nhất là xj thì ta chỉ việc cho xk > xj thì sẽ làm thuật toán sẽ hoạt động sai c) Nếu thuật toán kết luận phần tử lớn nhất là x k thì ta chỉ việc cho xk < xj ta sẽ có một phản ví dụ cho thuật toán này Như vậy ta luôn có thể đưa ra phản ví dụ cho thuật toán sử dụng ít hơn n-1 câu hỏi. Hay nói cách khác không thể tìm được phần tử lớn nhất của một dãy số gồm n số nếu dùng ít hơn n-1 phép so sánh (ta chú ý là ở đây một phép so sánh tương đương với một câu hỏi). Vậy cận dưới cho độ phức tạp của bài toán tìm số nguyên lớn nhất là n-1 = Ω(n). Nhưng mặt khác ta lại thấy rằng tồn tại thuật toán chỉ sử dụng n-1 phép so sánh là tìm ra được số lớn nhất trong dãy số trên // Giả sử dãy số được lưu trữ trong mảng số x[i], với i = 1, 2, …n. max = x[1]; for(i=2;i