Tài liệu Thiết kế và đánh giá thuật toán

Nội dung text: Tài liệu Thiết kế và đánh giá thuật toán

1. Lời nói đầu Xây dựng một thuật toán tốt để giải bài bài toán đã cho là bước quan trọng nhất trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật một thuật toán tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật toán cơ bản cho một số lớp bài bài toán điển hình. Tài liệu Thiết kế và đánh giá thuật toán được biên soạn nhằm phục vụ công việc giảng dạy và học tập môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Tài liệu cũng rất cần thiết cho tất cả các ngành học thuộc khoa Công nghệ thông tin. Nội dung của tài liệu trình bày các kỹ thuật thiết kế thuật toán thông dụng và cơ sở phân tích, đánh giá độ phức tạp của thuật toán. Tài liệu gồm 6 chương: Chương 1: Tổng quan về thiết kế và đánh giá thuật toán Chương 2: Kỹ thuật chia để trị Chương 3: Kỹ thuật tham lam Chương 4: Kỹ thuật quay lui Chương 5: Kỹ thuật nhánh và cận Chương 6: Kỹ thuật quy hoạch động Trong từng chương các vấn đề đưa ra đều được minh họa bằng các ví dụ. Cuối mỗi chương đều có một hệ thống các bài tập nhằm giúp người học củng cố các kiến thức đã được học đồng thời rèn luyện khả năng vận dụng các kiến thức để giải quyết một số bài toán trong thực tế. Với các bài tập khó tài liệu đã đưa ra hướng dẫn giải để giúp người học thuận lợi trong qua trình nghiên cứu và giải quyết các bài tập. Cuối tài liệu là phần cài đặt một số thuật toán đã được thiết kế nhằm giúp người học thuận lợi hơn trong việc nắm bắt và vận dụng các kỹ thuật thiết kế thuật toán. Tài liệu được biên soạn theo chương trình môn học Thiết kế và đánh giá thuật toán của ngành học Khoa học máy tính thuộc khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Nội dung tài liệu được biên soạn dựa trên cơ sở nội dung các bài giảng của tác giả trong một số năm qua tại khoa Công nghệ thông tin trường Đại học sư phạm kỹ thuật Nam Định. Trong quá trình biên soạn, tác giả đã nhận được nhiều ý kiến đóng góp cùng với sự động viên, khích lệ của bạn bè đồng nghiệp trong khoa và trong trường. Tác giả xin được tỏ lòng cảm ơn với những ý kiến đóng góp và động viên khích lệ này. i
2. Với lần biên soạn đầu tiên, mặc dù đã hết sức cố gắng song chắc chắn tài liệu không thể tránh khỏi những thiếu sót. Rất mong nhận được các ý kiến đóng góp để tài liệu ngày càng hoàn thiện hơn. Phạm Cao Hào ii
3. MỤC LỤC Chương 1. Tổng quan về thiết kế và đánh giá thuật toán 1 1.1. Thuật toán 1 1.1.1. Khái niệm thuật toán 1 1.1.2. Các đặc trưng cơ bản của thuật toán 1 1.2. Sự cần thiết của thiết kế và đánh giá thuât toán 2 1.3. Diễn tả thuật toán 3 1.4. Thiết kế thuật toán 7 1.4.1. Modul hoá và thiết kế từ trên xuống 7 1.4.2. Phương pháp là mịn dần (tinh chỉnh từng bước) 7 1.4.3. Một số kỹ thuật thiết kế 8 1.5. Phân tích thuật toán 9 1.5.1. Thời gian thực hiên thuật toán 9 1.5.2. Độ phức tạp tính toán của thuật toán 10 1.5.3. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui 16 1.5.4. Phân tích các thuật toán đệ quy 17 1) Thành lập phương trình truy hồi 18 2) Giải phương trình truy hồi 19 Bài tập chương 1. 31 Chương 2. Kỹ thuật chia để trị 37 2.1 Nội dung kỹ thuật 37 2.2. Các ví dụ áp dụng 37 2.2.1. Tìm min và max 37 2.2.2. Một số thuật toán sắp xếp 40 1) Sắp xếp nhanh 40 2) Sắp xếp trộn 44 2.2.3. Tìm kiếm nhị phân 51 2.2.4. Nhân các số nguyên lớn 53 Bài tập chương 2. 57 Chương 3. Kỹ thuật tham lam 62 3.1. Nội dung kỹ thuật 62 3.1.1. Bài toán tối ưu tổ hợp 62 3.1.2. Nội dung kỹ thuật tham lam 62 3.2. Các ví dụ áp dụng 62 iii
4. 3.2.1. Bài toán người giao hàng 62 3.2.2. Bài toán chiếc ba lô 65 3.2.3. Bài toán tô màu bản đồ 70 3.2.4. Tìm cây khung nhỏ nhất 74 3.2.5. Tìm đường đi ngắn nhất 77 3.2.6. Bài toán phân công công việc 79 Bài tập chương 3. 84 Chương 4. Kỹ thuật quay lui 86 4.1. Nội dung kỹ thuật 86 4.2. Các ví dụ áp dụng 87 4.2.1. Đưa ra các dãy nhị phân độ dài n 87 4.2.2. Đưa ra các hoán vị của n số nguyên 88 4.2.3. Đưa ra các tập con của tập gồm n số nguyên 90 4.2.4. Bài toán xếp hậu 92 4.2.5. Tìm đường đi trên đồ thị 94 4.2.6. Bài toán ngựa đi tuần 99 Bài tập chương 4 104 Chương 5. Kỹ thuật nhánh và cận 111 5.1. Nội dung kỹ thuật 111 5.2. Các ví dụ áp dụng 114 5.2.1. Bài toán người du lịch 114 5.2.2. Bài toán chiếc ba lô 128 Bài tập chương 5. 133 Chương 6. Kỹ thuật quy hoạch động 137 6.1. Nội dung kỹ thuật 137 6.2. Các ví dụ áp dụng 140 6.2.1. Tính số tổ hợp 140 6.2.2. Bài toán nhân nhiều ma trận 143 6.2.3. Bài toán chiếc ba lô 149 6.2.4. Xâu con chung dài nhất 154 Bài tập chương 6. 164 Phụ lục 171 Tài liệu tham khảo 195 iv
5. Chƣơng 1 TỔNG QUAN VỀ THIẾT KẾ VÀ ĐÁNH GIÁ THUẬT TOÁN 1.1. Thuật toán 1.1.1. Khái niệm thuật toán Thuật toán (Algorithm) đã được biết đến từ rất lâu. Đầu tiên thuật toán được hiểu như là các qui tắc thực hiện các phép tính số học với các con số được viết trong hệ thập phân. Cùng với sự phát triển của máy tính, khái niệm thuật toán được hiểu theo nghĩa rộng hơn. Khái niệm thuật toán được định nghĩa một cách hình thức chính xác thông qua máy Turing. ở đây chúng ta sẽ xem xét khái niệm thuật toán một cách trực quan. Thuật toán (hay giải thuật, thuật giải) là một khái niệm cơ sở của tin học. Mỗi bài toán trong thực tế bao gồm hai phần: - Input: Các đại lượng cho trước (đại lượng vào) - Output: Các đại lượng cần tìm (đại lượng ra) Như vậy việc giải bài toán là việc xác định tường minh output theo input bằng một quá trình có thể thực hiện một cách hiệu quả. Đó chính là nội dung cơ bản của lý thuyết tính toán. Khi cho bài toán, ta cần tìm ra một dãy hữu hạn các thao tác đơn giản được sắp xếp theo một trình tự xác định sao cho theo đó, từ input ta sẽ tìm ra được output theo yêu cầu. Một cách trực quan thuật toán giải một bài toán là một dãy hữu hạn các chỉ dẫn (quy tắc, thao tác hay phép toán) hết sức rõ ràng và chính xác được sắp xếp theo một trình tự xác định để sao cho sau một số hữu hạn lần thực hiên các chỉ dẫn đó thì biến đổi được input thành output. 1.1.2. Các đặc trƣng cơ bản của thuật toán 1) Dữ liệu vào Mỗi thuật toán có thể có một hoặc nhiều đại lượng vào mà ta thường gọi là dữ liệu vào 2) Dữ liệu ra Sau khi thực hiên xong thuật toán, tuỳ theo chức năng mà thuật toán đảm nhiệm ta có thể thu được một số đại luợng ra mà ta gọi là dữ liệu ra. 3) Tính xác định Tính xác định của thuật toán đòi hỏi ở chỗ ở mỗi bước các thao tác phải hết sức rõ ràng, không thể gây nên sự nhập nhằng, lẫn lộn, tuỳ tiện. Nói cách khác trong cùng một điều kiện hai bộ xử lý (người hoặc máy) thực hiện cùng một bước của thuật toán thì phải cho cùng một kết quả. 1
6. 4) Tính dừng Thuật toán phải dừng và cho kết quả sau một số hữu hạn bước thực hiện. 5) Tính hiệu quả Yêu cầu của tính hiệu quả là trong số các thuật toán thực hiện cùng một chức năng ta cần chọn thuật toán tốt nhất. Tiêu chuẩn tốt ở đây được hiểu là: thuật toán thực hiện nhanh, tốn ít thời gian nhất, dùng ít giấy hoặc từ nhớ để lưu trữ các kết quả trung gian. 6) Tính phổ dụng Một thuật toán được xem là có tính phổ dụng cao nếu nó có thể dùng để giải bất cứ bài toán nào trong một lớp các bài toán chứ không phải là một bài toán cụ thể. 1.2. Sự cần thiết của thiết kế và đánh giá thuật toán Xây dựng một thuật toán tốt để giải bài toán đã cho là bước quan trọng nhất trong việc giải bài toán đó trên máy tính điện tử. Để có được một thuật toán tốt cần phải nắm vững các kỹ thuật thiết kế, phân tích, đánh giá thuật toán cùng các thuật toán cơ bản cho một số lớp bài toán điển hình. Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau, vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau: (1) Thuật toán đúng đắn. (2) Thuật toán đơn giản. (3) Thuật toán thực hiện nhanh. Với yêu cầu (1), để kiểm tra tính đúng đắn của thuật toán chúng ta có thể cài đặt thuật toán đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì có thể thuật toán đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra thuật toán sai chứ chưa chứng minh được là nó đúng. Tính đúng đắn của thuật toán cần phải được chứng minh bằng toán học. Điều này không đơn giản và do vậy chúng ta sẽ không đề cập đến ở đây. Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là quan trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả , thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm thời gian thực hiện chương 2
7. trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của thuật toán. 1.3. Diễn tả thuật toán Có nhiều cách diễn tả thuật toán. Người ta thường diễn tả thuật toán bằng một trong các cách sau: 1) Liệt kê từng buớc Thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiện theo trình tự các bước thực hiện trong thuật toán 2) Sơ đồ khối (Lưu đồ) Dùng các hình vẽ (có qui ước) để diễn tả thuật toán. Lưu đồ cho hình ảnh trực quan và tổng thể của thuật toán nên thường được sử dụng. 3) Ngôn ngữ lập trình Dùng cấu trúc lệnh, dữ liệu của một ngôn ngữ lập trình nào đó để mô tả. 4) Dạng giả mã Thuật toán trình bày dưới dạng văn bản bằng ngôn ngữ tự nhiên tuy dễ hiểu nhưng khó cài đặt. Dùng một ngôn ngữ lập trình nào đó để diễn tả thì phức tạp, khó hiểu. Thông thường thuật toán cũng được trình bày dưới dạng văn bản và không ràng buộc nhiều vào cú pháp qui định của ngôn ngữ lập trình, nhưng cũng tuân theo một số qui ước ban đầu- Ta gọi dạng này là dạng giả mã. Tuỳ theo việc định hướng cài đặt thuật toán theo ngôn ngữ lập trình nào mà tả fiễn đạt thuật toán gần với ngôn ngữ ấy. Trong tài liệu naứy ta trình bày các thuật toán dưới dạng giả mã của ngôn ngữ lập trình C. Dưới đây là một số quy ước của ngôn ngữ lập trình C: * Các ký tự - Bộ chữ cái: 26 chữ cái - 10 chữ số thập phân. - Các dấu phép toán số học. - Các dấu phép toán quan hệ. . . . * Các phép toán số học và logic Các từ sau xem như là các từ khoá : if, else, case, for, while , do while 3
8. * Các phép toán số học và logic - Các phép toán số học : +, -, *, /, %. - Các phép toán Logic : &&, ||, ! * Lệnh gán: biến=biểu thức; * Khối lệnh: { A1; A2; An; } * Cấu trúc rẽ nhánh if Toán tử if cho phép lựa chọn chạy theo một trong hai nhánh tuỳ thuộc vào sự bằng không và khác không của biểu thức. Nó có hai cách viết sau : if (biểu thức) if (biểu thức) khối lệnh 1 khối lệnh 1 /* Dạng một */ else khối lệnh 2 /* Dạng hai */ Sự lồng nhau của các toán tử if : C cho phép sử dụng các toán tử if lồng nhau có nghĩa là trong các khối lệnh (1 và 2) ở trên có thể chứa các toán tử if - else khác. Trong trường hợp này, nếu không sử dụng các dấu đóng mở ngoặc cho các khối thì sẽ có thể nhầm lẫn giữa các if-else. Chú ý là máy sẽ gắn toán tử else với toán tử if không có else gần nhất. * Cấu trúc rẽ nhánh - toán tử switch: switch (biểu thức nguyên) { case n1 khối lệnh 1 case n2 4
9. khối lệnh 2 case nk khối lệnh k [ default khối lệnh k+1] } Với ni là các số nguyên, hằng ký tự hoặc biểu thức hằng. Các ni cần có giá trị khác nhau. Đoạn chương trình nằm giữa các dấu { } gọi là thân của toán tử switch. default là một thành phần không bắt buộc phải có trong thân của switch. * Cấu trúc lặp với toán tử while : Toán tử while dùng để xây dựng chu trình lặp dạng : while (biểu thức) Lệnh hoặc khối lệnh; Như vậy toán tử while gồm một biểu thức và thân chu trình. Thân chu trình có thể là một lệnh hoặc một khối lệnh. Hoạt động của chu trình như sau : Máy xác định giá trị của biểu thức, tuỳ thuộc giá trị của nó máy sẽ chọn cách thực hiện như sau : Nếu biểu thức có giá trị 0 (biểu thức sai), máy sẽ ra khỏi chu trình và chuyển tới thực hiện câu lệnh tiếp sau chu trình trong chương trình. Nếu biểu thức có giá trị khác không (biểu thức đúng), máy sẽ thực hiện lệnh hoặc khối lệnh trong thân của while. Khi máy thực hiện xong khối lệnh này nó lại thực hiện xác định lại giá trị biểu thức rồi làm tiếp các bước như trên. * Cấu trúc lặp với toán tử for : Toán tử for dùng để xây dựng cấu trúc lặp có dạng sau : for (biểu thức 1; biểu thức 2; biểu thức 3) Lệnh hoặc khối lệnh ; Toán tử for gồm ba biểu thức và thân for. Thân for là một câu lệnh hoặc một khối lệnh viết sau từ khoá for. Bất kỳ biểu thức nào trong ba biểu thức trên có thể 5
10. vắng mặt nhưng phải giữ dấu ; Thông thường biểu thức 1 là toán tử gán để tạo giá trị ban đầu cho biến điều khiển, biểu thức 2 là một quan hệ logic biểu thị điều kiện để tiếp tục chu trình, biểu thức ba là một toán tử gán dùng để thay đổi giá trị biến điều khiển. Hoạt động của toán tử for : Toán tử for hoạt động theo các bước sau : Xác định biểu thức 1 Xác định biểu thức 2 Tuỳ thuộc vào tính đúng sai của biểu thức 2 để máy lựa chọn một trong hai nhánh : Nếu biểu thức 2 có giá trị 0 (sai), máy sẽ ra khỏi for và chuyển tới câu lệnh sau thân for. Nếu biểu thức 2 có giá trị khác 0 (đúng), máy sẽ thực hiện các câu lệnh trong thân for. Tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu trình. * Cấu trúc do-while Khác với các toán tử while và for, việc kiểm tra điều kiện kết thúc đặt ở đầu chu trình, trong chu trình do while việc kiểm tra điều kiện kết thúc đặt cuối chu trình. Như vậy thân của chu trình bao giờ cũng được thực hiện ít nhất một lần. do Lệnh hoặc khối lệnh; while (biểu thức) ; Hoạt động của chu trình như sau : Máy thực hiện các lệnh trong thân chu trình. Khi thực hiện xong tất cả các lệnh trong thân của chu trình, máy sẽ xác định giá trị của biểu thức sau từ khoá while rồi quyết định thực hiện như sau : Nếu biểu thức đúng (khác 0) máy sẽ thực hiện lặp lại khối lệnh của chu trình lần thứ hai rồi thực hiện kiểm tra lại biểu thức như trên. Nếu biểu thức sai (bằng 0) máy sẽ kết thúc chu trình và chuyển tới thực hiện lệnh đứng sau toán tử while. 6
11. Những điều lưu ý với toán tử while ở trên hoàn toàn đúng với do while. * Câu lệnh break Câu lệnh break cho phép ra khỏi các chu trình với các toán tử for, while, do while và switch. Khi có nhiều chu trình lồng nhau, câu lệnh break sẽ đưa máy ra khỏi chu trình bên trong nhất chứa nó không cần điều kiện gì. * Câu lệnh continue : Trái với câu lệnh break, lệnh continue dùng để bắt đầu một vòng mới của chu trình chứa nó. Trong while và do while, lệnh continue chuyển điều khiển về thực hiện ngay phần kiểm tra, còn trong for điều khiển được chuyển về bước khởi đầu lại (tức là bước : tính biểu thức 3, sau đó quay lại bước 2 để bắt đầu một vòng mới của chu trình). Lệnh continue chỉ áp dụng cho chu trình chứ không áp dụng cho switch. 1.4. Thiết kế thuật toán 1.4.1. Modul hoá và thiết kế từ trên xuống Các bài toán giải được trên máy tính ngày càng phức tạp và đa dạng. Các thuật toán giải chúng ngày càng có quy mô lớn đòi hỏi nhiều thời gian và công sức của nhiều người. Tuy nhiên công việc sẽ đơn giản hơn nếu như ta chia bài toán ra thành các bài toán nhỏ. Điều đó cũng có nghĩa là nếu coi bài toán là modul chính thì cần chia thành các modul con. Đến lượt mình các modul con lại phân rã thành các modul con thích hợp Như vậy việc tổ chức lời giải thể hiện theo một cấu trúc phân cấp. Chiến thuật giải bài toán như vậy là “chia để trị”, thể hiện chiến thuật đó ta dùng thiết kế từ trên xuống. Đó là cách nhìn nhận vấn đề một cách tổng quát, đề cập đến các công việc chính, sau đó mới bổ sung dần các chi tiết. 1.4.2. Phƣơng pháp làm mịn dần (tinh chỉnh từng bƣớc) Đầu tiên thuật toán được trình bày dưới dạng ngôn ngữ tự nhiên thể hiện ý chính công việc. Các bước sau sẽ chi tiết hóa dần tương ứng với các công việc nhỏ hơn. Đó là các bước làm mịn dần đặc tả thuật toán và hướng về ngôn ngữ lập trình mà ta dự định cài đặt. Quá trình thiết kế và phát triển thuật toán sẽ thể hiện dần từ ngôn ngữ tự nhiên, sang ngôn ngữ mã giả rồi đến ngôn ngữ lập trình, và đi từ mức “làm cái gì“đến “làm như thế nào”. 7
12. 1.4.3. Một số kỹ thuật thiết kế Trên cơ sở lý thuyết máy Turing, người ta chia được các bài toán thành 2 lớp không giao nhau : Lớp giải được bằng thuật toán, và lớp không giải được bằng thuật toán. Đối với lớp các bài toán giải được bằng thuật toán, dựa vào các đặc trưng của quá trình thiết kế của thuật toán, ta có thể chỉ ra một số các kỹ thuật thiết kế thuật toán cơ bản sau đây : 1) Kỹ thuật chia để trị Chia bài toán thành các bài toán đủ nhỏ, giải các bài toán nhỏ rồi tổng hợp kết quả lại . 2) Kỹ thuật quay lui Tìm kiếm theo ưu tiên. Đối với mỗi bước thuật toán, ưu tiên theo độ rộng hay chiều sâu để tìm kiếm. Chẳng hạn thuật toán giải bài toán 8 hậu. 3) Kỹ thuật tham lam Ý tưởng là : Xác định trật tự xử lý để có lợi nhất, Sắp xếp dữ liệu theo trật tự đó, rồi xử lý dữ liệu theo trật tự đã nêu. Công sức bỏ ra là tìm ra trật tự đó. Chẳng hạn thuật toán tìm cây khung nhỏ nhất. 4) Kỹ thuật nhánh và cận Trong quá trình tìm kiếm lời giải, ta phân hoạch tập các phương án của bài toán ra thành hai hay nhiều tập con được biểu diễn như là các nút của cây tìm kiếm và cố gắng bằng phép đánh giá cận cho các nút, tìm cách loại bỏ các nhánh của cây mà ta biết chắc không chứa phương án tối ưu. 5) Kỹ thuật Quy hoạch động Kỹ thuật quy hoạch động dựa vào một nguyên lý, gọi là nguyên lý tối ưu của Bellman : “ Nếu lời giải của bài toán là tối ưu thì lời giải của các bài toán con cũng tối ưu ”. Kỹ thuật này tổ chức tìm kiếm lời giải theo kiểu từ dưới lên. Xuất phát từ các bài toán con nhỏ và đơn giản nhất, tổ hợp các lời giải của chúng để có lời giải của bài toán con lớn hơn và cứ như thế cuối cùng được lời giải của bài toán ban đầu. 8
13. 1.5. Phân tích thuËt toán Trong khi giải một bài toán chúng ta có thể có một số thuật toán khác nhau, vấn đề là cần phải đánh giá các thuật toán đó để lựa chọn một thuật toán tốt (nhất). Thông thường thì ta sẽ căn cứ vào các tiêu chuẩn sau: - Thuật toán đơn giản - Thuật toán thực hiện nhanh Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu thuật toán đơn giản là quan trọng. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có được kết quả, thời gian thực hiện chương trình không được đề cao vì dù sao thì chương trình đó cũng chỉ sử dụng một vài lần mà thôi. Tuy nhiên khi một chương trình được sử dụng nhiều lần thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu thuật toán thực hiện nhanh sẽ được xem xét một cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của thuật toán. Hơn nữa khối lượng dữ liệu lớn mà dung lượng bộ nhớ lại có giới hạn thì không thể bỏ qua yêu cầu về tiết kiệm bộ nhớ được. Tuy nhiên cân đối giữa yêu cầu về thời gian và không gian không mấy khi có được một giải phấp trọn vẹn. Sau đây ta sẽ chỉ chú ý đến việc phân tích thời gian thực hiện thuật toán. 1.5.1. Thêi gian thùc hiÖn thuËt toán Một phương pháp để xác định hiệu quả thời gian thực hiện của một thuật toán là lập trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định đối với tập hợp được chọn lọc các dữ liệu vào. Thời gian thực hiện không chỉ phụ thuộc vào thuật toán mà còn phụ thuộc vào tập các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi của thuật toán. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt đối với sự phức tạp thời gian trong trường hợp xấu nhất. Nói chung thì thời gian thực hiện thuật toán không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện giải thuật có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một 9
14. dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm. Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n. Để đánh giá thời gian thực hiện thuật toán người ta tìm cách đánh giá độc lập với các yếu tố bên ngoài như máy tính hay các yếu tố liên quan đến máy tính. Cách đánh giá như vậy dẫn tới khái niệm về cấp độ lớn của thời gian thực hiện thuật toán hay độ phức tạp tính toán của thuật toán. 1.5.2. Độ phức tạp tính toán của thuật toán Nếu thời gian thực hiện một thuật toán là T(n) =cn2 (với c là hằng số, n là kích thước dữ liệu đầu vào) thì ta nói: Độ phức tạp tính toán của thuật toán này có cấp là n2 (hay cấp độ lớn của thời gian thực hiện thuật toán là n2) và ta ký hiệu: T(n) = O(n2) (ký hiệu chữ O lớn) Một cách tổng quát có thể định nghĩa: Một hàm f(n) được xác định là O(g(n)) và viết là f(n) =O(g(n)) và được gọi là cấp g(n) nếu tồn tại các hằng số c và n0 sao cho: f(n) ≤ cg(n) khi n ≥ n0 nghĩa là f(n) bị chặn trên bởi một hằng số nhân với g(n), với mọi giá trị của n tăng từ một điểm nào đó. Thông thường các hàm thể hiện độ phức tạp tính toán của thuật toán có dạng : 2 3 n n log2n, n, nlog2, n , n , 2 , n!, n Sau đây là bảng giá trị của một số hàm đó 2 3 n Log2n n nlog2n n n 2 0 1 0 1 1 2 1 2 2 4 8 4 2 4 8 16 64 16 3 8 24 64 512 256 4 16 64 256 40963 65536 5 32 160 1024 32768 2.147.483.648 Hình 1.1. Bảng giá trị của một số hàm số Các hàm như 2n , n!, nn được gọi là hàm loại mũ. Một thuật toán mà thời gian 10
15. thực hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm như n3 , n2, nlog2n, n, log2n được gọi là các hàm loại đa thức. Một thuật toán mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được tức là có thể cài đặt để thực hiện, còn các thuật toán có độ phức tạp hàm mũ thì phải tìm cách cải tiến thuật toán. Các quy tắc xác định độ phức tạp của thuật toán: Xác định độ phức tạp tính toán của một thuật toán bất kỳ có thể dẫn tới những bài toán phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta cũng có thể phân tích được bằng một số quy tắc đơn giản. * Quy tắc tổng: Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi thực hiện P1 và tiếp theo là P2 sẽ là: T1(n) + T2(n) = O(max (f(n),g(n)) Chứng minh: Vì T1(n) = O(f(n)); T2(n) = O(g(n)) nên theo định nghĩa tồn tại các hằng số dương c1 , n1 và c2 , n2 sao cho: T1(n) ≤ c1 f(n), với mọi n > n1 T2(n) ≤ c2 g(n) với mọi n > n2. Chọn c = c1 + c2; n0 = max {n1, n2}. Khi đó: T1(n) + T2(n) c1 f(n) + c2 g(n) c max(f(n), g(n)) , với mọi n > n0. Do vậy: O(f(n)) + O(g(n)) = O(max(f(n), g(n))). Ví dụ 1.1. Trong một chương trình có 3 bước thực hiện mà độ phức tạp tính toán từng 2 3 bước lần lượt là O(n ), O(n ) và O(nlog2n) thì độ phức tạp tính toán hai bước đầu là O(max (n2, n3) = O(n3). Độ phức tạp tính toán của chương trình sẽ là: O(max(n3, 3 nlog2n)) = O(n ). Nhận xét: Từ quy tắc này có thể nhận thấy rằng: nếu g(n) ≤ f(n) với mọi n ≥ n0 thì: O(f(n)+g(n)) = O(f(n)). Chẳng hạn: O(n4+n2) = O(n4) O(n + log2n) = O(n). 11
16. * Quy tắc nhân: Giả sử T1(n) và T2(n) là độ phức tạp tính toán của hai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)) thì độ phức tạp tính toán khi P1 và P2 lồng nhau sẽ là: T1(n).T2(n) = O(f(n).g(n)) Chứng minh: Ta có: T1(n) = O(f(n)), T2(n) = O(g(n) theo định nghĩa tồn tại các hằng số dương c1 , n1và c2 , n2 sao cho: T1(n) ≤ c1 f(n), với mọi n > n1 T2(n) ≤ c2 g(n) với mọi n > n2. Chọn c = c1 * c2; n0 = max {n1, n2}. Khi đó: T1(n).T2(n) c1 f(n) c2 g(n) = c (f(n) g(n)). Do vậy: T1(n).T2(n) = O(f(n).g(n)). Ví dụ 1.2. Câu lệnh gán : x = x+1 có thời gian thực hiện bằng c (hằng số) nên được đánh giá là O(1). Câu lệnh: for ( i=1; i<=n; i++) x =x+1; Có độ phức tạp tính toán O(n.1) = O(n) Câu lệnh : for ( i= 1; i<=n; i++) for ( j= 1; j<=n; j++) x =x+1; có độ phức tạp tính toán được đánh giá là: O(n.n)=O(n2) Nhận xét: Từ quy tắc nhân ta sẽ có: O(cf(n)) = O(f(n)) Chẳng hạn O(n2/2) = O(n2) Chú ý : Dựa vào những nhận xét đã nêu ở trên về quy tắc khi đánh giá độ phức tạp tính toán của thuật toán ta chỉ cần chú ý tới các bước tương tự với một phép toán mà ta gọi là phép toán tích cực. Đó là một phép toán thuộc thuật toán mà thời gian thực hiện nó không ít hơn thời gian thực hiện các phép toán khác (tất nhiên phép toán tích cực không phải là duy nhất) hay nói một cách khác: số lần thực hiện nó không kém gì các phép toán khác. 12
17. Ví dụ 1.3. Giải thuật tính giá trị của ex theo công thức gần đúng: ex = 1 + x/1! +x2/2! + + xn/n! với x và n cho trước EXP1(); { scanf(x) ; S =1; for (i=1;i<=n;i++) { p =1; for(j=1;j<=i;j++) p=p*x/j; S = S +p; } } Ta có thể coi phép toán tích cực ở đây là phép: p = p*x/j Ta thấy nó được thực hiện: 1 +2+ + n = n(n+1)/2 lần Vậy độ phức tạp tính toán của thuật toán này được đánh giá là T(n) = O(n2) Thuật toán có thể được viết theo một cách khác: EXP2() { scanf(x); S =1; P =1; for (i=1;i<=n;i++) { p =p*x/i; S =S + p; } } 13
18. Bây giờ độ phức tạp tính toán lại là: T(n) = O(n). Vì phép gán p=p*x/i chỉ thực hiện n lần. Ví dụ 1.4. Thuật toán sắp xếp kiểu nổi bọt void Bubble(a) { for(i=1;i =i+1; j ) if (a[j-1]>a[j]) { tg:= a[j-1]; a[j-1] := a[j]; a[j]:= tg; } } Trong thuật toán ta coi phép so sánh (a[j-1]>a[j]) là phép toán tích cực. Phép toán này nằm trong vòng lặp for(j=n; j>=i+1; j ) nên nó được thực hiện (n-i) lần. Vòng lặp for(j=n; j>=i+1; j ) nằm trong vòng lặp for(i=1;i a[j]) sẽ là: n 1 n( n 1) ( n i ) i 1 2 Nên độ phức tạp tính toán của thuật toán là O(n2). Chú ý: Ta biết rằng thời gian thực hiện thuật toán không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng dữ liệu nhập nữa. Chẳng hạn, khi xếp tăng dần một dãy các số nguyên mà dãy các so nguyên đĩ đã có sẵn thứ tự tăng dần, hoặc ngược lại, hoặc ngẫu nhiên. Lúc đó khi phân tích thời gian thực hiện thuật toán ta sẽ phải xét tới: đối với mọi dữ liệu vào có kích thước n thì T(n) trong trường hợp tốt nhất, xấu nhất là như thế nào? T(n) trung bình? Việc xác định T(n) trung bình thường khó và phức tạp đòi hỏi những công cụ toán học đặc biệt, hơn nữa việc tính trung bình có thể có nhiều cách quan niệm khác nhau. Trong trường hợp T(n) khó xác định người ta thường đánh giá thuật toán qua giá trị xấu nhất của T(n) 14
19. VÝ dô 1.5. timkiem(v) /*Cho vectơ V có n phần tử, thuật toán này thực hiện tìm trong V một phần tử có giá trị bằng X cho trước. Nếu tìm thấy trả về chỉ số của phần tử đó, nếu không tìm thấy trả về giá trị 0*/ i =1; while ((V[i] !=X)&& (i<= n)) i= i+1; if (i<=n) return(i); else return(0); Coi phép toán tích cực ở đây là phép so sánh V[i] với X. Có thể thấy số lần phép toán thực hiện phụ thuộc vào chỉ số i mà V[i] = X. Trường hợp thuận lợi nhất xảy ra khi X bằng V[1]: một lần thực hiện. Trường hợp xấu nhất khi X bằng V[n] hoặc không tìm thấy: n lần thực hiện Vậy: Ttốt = O(1) và Txấu = O(n) Thì ta xác định độ phức tạp tính toán của thuật toán là O(n) * Qui tắc tổng quát để phân tích một chương trình: Giả sử rằng, các lệnh gán không chứa các lời gọi hàm. Khi đó để đánh giá thời gian thực hiện một chương trình, ta có thể áp dụng một số quy tắc sau 1. Thời gian thực hiện các lệnh đơn: gán, đọc, viết là O(1) 2. Lệnh hợp thành (khối lệnh) : thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng. 3. Lệnh if : Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là O(max (f(n), g(n))) 4. Lệnh witch: Lệnh này được đánh giá như lệnh if 5. Lệnh while : Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n)). Giả sử g(n) là số tối đa các lần thực hiện lệnh S. Khi đó thời gian thực hiện lệnh while là O(f(n)g(n)). 6. Lệnh do while :Giả sử thời gian thực hiện khối lệnh trong thân do while là O(f(n)). Giả sử g(n) là số lần tối đa các lần thực hiện khối lệnh trong thân do while . Khi đó thời gian thực hiện lệnh do while là O(f(n)g(n)). 7. Lệnh for : Lệnh này được đánh giá tương tự như lệnh while. 1.5.3. Ðộ phức tạp của chƣơng trình có gọi chƣơng trình con không đệ qui 15
20. Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các chương trình con mà nó gọi đã được đánh giá. Cuối cùng ta tính thời gian cho chương trình chính. Giả sử ta có một hệ thống các chương trình gọi nhau theo sơ đồ sau: Hình 1.2. Chương trình gọi chương trình con không đẹ quy Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12. Ðể xác định độ phức tạp tính toán của A, ta thực hiện theo các bước sau: 1. Xác định độ phức tạp tính toán của C, B2, B11 và B12. Vì các chương trình con này không gọi chương trình con nào cả. 2. Xác định độ phức tạp tính toán của B1. Vì B1 gọi B11 và B12 mà độ phức tạp tính toán của B11 và B12 đã được tính ở bước 1. 3. Xác định độ phức tạp tính toán của B. Vì B gọi B1 và B2 mà độ phức tạp tính toán của B1 đã được tính ở bước 2 và độ phức tạp tính toán của B2 đã được tính ở bước 1. 4. Xác định độ phức tạp tính toán của A. Vì A gọi B và C mà độ phức tạp tính toán của B đã được tính ở bước 3 và độ phức tạp tính toán của C đã được tính ở bước 1. Ví dụ 1.6. Thuật toán sắp xếp nổi bọt. Trước hết viết thủ tục Swap để thực hiện việc hoàn đổi hai phần tử cho nhau, sau đó trong thủ tục Bubble, khi cần sẽ gọi đến thủ tục Swap này. void Swap (x, y) 16
21. { temp = x; x = y; y = temp; } void Bubble (a) { for(i=1;i =i+1; j ) if (a[j-1]>a[j]) Swap(a[j-1], a[j]); } Trong cách viết trên, hàm Bubble gọi hàm Swap, do đó để tính độ phức tạp tính toán của Bubble, trước hết ta cần tính độ phức tạp tính toán của Swap. Dễ thấy độ phức tạp tính toán của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán. Do vậy ta có thể coi phép toán tích cực là phép so sánh (a[j-1]>a[j]) và khi đó dễ thấy độ phức tạp tính toán của thuật toán là: 1.5.4. Phân tích các thuật toán đệ quy Nhiều thuật toán dựa trên sự phân rã đệ qui một bài toán lớn thành các bài toán nhỏ, rồi dùng lời giải các bài toán nhỏ để giải bài toán ban đầu. Thời gian chạy của thuật toán như thế được xác định bởi kích thước và số lượng các bài toán con và giá phải trả của sự phân rã. Nên các thuật toán đệ qui có thời gian chạy phụ thuộc vào thời gian chạy cho các dữ liệu nhập có kích thước nhỏ hơn, điều này được diễn dịch thành một công thức toán học gọi là công thức truy hồi hay phương trình truy hồi, hệ thức truy hồi. Do đó, để tính độ phức tạp của thuật toán, ta thường phải giải các phương trình truy hồi. Với các thuật toán có các lời gọi đệ quy, ta không thể áp dụng cách tính như vừa trình bày trong mục 1.3.3 bởi vì một chương trình đệ quy sẽ gọi chính bản thân nó. Có thể thấy hình ảnh chương trình đệ quy A như sau: 17
22. Hình 1.3. Chương trình đệ quy A Với các chương trình đệ quy, trước hết ta cần thành lập các phương trình truy hồi, sau đó giải phương trình truy hồi, nghiệm của phương trình truy hồi sẽ là thời gian thực hiện của chương trình đệ quy. 1) Thành lập phƣơng trình truy hồi Phương trình truy hồi 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 chương trình với kích thước dữ liệu nhập là n, T(k) thời gian thực hiện chương trình với kích thước dữ liệu nhập là k, với k < n. Ðể thành lập được phương trình truy hồi, ta phải căn cứ vào chương trình đệ quy. Thông thường một chương trình đệ quy để giải bài toán kích thước n, phải có ít nhất một trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k<n). Để thành lập phương trình truy hồi, ta gọi T(n) là thời gian để giải bài toán kích thước n, ta có T(k) là thời gian để giải bài toán kích thước k. Khi dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n). Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ quy với kích thước k ta sẽ có bấy nhiêu T(k). Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n). Dạng tổng quát của một phương trình truy hồi sẽ là: Trong đó C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng. F(T(k)) là một đa thức của các T(k), d(n) là thời gian để phân chia bài toán và tổng hợp các kết quả. Chú ý: n Trong khi đánh giá độ phức tạp tính toán của thuật toán thì với T( ) ta sẽ 2 hiểu là hoặc (Với x là một số thực thì: 18
23. x là số nguyên lớn nhất nhỏ hơn hoặc bằng x x là số nguyên nhỏ nhất lớn hơn hoặc bằng x) Ví dụ 1.7. Xét hàm tính giai thừa viết bằng thuật toán đệ quy như sau: int Giai_thua(n) { if (n 1 chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán cho gt. 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ó: C nếu n 1 T(n) = 1 T(n-1)+C2 nếu n >1 Ðây là phương trình truy hồi để tính thời gian thực hiện của chương trình đệ quy Giai_thua. 2) Giải phƣơng trình truy hồi Một số phương pháp giải phương trình truy hồi: * Phương pháp thay thế 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 các T(1) hoặc T(0). Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra T(n). VÝ dô 1.8. Hàm tính n! trong ví dụ 1.7. int Giai_thua(n) { 19
24. if (n 1 - Với n 1, chỉ cần thực hiện lệnh gán gt = 1, do đó T(1) = O(1). - Với n > 1. cần thực hiện lệnh gán gt= n*Giai_thua(n - 1). Do đó thời gian T(n) là O(1) (để thực hiện phép nhân và phép gán) cộng với T(n-1) (để thực hiện lời gọi đệ qui Giai_thua(n – 1)). Tóm lại, ta có quan hệ sau: T(1) = O(1) T(n) = O(1) + T(n-1) Thay các O(1) bởi các hằng nào đó, ta nhận được quan hệ sau T(1) = C1 T(n) = C2 + T(n - 1) Để giải phương trình truy hồi, tìm T(n), chúng ta áp dụng phương pháp thế lặp. Ta có phương trình truy hồi T(m) = C2 + T(m-1), với m > 1 Thay m lần lượt bởi 2, 3, , n - 1, n, ta nhận được các quan hệ sau: T(2) = C2 + T(1) T(3) = C2 + T(2) T(n -1) = C2 + T(n -2) T(n) = C2 + T(n - 1) Bằng các phép thế liên tiếp, ta nhận được T(n) = (n - 1) C2 + T(1) hay T(n) = (n - 1) C2 + C1, trong đó C1 và C2 là các hằng nào đó. 20
25. Do đó, T(n) = O(n). Ví dụ 1.9. Giải phương trình truy hồi sau: T(n) = c1 nếu n=1 n 2T( )+c2n nếu n>1 2 Ta có với n>1: T(n) = 2T( )+c2n n 2 n = 2(2T( )+c2 ) + c2n = 4 T( ) + 2c2n = 2 T( ) + 2c2n 4 2 2 n 3 n = 4( 2T( )+c2 ) + 2c2n = 8T( ) + 3c2n = 2 T( ) + 3c2n 8 2 3 i n = 2 T( ) + ic2n 2 i n Quá trình sẽ dừng khi: =1 2 i n =2i i = log2n Khi đó: T(n) = nT(1) + c2nlog2n = nc1 + c2nlog2n Và T(n) = O(nlog2n) * Phương pháp đoán nghiệm Ta đoán một nghiệm f(n) và dùng chứng minh quy nạp để chứng tỏ rằng T(n) ≤ f(n) với mọi n. Thông thường f(n) là một trong các hàm quen thuộc như log2n, n, 2 3 n n nlog2n, n , n , 2 , n!, n . Ðôi khi chúng ta chỉ đoán dạng của f(n) trong đó có một vài tham số chưa xác 2 định (chẳng hạn f(n) = an với a chưa xác định) và trong quá trình chứng minh quy nạp ta sẽ suy diễn ra giá trị thích hợp của các tham số Ví dụ 1.10. Giải phương trình truy hồi sau: 21
26. c1 nếu n=1 T(n)= n 2T( )+c2n nếu n>1 2 Giả sử chúng ta đoán f(n) = anlog2n. Với n = 1 ta thấy rằng việc đoán như vậy không được bởi vì anlog2n có giá trị 0 không phụ thuộc vào giá trị của a. Vì thế ta thử tiếp theo f(n) = anlog2n + b. Với n = 1 ta có, T(1) = C1 và f(1) = b, muốn T(1) ≤ f(1) thì b ≥ C1 (*) Giả sử rằng T(k) ≤ f(k), tức là T(k) ≤ aklog2k + b với mọi k 0 và 1-n<0) Nếu ta lấy a và b sao cho cả (*) và ( ) đều thoả mãn Tức là: b c1 a c2 + b thì T(n) ≤ anlog2n + b với mọi n Như vậy với b c1 và a c1 + c2 thì ta sẽ có T(n) ≤ (c1 + c2)nlog2n +c1 với mọi n. Hay nói cách khác T(n) là O(nlog2n). * Phương pháp dùng phương trình đặc trưng với phương trình truy hồi tuyến tính thuần nhất hệ số hằng Phương trình truy hồi (công thức truy hồi) tuyến tính thuần nhất bậc k với hệ số hằng số có dạng: 22
27. an = c1an-1 + c2an-2 + + ckan-k trong đó c1, c2, , ck là các số thực, ck  0 Nếu cho trước k điều kiện ban đầu a0 = c0, a1 = c1, , ak-1 = ck-1 ,thì theo qui nạp toán học, dãy số thoả mãn phương trình truy hồi nêu trong định nghĩa sẽ được xác định duy nhất. Phương pháp cơ bản để giải phương trình truy hồi tuyến tính thuần nhất là n n tìm nghiệm dưới dạng an = r , trong đó r là hằng số. Ta có an = r là nghiệm của phương trình truy hồi an = c1an-1 + c2an-2 + + ckan-k khi và chỉ khi: n n-1 n-2 n-k r = c1r + c2r + + ckr n n-1 n-2 n-k Hay r - c1r - c2r - - ckr = 0 n Vậy, dãy {an} với an = r là nghiệm khi và chỉ khi r là nghiệm của phương trình đại số trên. Phương trình này được gọi là phương trình đặc trưng của công thức truy hồi và nghiệm của nó được gọi là nghiệm đặc trưng của phương trình truy hồi. Các nghiệm đặc trưng sẽ dùng cho công thức tường minh của tất cả các nghiệm của phương trình truy hồi. Đối với phương trình truy hồi tuyến tính thuần nhất bậc 2 khi phương trình đặc trưng có hai nghiệm phân biệt r1, r2. Khi đó dãy số {an} là nghiệm của công thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi n n an =  1r1 +  2r2 với n= 0, 1, 2, ,trong đó 1, 2 là các hằng số. Ngược lại, giả sử {an} là một nghiệm bất kỳ của phương trình truy hồi, ta sẽ n n chọn 1 và 2 sao cho dãy {an} với an = a1r1 + a2r2 thoả mãn các điều kiện đầu a0 = c0, a1 = c1. Thật vậy, đặt: a0 = c0 = 1 + 2 a1 = c1 = a1r1 + a2r2 Từ phương trình đầu ta được 2 = c0 - 1. Thay vào phương trình sau ta được: c1 = a1r1 + (c0 - 1)r2 = a1(r1 - r2) + c0r2 C1 C0r2 Suy ra 1 r1 r2 C C r 1 0 2 C0 r1 C1 và 2 C0 1 C0 = r1 r2 r1 r2 23
28. n n Vậy khi chọn các giá trị a1 và a2 này thì dãy {an} với an = a1r1 + a2r2 thoả mãn các điều kiện đầu. Vì phương trình truy hồi và các điều kiện đầu xác định duy n n nhất, nên an = a1r1 + a2r2 . Ví dụ 1.11. Giả sử rằng các con thỏ không bao giờ chết. Biết rằng một cặp thỏ sau 2 tháng tính từ khi ra đời sẽ sinh ra một cặp thỏ mới và sau đó cứ mỗi tháng lại sinh ra một cặp thỏ mới. Hỏi nếu tháng đầu có một cặp thỏ thì đến tháng thứ n sẽ có bao nhiêu cặp thỏ? Giải: Gọi số cặp thỏ có ở tháng thứ n là Fn thì theo giả thiết F1 = F2 = 1. Với n>2 ta nhận thấy rằng: Số cặp thỏ có ở tháng thứ n sẽ là số cặp thỏ có ở tháng thứ n-1 (là Fn-1) cộng với số cặp thỏ mới được sinh ra ở tháng thứ n - chính là số cặp thỏ có ở tháng thứ n-2 (là Fn-2). Tức là: Fn = Fn-1 + Fn-2 với n>2. Vì vậy có thể tính Fn theo hệ thức truy hồi sau: 1 nếu n 2 F = n F + F nếu n >2 n-1 n-2 Dãy số thể hiện Fn với các giá trị của n được gọi là dãy số Fibonacci. Từ hệ thức truy hồi trên ta dễ dàng có được giải thuật sau để tính số cặp thỏ có ở tháng thứ n. Fibo(n) { if(n 2 24
29. Giải phương trình đặc trưng r2- r- 1 = 0 ta thu được hai nghiệm: 1 5 r 1 2 1 5 r 2 2 n n Khi đó ta có T(n) =  1r1 +  2r2 (*) trong đó 1, 2 là các hằng số cần xác định từ các giá trị ban đầu T(1) và T(2). Thay T(1) và T(1) vào (*) và giải ra ta được 1 1 5 1 2 5 Khi đó ta có: n n 1 1 5 1 5 T( n ) 5 2 2 Hay: 1 5 T(n) = O( )n 2 Như vậy độ phức tạp tính toán của giải thuật là cấp hàm mũ. Trong các ví dụ sau tài liệu chỉ đưa ra các cách giải phương trình truy hồi (hệ thức truy hồi, công thức truy hồi) từ đó người đọc có thể dễ dàng vận dụng để xác định độ phức tạp tính toán của giải thuật tương ứng. Ví dụ 1.12. Tìm nghiệm của công thức truy hồi an = an-1 + 2an-2, với a0 = 2, a1 = 7 Giải: Phương trình đặc trưng của công thức truy hồi này có dạng r2 - r -2 = 0. Nghiệm của nó là r=2 và r=-1. Theo định lý 1 dãy {an} là nghiệm của công thức n n truy hồi khi và chỉ khi an =  12 +  2(-1) với các hằng số a1 và a2 nào đó. Từ các điều kiện đầu ta suy ra: a0 = 2 = 1 + 2 a1 = 7 = a12 + a2(-1) Giải ra ta được 1 = 3 và 2 = -1. Vậy nghiệm của công thức truy hồi với điều kiện đầu là dãy {an} với an = 3.2n - (-1)n 25
30. Trong trường hợp phương trình đặc trưng của công thức truy hồi tuyến tính thuần nhất bậc 2 có nghiệm đặc trưng là nghiệm bội (chỉ có một nghiệm r0) khi đó dãy số { an} là nghiệm của công thức truy hồi an = c1an-1 + c2an-2 khi và chỉ khi n n an =  1r0 +  2n r0 với n= 0, 1, 2, trong đó 1, 2 là các hằng số. Ví dụ 1.13. Tìm nghiệm của hệ thức truy hồi an = 6an-1- 9an-2 với các điều kiện ban đầu a0= 1 và a1 =6. Giải: Phương trình đặc trưng r2- 6r+ 9 = 0 có nghiệm kép r = 3. Do đó nghiệm n n của hệ thức truy hồi có dạng: an =  1 3 +  2n3 . Từ điều kiện đầu a0= 1 và a1 =6 suy ra  1 = 1 và 2 = 1. Do vậy nghiệm của hệ thức truy hồi và các điều kiện n n ban đầu đã cho là: an = 3 + n3 Tổng quát hóa kết quả trên cho trường hợp hệ thức truy hồi tuyến tính thuần -1 -2 nhất hệ số hằng bậc k > 2. Giả sử phương trình đặc trưng rk- c1rk - c2rk - - ck = 0 có k nghiệm phân biệt r1, r2, , rk. Khi đó dãy số {an} là nghiệm của hệ thức truy hồi an = c1an-1 + c2an-2+ + ckan-k khi và chỉ khi n n n an =  1r1 +  2r2 + +  krk với n= 0, 1, 2, trong đó 1, 2 , , k là các hằng số. Ví dụ 1.14. Tìm nghiệm của hệ thức an = 6an-1- 11an-2 + 6an-3 với điều kiện đầu a0 = 2, a1 = 5, a2 = 15. Giải: Phương trình đặc trưng r3- 6r2 + 11r- 6 = 0 có 3 ngiệm r1 = 1, r2 = 2, r3 = 3. Vì vậy, nghiệm có dạng n n n an =  11 +  22 + 33 . Sử dụng các điều kiện đầu ta có 1=1, 2 =-1, 3 = 2. Vậy nghiệm của hệ thức đã cho là an = 1- 2n+2.3n. * Phương trình truy hồi có dạng: 1 nếu n =1 (1 T(n) = (1) aT(n/b)+d(n) nếu n >1 Để xác định độ phức tạp tính toán của thuật toán theo phương trình truy hồi trên ta thực hiên như sau: 26
31. Chia bài toán kích thước n thành a bài toán con mỗi bài toán con có kích thước n/b. Giải các bài toán con này và tổng hợp các kết quả ta được lời giải của bài toán ban đầu. Với các bài toán con ta cũng áp dụng kỹ thuật này thì đến một lúc bài toán con sẽ có kích thước là 1. Kỹ thuật này sẽ dẫn ta đến một giải thuật đệ quy. Gọi thời gian để giải quyết bài toán đã cho kích thước n là T(n), thời gian để giải quyết bài toán con kích thước n/b là T(n/b), thời gian để giải quyết bài toán con kích thước 1 là 1, thời gian để phân tích bài toán thành các bài toán con kích thước n/b và tổng hợp kết quả là d(n) thì ta sẽ có phương trình (1). Với phương trình (1) khi n>1 ta có: n T(n) = aT( ) + d(n) b n n = a(aT( ) + d( )) + d(n) b 2 b = a2T( ) + d(n) + ad( ) n n = a2(aT( ) + d( ))+ d(n) + ad( ) b 3 b 2 = a3T( ) + d(n) + ad( )+ a2d( ) n n =aiT( ) + d(n) + ad( )+ a2d( ) + +ai-1d( ) b i bi 1 i 1 n i a j d( ) = a T( ) +  j j 0 b Giả sử n = bk khi đó ta sẽ có: k 1 n k n a j d( ) T(n) = a T( k ) +  j b j 0 b k 1 n k a j d( ) = a T(1) +  j j 0 b k 1 = ak + = ak + a j d(bk j ) (2) j 0 Trong (1) hàm d(n) được gọi là hàm tiến triển. 27
32. Trong (2) hàm ak được gọi là nghiệm thuần nhất. Nghiệm thuần nhất biểu diễn thời gian để giải các bài toán con.Ta có: k b = n k = logbn a Do đó ak = alogb n = alogb loga n = nlogb a k 1 Trong (2) hàm a j d(bk j ) được gọi là nghiệm riêng. Nghiệm riêng biểu j 0 diễn thời gian để tạo các bài toán con và tổng hợp kết quả. Dễ thấy rằng nghiệm riêng phụ thuộc vào hàm tiến triển, số lượng và kích thước các bài toán con. Theo qui tắc tổng trong (2) ta nhận thấy trong hai nghiệm: nghiệm riêng và nghiệm thuần nhất nghiệm nào lớn hơn thì đó là nghiệm của phương trình truy hồi. Việc xác định nghiệm riêng nói chung là phức tạp, ở đây ta chỉ quan tâm đến một lớp các phương trình dạng (1) mà ở đó hàm tiến triển có những dạng mà từ đó ta có thể dễ dàng tìm được nghiệm riêng. Hàm nhân: Một hàm f(n) được gọi là hàm nhân nếu với mọi n, m nguyên dương ta đều có f(n.m)=f(n).f(m) Ví dụ 1.15. Hàm f(n) = nk là một hàm nhân vì: f(n.m) = (nm)k = nk.mk = f(n).f(m) + Tìm nghiệm của (1) trong trường hợp d(n) là hàm nhân. Nếu d(n) là hàm nhân thì khi đó ta có: a ( )k 1 k 1 k 1 j k j a d( b ) = a d (b )= d k ( b ) ( ) j d k ( b )   d( b ) a j 0 j 0 1 d( b ) Như vậy nghiệm riêng của (2) sẽ là: a k d k ( b ) (3) a 1 d( b ) Khi đó xảy ra các trường hợp sau: 1- Nếu a > d(b) thì trong (3) ta có ak > dk(b), theo quy tắc tổng độ phức tạp của nghiệm riêng là O(ak) bằng độ phức tập của nghiệm thuần nhất và đều bằng O( ), tức la T(n) =O( ) 28
33. Ví dụ 1.16. Giải phương trình truy hồi sau: 1 nếu n =1 T(n) = 4T(n/2)+ n nếu n >1 Giải: Phương trình có dạng (1) với a=4, b=2 và d(n) = n. Vì d(n) = n nên dễ thấy rằng d(n) là hàm nhân và d(b) = d(2) =2 1 Giải: Phương trình có dạng (1) với a=4, b=2 và d(n) = n3. Vì d(n) = n3 nên d(n) là hàm nhân và d(b) = d(2) =23 > a. log 23 Vậy T(n) = O( n 2 ) = O(n3) 3- Nếu a = d(b) thì (3) không xác định, trong trường hợp này ta phải tính trực tiếp nghiệm riêng. Ta có: k 1 a k 1 d k (b )( ) j a k 1 a k k j 0 d(b ) j 0 a Do bk = n k = logbn và ak = alogb n = alogb loga n = nlogb a Nên nghiệm riêng sẽ là: logbn Nghiệm riêng lớn hơn nghiệm thuần nhất ( logbn > ) Vậy ta có: T(n) = O( logbn) Ví dụ 1.18. 29
34. Giải phương trình truy hồi sau: 1 nếu n =1 T(n) = Giải: 2T(n/2)+ n nếu n >1 Phương trình có dạng (1) với a=2, b=2 và d(n) = n. Vì d(n) = n nên d(n) là hàm nhân và d(b) = d(2) =2 = a. log2 2 n n Vậy T(n) = O( n log2 ) = O(nlog2 ) + Tìm nghiệm của (1) trong trường hợp d(n) không phải là một hàm nhân. Trong trường hợp này ta phải tính trực tiếp nghiệm riêng rồi lấy nghiệm lớn hơn trong hai nghiệm: nghiệm riêng và nghiệm thuần nhất làm nghiệm của (1). Ví dụ 1.19. Giải phương trình truy hồi sau: 1 nếu n =1 T(n) = 2T(n/2)+ nlog2n nếu n >1 Giải: Phương trình có dạng (1) với a=2, b=2 và d(n) = nlog2n. Dễ thấy rằng d(n) không phải là hàm nhân nên ta trực tiếp tìm nghiệm riêng như sau: k 1 k 1 k 1 j k j j k j k j k k k( k 1) a d(b ) 2 2 log 2 2 2 ( k j ) 2 j 0 j 0 j 0 2 k k( k 1) kk2 2 Ta có O(2 ) = O(2 ) = O(nlog2 n) ( vì k = logbn = log2n) 2 Nghiệm thuần nhất 2k = n Nghiệm riêng lớn hơn nghiệm thuần nhất nên ta có: 2 T(n) = O(nlog2 n) 30
35. BÀI TẬP CHƢƠNG 1 1. Xác định độ phức tạp tính toán của giải thuật sau: sapxep1(a,n) { for(i=1;i n) return(0) else return(i); } 3. Xác định độ phức tạp tính toán của đoạn chương trình sau: for(i=1;i<=n;i++) for(j=1;j<=n;j++) { c[i,j] := 0; 31
36. for(k=1;k =1)&&(x<k[j])) { a[j+1]=a[j]; j=j-1; } a[j+1]=x; } } 5. Xác định độ phức tạp tính toán của giải thuật sắp xếp kiểu vun đống Hướng dẫn: Dãy khoá K gồm n khoá. Để sắp xếp dãy khoá theo thứ tự tăng dần theo kiểu vun đống ta xây dựng các hàm ADJUST và HEAP_SORT. Hàm ADJUST(i,n) thực hiện việc chỉnh lý một cây nhị phân hoàn chỉnh với gốc i để cây trở thành đống. Cây con trái và cây con phải của i, tức là cây với gốc là 2i và 2i+1 đã thoả mãn điều kiện của đống. Không có nút nào ứng với chỉ số lớn hơn n. ADJUST được gọi trong HEAP_SORT. ADJUST(i,n) { // Khởi đầu key=k[i]; j=2*i; 32
37. // Chọn con ứng với khoá lớn nhất trong hai con của i while(j k[j]) { k[[j/2]]=key; return; } k[[j/2]]=k[j]; j=2*j; } k[[j/2]]=key; return; } Ta coi phép toán tích cực là phép so sánh (j =1;i ) ADJUST(i,n); // Sắp xếp for(i=n-1;i>=1;i ) { x=k[1]; k[1]=k[i+1]; k[i+1]=x; 33
38. } } Trong thuật toán này vòng lặp for(i=[n/2];i>=1;i ) thực hiện lặp n/2 lần, mỗi lần lặp gọi ADJUST(i,n). Do vậy độ phức tạp tính toán của HEAP_SORT là O(nlog2n). 6. Giải các phương trình truy hồi sau: 1 nếu n =1 a) T(n) = 3T(n/2)+ n nếu n >1 b) 1 nếu n =1 T(n) = 3T(n/2)+ n2 nếu n >1 1 nếu n =1 T(n) = c) 8T(n/2)+ n3 nếu n >1 7. Giải các phương trình truy hồi sau: a) T(1) = 2 và T(n) = 2T(n-1) + 1 với n > 1 b) T(1) = 3, T(2)=6 và T(n) = T(n-1) + 6T(n-2) với n > 2 8. Cho tổng 1 1 1 S 1 với n nguyên dương 2 3 n Viết một giải thuật không đệ quy và một giải thuật đệ quy tính tổng trên và đánh giá độ phức tạp tính toán của các giải thuật đó. Hướng dẫn: Thuật toán đệ quy: tong(n) { if(n==1) return(1); else return(tong(n-1)+1/n); } Đánh giá độ phức tạp: - Xây dựng phương trình truy hồi c1 nếu n=1 T(n)= T(n-1) + c2 nếu n>1 - Giải phương trình truy hồi T(n) = T(n-1) + c2 = T(n-2) + 2c2 34
39. = T(1) + (n-1)c2 - Độ phức tạp tính toán của giải thuật: T(n) =O(n). 9. Cho dãy a gồm n số nguyên đã được sắp xếp theo thứ tự tăng dần, các phần tử của dãy được đánh chỉ số từ 1 đến n. Xác định độ phức tạp tính toán của các giải thuật sau: a. Giải thuật tìm kiếm nhị phân TKNP(a,n,x) { l=1; r=n; while(l a[m]) l=m+1; else return(m) return(0); } b. Giải thuật tìm kiếm nhị phân đệ quy TKNP(l,r,a,x) { if(l>r) loc=0; else { m=[(l+r)/2]; if(x a[m]) loc=TKNP(m+1,r,a,x) else loc=m; return(loc); 35
40. } Hướng dẫn ý b. - Xây dựng phương trình truy hồi: c1 nếu n=1 T(n)= n T( )+c2 nếu n>1 2 Với n>1 ta có: T(n) = T( )+ c2 n = T( )+ 2c2 4 n = T( )+ 3c2 8 n = T( )+ ic2 2 i n i Dừng khi =1 n=2 i=log2n 2 i Do đó T(n) = T(1) + c2log2n = c1 + c2log2n = O(log2n) 36
41. Chƣơng 2 KỸ THUẬT CHIA ĐỂ TRỊ 2.1. Néi dung kü thuËt Có thể nói rằng kĩ thuật quan trọng nhất, được áp dụng rộng rãi nhất để thiết kế các thuật toán có hiệu quả là kĩ thuật "chia để trị". Nội dung của nó là: Ðể giải một bài toán kích thước n, ta chia bài toán đã cho thành một số bài toán con có kích thưóc nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải của bài toán ban đầu. Ðối với các bài toán con, chúng ta lại sử dụng kĩ thuật chia để trị để có được các bài toán kích thước nhỏ hơn nữa. Quá trình trên sẽ dẫn đến những bài toán mà lời giải chúng là hiển nhiên hoặc dễ dàng thực hiện, ta gọi các bài toán này là bài toán cơ sở. Tóm lại kĩ thuật chia để trị bao gồm hai quá trình: Phân tích bài toán đã cho thành các bài toán cơ sở và tổng hợp kết quả từ bài toán cơ sở để có lời giải của bài toán ban đầu. Tuy nhiên đối với một số bài toán, thì quá trình phân tích đã chứa đựng việc tổng hợp kết quả do đó nếu chúng 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 khó khăn. Kĩ thuật này sẽ cho chúng ta một thuật toán đệ quy mà việc xác định độ phức tạp của nó sẽ phải giải một phương trình đệ quy như trong chương 1 đã trình bày. Sơ đồ chia-để-trị gồm ba bước ở mỗi mức của đệ quy: - Chia bài toán thành một số bài toán con. - Trị các bài toán con bằng cách giải chúng đệ quy. Nếu kích thước các bài toán con là đủ nhỏ (bài toán cơ sở), giải trực tiếp các bài toán này. - Kết hợp các lời giải của các bài toán con thành lời giải cho bài toán ban đầu. Phần tiếp sau trình bày một số ví dụ áp dụng kỹ thuật chia để trị để thiết kế thuật toán cùng với sự đánh giá độ phức tạp tính toán của thuật toán. 2.2. C¸c vÝ dô ¸p dông 2.2.1. T×m min vµ max 1) Bài toán Cho mảng a gồm n phần tử: a[1 n]. Tìm phần tử nhỏ nhất (min) và phần tử lớn nhất (max) trong dãy. 2) Thiết kế thuật toán 37
42. Tại mỗi bước chia đôi đoạn cần tìm rồi tìm min, max của từng đoạn, sau đó tổng hợp kết quả. Nếu đoạn chỉ có một phần tử thì min = max và bằng phần tử đó. Hàm MinMax(a,l,r,Min,Max) cho Min và Max trong đoạn a[l r]. Thuật toán Input : a[1 n] Output : Min = Min (a[1], ,a[n]), Max = Max (a[1], ,a[n]). MinMax(a,l, r, Min, Max) if (l == r) { Min = a[l]; Max = a[l]; } Else { MinMax(a,l, (l+r)/ 2, Min1, Max1); MinMax(a,(l+r)/2 + 1, r , Min2, Max2); If (Min1 Max2) Max = Max1 Else Max = Max2; } 3) Đánh giá độ phức tạp tính toán của thuật toán - Với n = 1, chỉ cần thực hiện 2 lệnh, do đó T(1) = O(1). - Với n > 1 cần thực hiện lệnh các lệnh: MinMax(a,l, (l+r) / 2, Min1, Max1); MinMax(a,(l+r) /2 + 1, r , Min2, Max2); If (Min1 < Min2) 38
43. Min = Min1; Else Min = Min2; If (Max1 > Max2) Max = Max1 Else Max = Max2; n Ở đây có 2 lời gọi đệ quy với thời gian là T( ). Khi kết thúc lời gọi đệ quy 2 thì thực hiện phép so sánh và phép gán với thời gian là O(1). Tóm lại, ta có quan hệ sau: T(1) = O(1) T(n) = O(1) + 2T( ) Thay các O(1) bởi các hằng nào đó, ta nhận được phương trình đệ quy: C1 nếu n=1 T(n)= n 2T( )+C nếu >1 2 2 Với n>1 ta có: T(n) = 2T( ) + C2 n = 2(2T( ) + C ) + C = 4T( ) + 3C 4 2 2 2 n = 2iT( ) + (2i - 1)C 2i 2 Quá trình dừng khi =1 n = 2i i = log2n Khi đó: 39
44. T(n) = nT(1) +(2log2n -1)C2 = C1n + C2(2log2n -1) Vậy T(n) = O(n) 2.2.2. Một số thuật toán sắp xếp Bài toán: Cho dãy số a có n phần a1, a2, , an . Hãy sắp xếp dãy theo thứ tự tăng dần. 1) S¾p xÕp nhanh (Quicksort) * Ý tưởng: Chọn x là một phần tử làm biên (thường chọn là phần tử ở giữa dãy số). Phân hoạch dãy thành 3 dãy con 1. ak x , với k = j n ak x Hình 2.1. Phân hoạch dãy a thành 3 dãy con Nếu số phần tử trong dãy con 1, dãy con 3 lớn hơn 1 thì ta tiếp tục phân hoạch theo phương pháp trên. Ngược lại thì dừng. * Thiết kế thuật toán Phân hoạch dãy am, am+1, ., an thành 2 dãy con: Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị biên, m x) j ; Bước 2c : Nếu i = x; a[j]<=x mà a[j] đứng sau a[i] Hoán vị (a[i],a[j]); i++; j ; 40
45. Bước 3 : Nếu i x Bước 2 : Nếu ( m < j ) // dãy con 1 có nhiều hơn 1 phần tử Phân hoạch dãy am aj Nếu ( i < n ) // dãy con 3 có nhiều hơn 1 phần tử Phân hoạch dãy ai an Chẳng hạn cho dãy số a: 12 2 8 5 1 6 4 15 Phân hoạch đoạn l=1, r = 8: x = A[4] =5 Phân hoạch đoạn l =1, r = 3: x = A[2] = 2 41
46. Phân hoạch đoạn l = 5, r = 8: x = A[6] = 6 Phân hoạch đoạn l = 7, r = 8: x = A[7] = 6 Hình 2.2. Sắp xếp dãy a theo thứ tự tăng dần Quich-Sort(a,l,r) { i = l; j = r; x = a[(l+r)/2]; // Chọn phần tử giữa while (i x) j ; if (i <= j) { tg = a[i]; a[i]=a[j] a[j]=tg; i++; 42
47. j } } if (l i ) QS(a,i,r); * Đánh giá độ phức tạp tính toán của thuật toán Gọi T(n) là thời gian thực hiện thuật toán, p(n) là thời gian để phân một dãy n phần tử thành hai dãy con thì: T(n) = p(n) + T(J-l) + T(r-i) = Cn + T(J-l) + T(r-i) (C là hằng số) Trường hợp xấu nhất xảy ra khi phần tử được chọn luôn là lớn nhất hoặc nhỏ nhất: sau khi phân hoạch một trong hai dãy con chỉ có một phần tử, dãy kia gồm n-1 phần tử (khi j = l hoặc r = i) Giả sử j = l thì ta có: T(n) = Cn + T(0) + T(n-1) = Cn + T(n-1) = Cn + C(n-1) + T(n-2) = Cn + C(n-1)+ +C + T(0) n( n 1) = C 2 Vậy T(n) = O(n2) Trường hợp tốt nhất xảy ra khi dãy luôn được chia đôi. Khi đó ta có phương trình truy hồi: C nếu n=1 T(n)= n 2T( ) + n nếu n>1 2 Trong đó: 2T( ) là thời gian sắp xếp hai dãy con n là thời gian kiểm tra mỗi phần tử 43
48. Ta có với n>1 thì: n T(n) = 2T( ) + n 2 n n = 2(2T( )+ ) + n = 4T( ) +2 n 4 4 n n = 4(2T( )+ ) + 2n = 8T( ) +3n 8 8 n = 2iT( ) +i.n 2 i n Dừng khi =1 2 i n= 2i i= log2n Và khi đó ta có: T(n) = nT(1) + nlog2n = Cn + nlog2n = O(nlog2n) Trường hợp trung bình người ta đã chứng minh được rằng: T(n)= O(nlog2n) 2) Sắp xếp trộn * Ý tưởng Thuật toán sắp xếp kiểu trộn hai đường trực tiếp được thực hiện theo nhiều bước lặp. Mỗi bước lặp bao gồm hai giai đoạn : Giai đoạn 1: Phân bố luân phiên từng p phần tử từ dãy a vào các dãy trung gian b và c trong khi chưa hết dãy a. Giai đoạn 2: Trộn từng bộ p phần tử trong dãy b với p phần tử trong c, kết quả trộn được đưa vào a, trong khi chưa hết dãy b và chưa hết dãy c. Các bước lặp còn được thực hiện trong khi p còn ≤ n . Bước đầu tiên p được khởi động bằng 1. 44
49. Mỗi bước lặp sau( sau một lần phân bố và trộn ), số phần tử p sẽ khởi động lại là : p = p * 2 . Ví dụ 2.1. Giả sử a là dãy sau: 11 34 20 8 65 25 11 45 21 70 15 20 8 Đầu tiên ta phân bố luân phiên từng phần tử của dãy a vào các dãy trung gian b và c (p=1). + Lần phân bố đầu tiên (p=1) Dãy b: 11 20 65 11 21 15 8 Dãy c: 34 8 25 45 70 20 Thực hiện trộn hai đường từng phần tử của b với từng phần tử của c, kết quả đưa vào dãy a. 11, 34 8, 20 25, 65 11, 45 21, 70 15, 20 8 + Lần phân bố thứ 2 (p=2) Dãy b: 11, 34 25, 65 21, 70 8 Dãy c: 8, 20 11, 45 15, 20 Thực hiện trộn hai đường p phần tử của b với p phần tử của c, kết quả đưa vào dãy a. 8, 11, 20, 34 11, 25, 45, 65 15, 20, 21, 70 8 + Lần phân bố thứ 3 (p=4) Dãy b: 8, 11, 20, 34 15, 20, 21, 70 45
50. Dãy c: 11, 25, 45, 65 8 Thực hiện trộn hai đường p phần tử của b với p phần tử của c, kết quả đưa vào dãy a. 8, 11, 11, 20, 25, 34, 45, 65 8, 15, 20, 21, 70 + Lần phân bố thứ 4 (p=8) Dãy b: 8, 11, 11, 20, 25, 34, 45, 65 Dãy c: 8, 15, 20, 21, 70 Thực hiện trộn hai đường p phần tử của b với p phần tử của c, kết quả đưa vào dãy a. 8, 8, 11, 11, 15, 20, 20, 21, 25, 34, 45, 65, 70 Hình 2.3. Sắp xếp dãy a theo thứ tự tăng dần Lúc này a đã được sắp thứ tự. * Thiết kế thuật toán input a[1 n]; // dãy cần sắp Output a đã được sắp Mô tả: p = 1; Trong khi (p <= n) ta thực hiện : { - Trong khi chưa hết dãy a thì phân bố luân phiên từng p phần tử từ dãy a vào các dãy trung gian b và c - Trong khi chưa hết dãy b và chưa hết dãy c thì trộn từng cặp p phần tử trong dãy b với p phần tử trong dãy c, kết quả ghi vào a. - p = 2p } 46
51. Mô tả trên có thể viết thành hàm : mergesort() { p = 1; while ( p <= n ) { distribution (p); merge(p); p = p * 2; } } Như vậy, thuật toán chủ yếu được xây dựng trên 2 công việc : - distribution(p) : Phân bố luân phiên p phần tử từ dãy a vào các dãy trung gian b, c trong khi chưa hết dãy a. - merge(p) : Trộn từng cặp p phần tử trong b, và p phần tử trong c, kết quả lưu trử vào a, trong khi chưa hết dãy b và chưa hết dãy c. Với công việc thứ nhất: Phân bố luân phiên p phần tử từ dãy a vào các dãy trung gian b, c cho đến hết dãy a. Input a; Output b, c; Mô tả Thực hiện { Đọc từng p phần tử trong a và chép luân phiên vào b, c; } Trong khi (chưa hết dãy a); Trong mô tả trên, có 2 thao tác con cần phải lưu ý : Thao tác 1: Làm thế nào để xử lý một cách tự động việc chép luân phiên vào b và c. Ta thực hiện bằng cách : Dùng một khoá k, với k {1,2} và quy định : 47
52. Nếu k = 1 thì chép vào b; Nếu k = 2 thì chép vào c; Giả sử đầu tiên cho k = 1 để quyết định chép p phần tử của a vào b trước. Sau mỗi lần chép xong p phần tử, ta chỉ cần khởi động lại giá trị k = 3-k . Thao tác 2: Đọc p phần tử của a chép vào b như thế nào ? Ta đọc từng phần tử của a và chép phần tử đó vào b; Việc đọc chép từng phần tử này còn được thực hiện trong khi chưa đủ p phần tử và chưa hết dãy a. Vậy thao tác phân bố có thể mô tả chi tiết như sau : do { i = 1; while ( (i <= p) && (chưa hết dãy a) ) { Đọc phần tử thứ i trong a; if ( k == 1) chép vào b; else chép vào c; i++; } k = 3-k; } while(chưa hết dãy F); Thao tác phân bố cài đặt thành một hàm như sau : //F, F1, F2, n, h1,h2 là các biến toàn cục. distribute(p) { int i, k=1, l = 1; h1 = 0; h2 = 0; do { 48
53. i = 1; while( i<=p && l <= n) { if(k==1) { h1++; F1[h1] = F[l]; } else { h2++; F2[h2] = F[l]; } i++; l++; } k = 3-k; } while(l <= n); } Với công việc thứ hai: Trộn từng bộ p phần tử trong c, và p phần tử trong c, kết quả lưu tr? vào a, trong khi chưa hết b và c. Input b, c; Output a; Mô tả : Trong khi ( chưa hết dãy b và chưa hết dãy c ) { Trộn từng cặp p phần tử của b và của c vào a; } Trong khi (chưa hết dãy c) 49
54. chép các phần tử còn lại của c vào a; Trong khi (chưa hết dãy b) chép các phần tử còn lại của b vào a; Ta cần chỉ rõ công việc trộn từng cặp p phần tử của b và của c vào a hoạt động như thế nào ? Đó là : - (*) : Đọc từng phần tử trong b, trong c, so sánh giá trị của chúng, giá trị nào nhỏ hơn thì chép phần tử tương ứng vào a. Nếu là phần tử của b thì đọc tiếp 1 phần tử của b; ngược lại thì đọc tiếp 1 phần tử của c - ( ) :Thao tác trên còn được thực hiện trong khi : chưa đọc đủ p phần tử trong b và chưa đọc đủ p phần tử trong c và chưa hết dãy c và chưa hết dãy b; Vòng lặp ( ) dừng khi đã đọc đủ p phần tử trong c, hoặc đã đọc đủ p phần tử trong b, hoặc hết dãy b hoặc hết dãy c; Và khi đó ta cần xử lý các trường hợp sau : Trong trường hợp chưa hết dãy b và chưa hết dãy c : Nếu chưa đủ p phần tử trong b, thì đọc và chép các phần tử của b vào a cho đủ p. Tương tự như vậy cho c. * Đánh giá độ phức tạp tính toán của thuật toán Ta nhận xét rằng, trong phương pháp sắp xếp bằng trộn hai đường trực tiếp, số lượng các bước sao chép các phần tử từ dãy này sang dãy kia còn lớn hơn số lượng các bước so sánh giữa các phần tử : Vì ứng vớùi một lần so sánh thì có một thao tác sao chép, nhưng nếu một dãy nào đó xử lý cạn (hết dãy) thì phần đuôi của dãy còn lại được sao chép mà không ứng với một phép so sánh nào. Vì thế, đối với phương pháp này, ta chọn phép sao chép làm căn cứ đánh giá thời gian thực hiện của thuật toán. Trong mỗi lần phân bố và trộn thì toàn bộ n phần tử được duyệt qua, so sánh và chép vào dãy đích (output). Như vậy thời gian chi phí cho mỗi bước có cấp là O(n). Vì trong mỗi bước (bước thứ k) ta giải quyết được 2k = p giá trị và tiến trình dừng khi p ≥ n nên ta có lg2n bước, do đó cấp thời gian chi phí cho phương pháp này là O(nlg2n). Một nhượïc điểm của phương pháp sắp xếp bằng kiểu trộn hai đường trực tiếp là chi phí cho không gian quá lớn: nó đòi hỏi cung cấp vùng nhớ 2n phần tử, gấp đôi so với phương pháp thông thường. Do đó phương pháp này chỉ thích hợp khi ta thao tác trên các tệp. 50
55. Mặt khác, phương pháp sắp xếp kiểu trộn hai đường trực tiếp có một nhược diểm quan trọng nữa là nó tự giới hạn số lượng các giá trị cố định là 1, 2, 4, , 2k, trong đó 2k r kết thúc và trả lại giá trị 0 (không tìm thấy) - Nếu l r) loc=0; 51
56. else { m=[(l+r)/2]; if(x a[m]) loc=TKNP(m+1,r,a,x) else loc=m; return(loc); } 4) Đánh giá độ phức tạp tính toán của thuật toán - Xây dựng phương trình truy hồi: c1 nếu n=1 T(n)= n T( )+c2 nếu n>1 2 Với n>1 ta có: T(n) = T( )+ c2 n = T( )+ 2c2 4 n = T( )+ 3c2 8 n = T( )+ ic2 2 i n Dừng khi =1 2 i n=2i i=log2n Do đó T(n) = T(1) + c2log2n = c1 + c2log2n 52
57. = O(log2n) 2.2.4. Nh©n c¸c sè nguyªn lín. 1) Bài toán Cho hai số nguyên X và Y, mỗi số gồm n chữ số. Tính tích của hai số nguyên đó. 2) Ý tƣởng Biểu diễn X và Y dưới dạng X = A10n/2 + B và Y = C10n/2 + D Trong đó A, B, C, D là các số có n/2 chữ số. Chẳng hạn với X = 1234 thì A = 12 và B = 34 vì 12*102 + 34 = 1234 = X Với cách biểu diễn này thì XY = AC10n + (AD + BC)10n/2 + BD (*) Thay vì nhân trực tiếp 2 số có n chữ số, ta phân tích bài toán ban đầu thành một số bài toán nhân 2 số có n/2 chữ số. Sau đó, ta kết hợp các kết quả trung gian theo công thức (*). Việc phân chia này sẽ dẫn đến các bài toán nhân 2 số có 1 chữ số. Đây là bài toán cơ sở. Tóm lại: - Kích thước bài toán: số chữ số của X, Y - Phân tích: Chia bài toán ban đầu thành các bài toán nhân các số có n/2 chữ số. Quá trình phân chia dừng lại khi kích thước bài toán bằng 1. - Tổng hợp: Tổng hợp kết quả theo công thức (*). Chú ý: Với những số có một số lẻ chữ số ta thêm số 0 vào đầu để được số có một số chẵn chữ số. 3) Thiết kế thuật toán Theo công thức (*) ở trên việc nhân 2 số nguyên có n chữ số được phân chia thành 4 phép nhân các số nguyên có n/2 chữ số, 3 phép cộng và 2 phép nhân với 10n và 10n/2. Phép cộng các số cần O(n). Phép nhân với 10n tốn O(n). Gọi T(n) là thời gian nhân 2 số có n chữ số ta có phương trình truy hồi sau: C1 nếu n =1 T(n)= n 4T( ) + C n nếu n >1 2 2 Khi đó độ phức tạp tính toán sẽ được xác định như sau: Ta có với n>1: 53
58. n T(n) = 4T( )+c2n 2 n 4 n = 4(4T( )+c2 ) + c2n = 16T( ) + 3c2n = 2 T( ) + 3c2n 4 2 2 n 6 n = 16( 4T( )+c2 ) + 3c2n = 64T( ) + 7c2n = 2 T( ) + 7c2n 8 2 3 2i n i = 2 T( ) + (2 - 1)c2n 2 i n Quá trình sẽ dừng khi =1 2 i n =2i i = log2n 2log2 n log2 n Khi đó T(n) = 2 T(1) ( 2 1)C2n 2 = C1n + C2(n-1)n Và T(n) = O(n2) Như vậy ta không cải tiến được gì với giải thuật nhân thông thường. Ta biến đổi công thức (*) lại như sau: XY = AC10n + [(A -B)(D-C) + AC + BD]10n/2 + BD ( ) Theo công thức này, ta chỉ cần 3 phép nhân các số nguyên có n/2 chữ số, 6 phép cộng trừ và 2 phép nhân với 10n, 10n/2. Ví dụ 2.2. Ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho hai toán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạng thành hai nửa: 0981 tách thành w = 09 và x = 81 1234 tách thành y = 12 và z = 34 Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tích cần tìm có thể tính được là: 981 x 1234 = (102w + x)( 102y + z) = 104wy + 102(wz + xy) + xz 54
59. = 1080000 + 127800 + 2754 = 1210554 Thủ tục trên đến bốn phép nhân hai nửa: wy, wz, xy và xz. Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ như không thể được cho đến khi chúng ta nhớ ra rằng mình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểm này, hãy xét tích: r = (w + x)(y+z) = wy + (wz + xy) + xz Chỉ sau một phép nhân, chúng ta thu được tổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau: p = wy = 09 * 12 = 108 q = xz = 81 * 34 = 2754 r = (w + x)(y+z) = 90 * 46 = 4140 và cuối cùng 981 x 1234 = 104p + 102(r – p – q) + q = 1080000 + 127800 + 2754 = 1210554. Như vậy tích của 981 và 1234 có thể rút gọn về ba phép nhân của hai số có hai chữ số (09 với 12, 81 với 34 và 90 với 46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10), phép cộng và phép trừ. Từ đó ta đưa ra thuật toán nhân số nguyên lớn là Nhan(x,y,n) { if (n == 1) Return x[0]*y[0]; Else { a = x[n-1]. . . x[n/2]; b = x[n/2-1] . . . x[0]; c = y[n-1]. . . y[n/2]; d = y[n/2-1] . . . y[0]; U = Nhan(a,c,n/2); 55
60. V = Nhan(b,d,n/2); W = Nhan(a+b,c+d,n/2); Return U*10n + (W-U-V)*10n/2 + V } } 4) Đánh giá độ phức tạp tính toán của thuật toán Ta có phương trình đệ quy sau: T(1) = 1 T(n) = 3T(n/2) + cn Giải phương trình ta được T(n) = O(nlog3) = O(n1.59). Rõ ràng cải tiến hơn giải thuật cũ rất nhiều. thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điển và n càng lớn thì sự cải thiện này càng đáng giá. 56
61. Bµi tËp ch•¬ng 2 1. Hãy đưa ra hai thuật toán được thiết kế theo kỹ thuật chia để trị. 2. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau: Tính tổng: 1 + 1/2 + 1/3 + + 1/n với n là một số nguyên dương. 3. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau: Tìm ước số chung lớn nhất của hai số nguyên dương. 4. Bài toán tháp Hà nội Có n chiếc đĩa với đường kính khác nhau được đặt chồng lên nhau ở vị trí A, đĩa bé ở trên đĩa to. Cần chuyển chồng đĩa sang vị trí B được lấy vị trí C làm trung chuyển với điều kiện: Mỗi lần chỉ được chuyển một đĩa và trong quá trình chuyển không bao giờ được đặt đĩa to ở trên đĩa bé. Hướng dẫn: Vận dụng kỹ thuật chia để trị: Bài toán chuyển N đĩa từ A sang B có thể chia thành các bài toán nhỏ hơn như sau: (a) Chuyển N-1 đĩa ở trên từ A sang C (b) Chuyển một đĩa từ A sang B (c) Chuyển N-1 đĩa từ C sang B. Như vậy bài toán đã được chuyển thành các bài toán tương tự với kích thước nhỏ hơn. Công việc được tiếp tục với (n-1) đĩa và cứ như thế cho đến khi chỉ còn một đĩa. 5. Bài toán hoán đổi hai phần trong dãy Cho a[1 n] là một mảng gồm n phần tử. Ta cần chuyển m phần tử đầu tiên của mảng với phần còn lại của mảng (n-m phân tử) mà không dùng một mảng phụ . Chẳng hạn, với n = 8, a[8] = (1, 2, 3, 4, 5, 6, 7, 8) Nếu m = 3, thì kết quả là : ( 4, 5, 6, 7, 8, 1, 2, 3) Nếu m = 5, thì kết quả là : ( 6, 7, 8, 1, 2, 3, 4, 5) Nếu m = 4, thì kết quả là : ( 5, 6, 7, 8, 1, 2, 3, 4) Hướng dẫn: - Nếu m = n – m: Hoán đổi các phần tử của 2 nửa mảng có độ dài bằng nhau : 57
62. - Nếu m n–m + Nếu m n – m : hoán đổi n-m phần tử đầu tiên với n-m phần tử của phần sau. Sau đó trong mảng a[n-m+1 . . n] ta hoán đổi n-m phần tử cuối mảng với các phần tử của phần đầu. Như vậy, bằng cách áp dụng phương pháp chia để trị, ta chia bài toán thành 2 bài toán con : - Bài toán thứ nhất là hoán đổi hai mảng con có độ dài bằng nhau, cụ thể là hoán đổi nửa số phần tử đầu và cuối của mảng cho nhau bằng cách đổi chỗ từng cặp phần tử tương ứng. - Bài toán thứ hai cùng dạng với bài toán đã cho nhưng kích thước nhỏ hơn, nên có thể gọi thuật toán đệ qui để giải và quá trình gọi đệ qui sẽ dừng khi đạt tới sự hoán đổi 2 phần có độ dài bằng nhau Vậy mấu chốt của thuật toán là thực hiện thao tác hoán đổi 2 nhóm phần tử, lặp lại thao tác này trong khi số lượng phần tử của 2 nhóm còn khác nhau. Vì vậy ta sẽ thay thuật toán đệ qui bằng thuật toán lặp. // Hoán đổi m phần tử đầu của mảng với phần còn lại. Input : a[1 n], m. (m ≤n) Output : a[1 n] với tính chất m phần tử đầu mảng a (mảng nhập ) nằm cuối mảng kết quả, n-m phần tử cuối mảng nhập nằm ở đầu mảng kết quả. Mô tả thuật toán : Transpose(a,n,m) { i = m; j = n-m; m = m+1; Khi ( i != j) Nếu ( i > j) { Exchange(a,m-i,m,j); i = i – j; } Ngược lại { 58
63. j = j – i; Exchange(a,m-i,m+j,i); } Exchange(a,m-i,m,i); } Hàm exchange : input a, i,j, //vị trí m; // Số phần tử cần hoán đổi output a Exchange(a,i,j,m) { Với mọi p = 0 -> m-1 Đổichỗ (a[i+p], a[j+p]); } 6. Lập lịch thi đấu thể thao Có n = 2k đối thủ thi đấu với nhau theo thể thức vòng tròn một lượt: Mỗi đấu thủ phải đấu với các đấu thủ khác 1 trận. Mỗi đấu thủ chỉ đấu nhiều nhất một trận mỗi ngày. Hãy xếp lịch thi đấu sao cho số ngày thi đấu là ít nhất. Hướng dẫn: Vì thể thức thi đấu là vòng tròn một lượt nên mỗi đấu thủ phải thi đấu đúng n-1 trận. Ta dễ dàng thấy rằng vì n là một số chẵn nên ta có thể sắp nhiều nhất là n/2 cặp thi đấu trong một ngày và do đó cần ít nhất n-1 ngày. Ta sẽ tìm cách xây dựng lịch để số ngày thi đấu là n-1. Lịch thi đấu là một bảng n dòng và n-1 cột. Các dòng được đánh số từ 1 đến n và các cột được đánh số từ 1 đến n-1, trong đó dòng i biểu diễn cho đấu thủ i, cột j biểu diễn cho ngày thi đấu j và ô(i, j) ghi đấu thủ phải thi đấu với đấu thủ i trong ngày j. Kỹ thuật chia để trị được áp dụng để xây dựng lịch thi đấu như sau: Ðể sắp lịch cho n đấu thủ, ta sẽ sắp lịch cho n/2 đấu thủ, để sắp lịch cho n/2 đấu thủ, ta sẽ sắp lịch cho n/4 đấu thủ Quá trình này sẽ dẫn đến bài toán cơ sở là sắp lịch thi đấu cho 2 đấu thủ. Hai đấu thủ này sẽ thi đấu một trận trong một ngày, lịch thi đấu cho họ thật dễ sắp. Khó khăn chính là ở chỗ từ các lịch thi đấu cho hai đấu thủ, ta tổng hợp lại để được lịch 59
64. thi đấu của 4 đấu thủ, 8 cấu thủ, Góc trên bên trái của bảng chính là lịch thi đấu của n/2 đấu thủ từ 1 đến n/2 trong các ngày từ ngày 1 đến ngày [(n-1)/2], từ đó ta có góc dưới bên trái là lịch thi đấu trong các ngày này của các đấu thủ từ n/2+1 đến n: nó sẽ bằng các phần tử ở góc trên bên trái cộng thêm n/2. Góc dưới bên phải của bảng chính là góc trên bên trái và góc trên bên phải chính là góc dưới bên trái. Còn với cột [(n-1)/2] +1 thì n/2 đấu thủ đầu sẽ lần lượt đấu với n/2 đấu thủ sau và ngược lại. Chẳng hạn: Xuất phát từ lịch thi đấu cho hai đấu thủ ta có thể xây dựng lịch thi đấu cho 4 đấu thủ như sau: Lịch thi đấu cho 4 đấu thủ sẽ là một bảng 4 dòng, 3 cột. Lịch thi đấu cho 2 đấu thủ 1 và 2 trong ngày thứ 1 chính là lịch thi đấu của hai đấu thủ (bài toán cơ sở). Như vậy ta có Ô(1,1) = “2” và Ô(2,1) = “1”. Tương tự ta có lịch thi đấu cho 2 đấu thủ 3 và 4 trong ngày thứ 1. Nghĩa là Ô(3,1) =“4” và Ô(4,1) = “3”. (Ta cố thể thấy rằng Ô(3,1) = Ô(1,1) + 2 và Ô(4,1) = Ô(2,1) + 2 ). 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. Bây giờ để hoàn thành lịch thi đấu cho 4 đấu thủ ta điền nốt cột 2. Lịch thi đấu cho 8 đấu thủ là một bảng gồm 8 dòng, 7 cột. Góc trên bên trái chính là ch thi đấu trong 3 ngày đầu của 4 đấu thủ từ 1 đến 4. Các ô của góc dưới bên trái sẽ bằng các ô tương ứng của góc trên bên trái cộng với 4. Ðây chính là lịch thi đấu cho 4 đấu thủ 5, 6, 7 và 8 trong 3 ngày đầu. Bây giờ chúng ta hoàn thành việc sắp lịch bằng cách lấp đầy góc dưới bên phải bởi góc trên bên trái và góc trên bên phải bởi góc dưới bên trái và điền nốt cột 4. Dưới đây là các bảng xếp lịch thi đấu cho 2 đấu thủ, 4 đấu thủ và 8 đấu thủ theo cách xây dựng trên: 8 đấu thủ 2 đấu thủ 4 đấu thủ 1 1 2 3 1 2 3 4 5 6 7 1 2 1 2 3 4 1 2 3 4 5 6 7 8 2 1 2 1 4 3 2 1 4 3 6 5 8 7 3 4 1 2 3 4 1 2 7 8 5 6 4 3 2 1 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 60
65. 7. Bài toán tìm cặp điểm gần nhất (láng giềng gần nhất) Trong mặt phẳng cho n điểm phân biệt. Hãy tìm hai điểm gần nhau nhất (khoảng cách Ơcolit là nhỏ nhất). Hướng dẫn: Xây dựng một thuật toán dựa trên kỹ thuật chia để trị với ý tưởng là: sắp xếp các điểm theo một trục toạ độ, như trục x chẳng hạn, rồi dùng thứ tự này để chia tập điểm thành hai phần. Trong toàn bộ tập điểm đã cho, cặp điểm gần nhất hoặc là cặp gần nhất trong cùng một bên nào đó, hoặc là một cặp điểm cắt ngang đường thẳng phân giới giữa hai tập điểm thành phần. Dĩ nhiên, trường hợp đáng chú ý là khi cặp điểm gần nhất cắt ngang đường phân giới. Cặp điểm gần nhất trong mỗi nửa bên rõ ràng là tìm được bằng các lời gọi đệ quy, nhưng còn các cặp có mỗi điểm ở một bên đường phân giới sẽ được kiểm tra như thế nào? Điều tất nhiên là chúng ta sẽ chỉ cần xét những điểm trong khoảng cách min ở hai bên đường phân giới (vì đang tìm cặp điểm gần nhất), với min là khoảng cách nhỏ hơn giữa các cặp điểm gần nhất ở mỗi nửa bên. Tuy nhiên, trong trường hợp xấu nhất thì nhận xét này là không đủ, vì có thể có nhiều cặp gần với đường phân giới; ví dụ như tất cả các điểm ở mỗi nửa bên có thể sắp thành một hàng ngay cạnh đường thẳng phân giới. Để xử lý tình huống trên, cần phải sắp các điểm theo y. Như vậy, chúng ra có thể giới hạn các khoảng cách phải tính như sau: - Xử lý các điểm theo chiều tăng của y - Kiểm tra xem mỗi điểm có nằm trong dải đứng chứa các điểm trong phạm vi min kể từ điểm phân giới - Với mỗi điểm trong dải trên, tính khoảng cách giữa điểm này với các điểm cũng trong dải và có tung độ y nhỏ hơn tung độ của điểm đang xét nhưng không nhỏ quá min. Khoảng cách giữa các điểm ở mỗi nửa bên tối thiểu là min nên số điểm phải kiểm tra sẽ ít hơn. Viết một hàm đệ quy vừa sắp theo y lại vừa tìm cặp điểm gần nhất. Thủ tục này sẽ chia đôi tập điểm, rồi gọi lại chính nó để sắp hai nửa bên theo y và tìm cặp điểm gần nhất trong mỗi nửa, sau đó trộn hai nửa bên để hoàn tất việc sắp theo y và áp dụng lại thủ tục trên để hoàn tất việc tính cặp điểm gần nhất. Khi sắp theo y, việc chia đôi có thể làm bằng bất kỳ cách nào, nhưng với phép tính cặp điểm gần nhất, việc chia đôi yêu cầu có một nửa bên có hoành độ x nhỏ hơn nửa bên còn lại. Điều này được thực hiên bằng cách sắp theo x trước khi chia đôi tập điểm. 61
66. Ch•¬ng 3 Kü thuËt tham lam 3.1. Néi dung kü thuËt 3.1.1. Bµi to¸n tèi •u tæ hîp Bài toán tối ưu tổ hợp có dạng tổng quát như sau: Cho hàm f(x) xác định trên một tập hữu hạn các phần tử D. Hàm f(x) được gọi là hàm mục tiêu, tập D được gọi là tập các phương án 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ế được gọi là phương án tối ưu. Ta có thể tìm thấy 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ù tập hợp D là hữu hạn nhưng để tìm 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” thì độ phức tạp tính toán sẽ có có cấp hàm mũ. 3.1.2. Néi dung kü thuËt tham lam Tham lam (còn gọi là tham ăn, háu ăn) hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp trong quá trình xây dựng một phương án x. Phương án x được xây dựng bằng cách lựa chọn từng thành phần xi 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. Áp dụng kĩ thuật tham lam sẽ cho một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu. 3.2 C¸c vÝ dô ¸p dông 3.2.1. Bµi to¸n ng•êi giao hµng 1) Bài toán Có 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 62
67. đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Giả thiết rằng mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. Nếu sử dụng 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 của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất. Như vậy chúng ta cần xét tất cả là (n-1)!/2 chu trình. Thực vậy, do mỗi chu trình đều đi qua tất cả các đỉnh (thành phố) nên ta có thể cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác, nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên, chúng ta còn n-2 cách chọn cạnh thứ hai, do đó ta có (n-1)(n-2) cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ thấy có (n-1)! cách chọn một chu trình. Tuy nhiên với mỗi chu trình ta chỉ quan tâm đến tổng độ dài các cạnh chứ không quan tâm đến hướng vì vậy có tất cả (n - 1)!/2 chu trình. Ðó là một thuật toán có độ phức tạp tính toán là hàm mũ. 2) Thiết kế thuật toán - Ý tưởng: Gọi n thành phố người giao hàng phải đi qua là các thành phố 1, 2, , n. Xuất phát từ một thành phố i nào đó đi đến thành gần thành phố i nhất trong trong n-1 thành phố còn lại, chẳng hạn thành phố j, từ thành phố j đi đến thành phố gần thành phố j nhất trong n-2 thành phố còn lại. Quá trình được lặp lại cho đến khi đã đi hết n thành phố thì quay về thành phố i - ta được một chu trình. - Thuật toán: Giaohang (a, n, dau) /* Mảng a mà a[i][j] là độ dài từ thành phố i đến thành phố j n số thành phố dau: thành phố xuất phát xet[v]: ghi nhận trạng thái thành phố v- chưa đến bằng 0, đã đến bằng 1 cost: lưu độ dài chu trình Mảng ct có các phần tử lưu trữ lần lượt n thành phố đi qua */ { for(k = 1; k <= n; k++) 63
68. xet[k] = 0; cost = 0; v = dau; i = 1; ct[i] = v; xet[v] = 1; while(i a[v][k]) { min = a[v][k]; w = k; } v = w; i++; ct[i] = v; xet[v] = 1; cost += min; } return cost; } 3) Đánh giá độ phức tạp tính toán của thuật toán Phép toán tích cực là phép kiểm tra (!xet[k]), phép kiểm tra này nằm trong vòng lặp for (k = 1; k <= n; k++) và vòng lặp while(i < n). Mỗi vòng lặp thực hiện n lần, do đó độ phức tạp tính toán là O(n2). Nhận xét: 64
69. Có thể giải quyết bài toán bằng kỹ thuật tham lam theo cách tiếp cận khác như sau: 1. Sắp xếp các cạnh theo thứ tự tăng dần của độ dài. 2. Lần lượt 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 đó thỏa 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, do yêu cầu của bài toán là mỗi thành phố chỉ được đến một lần: một lần đến và một lần đi) Cho đến khi xây dựng được một chu trình. Thuật toán Giaohang() /* E là tập hợp các cạnh đã được sắp xếp theo chiều tăng của độ dài, Chu_trinh là tập hợp các cạnh được chọn để đưa vào chu trình */ { Chu_Trinh = Φ; Gia = 0; while(E <> Φ) { if (cạnh e có thể chọn) { Chu_Trinh = Chu_Trinh + [e] ; Gia = Gia + độ dài của e; } E = E-[e]; } } Thuật toán trên có độ phức tạp tính toán là O(n2) 3.2.2. Bµi to¸n chiÕc ba l« 1) Bài toán 65
70. Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi và một giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất. 2) Thiết kế thuật toán Theo yêu cầu của bài toán thì ta cần những đồ vật có giá trị cao mà trọng lượng lại nhỏ để sao cho có thể mang được nhiều “đồ quý”, sẽ là hợp lý khi ta quan tâm đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượng. Ðơn giá càng cao thì đồ càng quý. Từ đó ta có kĩ thuật tham lam áp dụng cho bài toán này là: 1. Tính đơn giá cho các loại đồ vật. 2. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ. 3.Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép. 4. Xác định trọng luợng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa. Ví dụ 3.1. Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng dưới: Tên đồ vật Trọng lượng Giá trị A 15 30 B 10 25 C 2 2 D 4 6 Hình 3.1. Trọng lượng và giá trị của 4 loại đồ vật Tính đơn giá cho các loại đồ vật: 66
71. Tên đồ vật Trọng lượng Giá trị Đơn giá A 15 30 2 B 10 25 2,5 C 2 2 1 D 4 6 1,5 Hình 3.2. Đơn giá của 4 loại đồ vật Sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng sau: Tên đồ vật Trọng lượng Giá trị Đơn giá B 10 25 2,5 A 15 30 2 D 4 6 1,5 C 2 2 1 Hình 3.3. Các đồ vật theo đơn giá giảm dần Theo đó thì thứ tự ưu tiên để chọn đồ vật là B, A, D, C. Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vật loại B, trọng lượng còn lại trong ba lô là 37 - 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C. Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và 1 cái loại C. Tổng trọng lượng là 3*10 + 1*4 + 1*2 = 36 Tổng giá trị là 3*25+1*6+1*2 = 83. Thuật toán giải bài toán cái ba lô bằng kĩ thuật tham lam như sau: Tổ chức dữ liệu: - Mỗi đồ vật được biểu diễn bởi một mẩu tin có các trường: • Ten: Lưu trữ tên đồ vật. • Trong_luong: Lưu trữ trọng lượng của đồ vật. • Gia_tri: Lưu trữ giá trị của đồ vật 67
72. • Don_gia: Lưu trữ đơn giá của đồ vật • Phuong_an: Lưu trữ số lượng đồ vật được chọn theo phương án. - Danh sách các đồ vật được biểu diễn bởi một mảng các đồ vật. Thuật toán: input: mảng dsdv mà các trường Ten, Trong_luong, Gia_tri, Don_gia đã có giá trị. ouput: Phương án chọn đồ vật - được thể hiện ở giá trị của các trường Phuong_an của các đồ vật Hàm Chon(d,S) cho số lượng đồ vật có trọng lượng d được chọn, S là trọng lượng còn có thể cho thêm của ba lô. Chon(d,S) { i=0; while(S>d) { i++; S=S-d; } return(i); } Hàm Dovat(dsdv,W) tìm ra phương án chọn đồ vật Dovat(dsdv,W) { /*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/ for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(dsdv[i].don_gia<dsdv[j].don_gia) { tg=dsdv[i]; dsdv[i]=dsdv[j]; dsdv[j]=tg; 68
73. } /* Xây dựng phương án*/ for(i=1;i<=n-1;i++) { Dsdv[i].Phuong_an:= Chon(dsdv[i].Trong_luong, W); W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong; } } Trong trường hợp trọng lượng của các vật và W là các số nguyên thì ta bỏ hàm Chon(d,S) và khi đó thuật toán sẽ là: Dovat(dsdv,W) { /*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/ for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(dsdv[i].don_gia<dsdv[j].don_gia) { tg=dsdv[i]; dsdv[i]=dsdv[j]; dsdv[j]=tg; } /* Xây dựng phương án*/ for(i=1;i<=n-1;i++) { Dsdv[i].Phuong_an:= W/dsdv[i].Trong_luong; W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong; } } 3) Đánh giá độ phức tạp tính toán của thuật toán Trong thuật toán Dovat(dsdv,W) ta phải sắp xếp mảng dsdv, công việc này 69
74. mất thời gian O(n2). Tiếp theo là công việc xây dựng phương án chọn đồ vật. Công việc này được thực hiện bởi vòng lặp for(i=1;i<=n-1;i++), vòng lặp được thực hiện n lần, mỗi lần lặp lại gọi hàm Chon(dsdv[i].Trong_luong, W). Trong hàm Chon(dsdv[i].Trong_luong, W) có vòng lặp while thực hiện nhiều nhất là n phép so sánh. Do đó công việc xây dựng phương án chọn đồ vật mất thời gian O(n2). Vậy độ phức tạp tính toán của thuật toán là O(n2). 3.2.3. Bµi to¸n t« mµu b¶n ®å 1) Bài toán Hãy dùng số màu ít nhất để tô màu cho một bản đồ với điều kiện: mỗi quốc gia được tô một màu và hai quốc gia kề nhau (có chung đường biên giới ) thì phải có màu khác nhau. Ta xây dựng một đơn đồ thị vô hướng: Mỗi quốc gia tương ứng với một đỉnh của đồ thị, hai quốc gia kề nhau thì hai đỉnh tương ứng kề nhau (có cạnh nối giữa chúng). Khi đó bài toán đã cho sẽ chính là bài toán: Hãy dùng số màu ít nhất để tô màu cho các đỉnh của một đơn đồ thị vô hướng sao cho hai đỉnh kề nhau phải có màu khác nhau. (Bài toán tô màu đồ thị) 2) Thiết kế thuật toán Có nhiều kỹ thuật được sử dụng để thiết kế thuật toán giải bài toán tô màu đồ thị và tìm được phương án tối ưu với thời gian hàm mũ. Ở đây chúng ta sẽ thiết kế thuật toán giải bài toán này theo tinh thần của kỹ thuật tham lam: kết quả có thể chỉ là một phương "tốt" chứ chưa đảm bảo là tối ưu nhưng thời gian là có thể chấp nhận được. Trước hết ta định nghĩa bậc của một đỉnh là số đỉnh trên đồ thị chưa được tô mầu mà đỉnh này được nối trực tiếp với đỉnh đang xét bằng một cạnh nối trực tiếp. Nếu đỉnh đó không được nối với bất kỳ đỉnh nào thì bậc của đỉnh đó là 0 -Bước 1 : Tìm đỉnh có bậc cao nhất trên đồ thị ( gọi là đỉnh u ) -Bước 2 : Tăng số màu cần tô lên 1 và tô màu cho đỉnh vừa tìm -Bước 3 : Tìm đỉnh v để tô màu giống u thỏa mãn các điều kiện sau : v đi đến đỉnh u thông qua duy nhất 1 đỉnh w khác và v có số bậc lớn nhất. Nếu không tìm được đỉnh như vậy ta sẽ tìm đỉnh v có bậc lớn nhất mà không kề với u. Nếu tìm được v thỏa mãn thì ta tô màu cho v chính là màu của đỉnh u. Sau đó nhập đỉnh u và 70
75. v vào làm 1 đỉnh. Tức : đỉnh w kể với v thì cũng coi như kề với u ( a[v,w] =1 thì a[u,w] =1 and a[w,u] = 1 ) -Bước 4 : Lập lại bước 3 cho đến khi v = 0. -Bước 5 : Lặp lại bước 1 cho đến khi tô hết mầu các đỉnh của đồ thị. Tổ chức dữ liệu: somau: Lưu trữ số màu cần tô n : Số đỉnh của đồ thị color : Mảng lưu màu của đỉnh đồ thị, color [i] = 0 nghĩa là đỉnh i chưa được tô màu a : ma trận kề - a[u,v] = 1 tức hai đỉnh u và c có cạnh nối, a[u,v] = 0 tức hai đỉnh không có cạnh nối count : Đếm số đỉnh đã tô màu ,Count = n: dừng Thuật toán Thuật toán được xây dựng qua các hàm sau: - dinh_bac_max(): Hàm tìm ra đỉnh có bậc lớn nhất - tomau(u ): tô màu cho đỉnh u - tim_dinh_cung_mau(u, v): tìm đỉnh v để tô màu cùng với màu đinh u - Nhapdinh(u,v): u,v được tô cùng màu thì các đỉnh kề với v được coi như kề với u. - main() Các hàm: dinh_bac_max () { max := -1;//Vi co the co dinh co bac la 0 for(i=1;i<=n;i++) if (color[i] == 0) /*Xét các đỉnh chưa được tô màu để tìm ra đỉnh bậc lớn nhất*/ { dem = 0; for(j=1;j<=n;j++) 71
76. if ((color[j] == 0) && (a[i][j] == 1)) dem++; if (dem > max) //Cập nhật giá trị lớn nhất { max = dem; u = i; } } return(u); } tomau(u); { count = count + 1; color[u] = somau; } tim_dinh_cung_mau(u, v ) { max = 0; for(i=1;i max) then // Cập nhật giá trị max { max = dem; 72
77. v = i; } } if (v > 0) return; /*Nếu tồn tại v chưa tô màu đi đến được u thông qua duy nhất 1 đỉnh khác*/ max = -1; // vì có thể tồn tại v mà bậc chỉ là 0 for(i=1;i max) { max = dem; v = i; } } } Nhapdinh(u,v) { for(i=1;i<=n;i++) if (a[v,i] == 1) { a[u,i] = 1; a[i,u] = 1; } } 73
78. main() { somau = 0; do somau = somau+1; u = dinh_bac_max; tomau(u); do tim_dinh_cung_mau(u,v); /* Tìm đỉnh v có thể tô màu giống mầu của u*/ if (v > 0) { tomau(v); nhap_dinh(u,v); } while (v == 0); while (count == n); } 3) Đánh giá độ phức tạp tính toán của thuật toán Trong hàm main() có hai vòng lặp do while lồng nhau, mỗi vòng lặp thực hiện nhiều nhất n lần. Trong hai vòng lặp này có lời gọi hàm tim_dinh_cung_mau(u,v), trong hàm này phép toán tích cực là phép so sánh (có thời gian O(1)) được đặt trong hai vòng lặp lồng nhau là for(i=1;i<=n;i++) và for(j=1;j<=n;j++). Vậy độ phức tạp của thuật toán là O(n4) 3.2.4. Tìm cây khung nhỏ nhất 1) Bài toán Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = { 1,2, ,n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số không âm c(e), gọi là độ dài của nó. Giả sử T =(V, ET) là cây khung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài của các cạnh của nó: 74
79. c(T)  c(e) e ET Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất. Để giải bài toán cây khung nhỏ nhất, tất nhiên có thể liệt kê tất cả các cây khung của đồ thị và chọn trong số chúng cây khung nhỏ nhất. Phương pháp như vậy, trong trường hợp đồ thị đầy đủ, sẽ đòi hỏi thời gian cỡ nn-2 , và rõ ràng không thể thực hiện được ngay cả với những đồ thị với số đỉnh cỡ hàng chục. Rất may đối với bài toán cây khung nhỏ nhất chúng ta đã có những thuật toán rất hiệu quả để giải chúng .Chúng ta sẽ xét một trong số những thuật toán như vậy, đó là thuật toán Prim 2) Thuật toán Prim Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất, phương pháp này sử dụng kỹ thuật tham lam. Cụ thể, bắt đầu từ một đỉnh nào đó tuỳ ý của đồ thị chẳng hạn là đỉnh s, đầu tiên ta nối s với đỉnh lân cận có độ dài nhỏ nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các đỉnh kề của đỉnh s, cạnh(s,y) có độ dài nhỏ nhất. Tiếp theo, trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm ba đỉnh và hai cạnh. Quá trình này sẽ được tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh, đó chính là cây khung nhỏ nhất cần tìm. Giả sử đồ thị cho bởi ma trận trọng số C= { c[i,j] i,j =1, 2, , n} với qui ước c[x, x] = 0 và c[x,y] = nếu không có cạnh (x,y). Trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của một đỉnh x sẽ gồm hai thành phần và có dạng [ ax, bx], trong đó thành phần ax ghi nhận đỉnh của cây khung gần x nhất (cây khung đang xây dựng) còn thành phần bx dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối đỉnh x với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh x đến tập đỉnh của cây khung), tức là: bx = min { c[x,y]: y VT } (VT là tập các đỉnh của cây khung đang xây dựng). Các nhãn sẽ được chỉnh dần trong một quá trình lặp. Tại mỗi bước lặp tìm được một đỉnh có nhãn “tốt nhất” để bổ sung vào cây khung. Đỉnh đã được chọn bổ sung vào 75
80. cây khung sẽ không được tham gia chỉnh nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi tập VT có n phần tử. Thuật toán Prim được thể hiện nhu sau: CKNN() { // khởi tạo //Chọn s là một đỉnh nào đó của đồ thị VT={s}; ET=; bs=0; as=s; for (x V \ VT) { ax = s; bx= c[s,x]; } kt=1; while(kt) { // tìm đỉnh có nhãn “tốt nhất” bổ sung vào cây khung p=v; //v là một đỉnh thuộc V\VT for (x V \ VT) if(bx<bp) p=x; VT =VT  {p}; ET=ET{(p, ap)}; if ( VT ==n) { T= (VT, ET) là cây khung nhỏ nhất của đồ thị; kt=0; } else /* chỉnh nhãn */ 76
81. for (x V\VT) if (bx > c[p, x]) { bx:=c[p, x]; ax:=p; } } } 3) Độ phức tạp tính toán của thuật toán Trong thuật toán ta coi phép toán tích cực là phép so sánh (bx<bp) khi tìm đỉnh có nhãn tốt nhất để bổ sung vào cây khung. Phép so sánh nằm trong vòng lặp for (x V\VT), vòng lặp này thực hiện nhiều nhất (n-1) lần. Vòng lặp for (x V\VT) nằm trong vòng lặp while(kt) có số lần thực hiện nhiều nhất (n-1) lần. Vậy độ phức tạp tính toán của thuật toán là O(n2) 3.2.5. Tìm đƣờng đi ngắn nhất 1) Bài toán Cho đồ thị có hướng (hoặc vô hướng) G=(V,E), V =n, E =m với các cạnh được gán trọng số, nghĩa là, mỗi cạnh (u,v) E được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. ở đây ta chỉ xét đồ thị có trọng số của các cạnh là không âm. Chúng ta sẽ đặt a(u,v) = , nếu (u,v) E. Nếu dãy v0, v1, , vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau p a(vi 1 ,vi ) i 1 (nếu chúng ta gán trọng số cho tất cả các cạnh đều bằng 1, thì ta thu được định nghĩa độ dài của đường đi như là số cạnh của đường đi). Bài toán tìm đường đi ngắn nhất trên đồ thị có thể phát biểu như sau: Tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát s V đến đỉnh cuối cùng (đích) t V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t. 77
82. Ta sẽ xem xét việc giải quyết bài toán này bằng thuật toán Dijkstra và xem xét tính chất tham lam trong thuật toán. 2) Thuật toán Dijkstra Thuật toán Dijkstra giải bài toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của một đỉnh x sẽ gồm hai thành phần và có dạng [ax, bx], trong đó thành phần ax chỉ đỉnh đi trước x trong đường đi còn thành phần bx là cận trên của độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn của các đỉnh sẽ được chỉnh dần trong một quá trình lặp. Cứ mỗi bước lặp sẽ có có một nhãn tạm thời được chọn làm nhãn cố định. Khi đỉnh x có nhãn trở thành cố định thì bx sẽ là độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn đã được cố định sẽ không tham gia sửa nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi nhãn đỉnh t được chọn làm nhãn cố định. Khi đó bt là độ dài đường đi nhắn nhất từ đỉnh s đến đỉnh t và đường đi là: s -> ->at->t. Thuật toán input: Đồ thị G = (V,E) với n đỉnh, ma trận trọng số C với c(u,u)=0, c(u,v) = , nếu (u,v) E. s V là đỉnh xuất phát, t V là đỉnh đích output: Độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh t. Dijkstra(c,s,t) { /* khởi tạo */ for x V do { bx= c[s,x]; ax=s; } U:= V\{s}; /* U là tập các đỉnh có nhãn tạm thời*/ p=s; while (p t) { p=v; //v là một đỉnh thuộc U 78