Luận văn Mô phỏng một số thuật toán trên đồ thị

Trang 3 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ Hà Nội - 2011 Trang 4 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ CHINH MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ Ngành: Công nghệ thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HỒ CẨM HÀ Hà Nội - 2011 Trang 5 LỜI CAM ĐOAN Tôi xin cam đoan, kết quả luận văn hoàn toàn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của TS. Hồ Cẩm Hà. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Học viên Nguyễn Thị Chinh Trang 6 LỜI CẢM ƠN Trước hết, tôi muốn gửi lời cảm đến các Thầy, Cô trong khoa Công nghệ thông tin- Trường Đại học Công nghệ - Đại học Quốc gia Hà nội đã truyền đạt các kiến thức quý báu cho tôi trong suốt thời gian học tập tại trường. Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới cô giáo hướng dẫn TS Hồ Cẩm Hà, người đã tận tình chỉ bảo và hướng dẫn về mặt chuyên môn cho tôi trong suốt quá trình thực hiện luận văn này. Cũng qua đây, tôi xin gửi lời cảm ơn đến Ban Giám hiệu trường THPT Chuyên Đại học Sư phạm Hà Nội, nơi tôi đang công tác đã tạo mọi điều kiện thuận lợi cho tôi trong thời gian học tập cũng như trong suốt quá trình thực hiện luận văn tốt nghiệp. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn ủng hộ, động viên tôi rất nhiều để tôi yên tâm nghiên cứu và hoàn thành luận văn. Trong suốt quá trình làm luận văn, bản thân tôi đã cố gắng tập trung tìm hiểu, nghiên cứu và tham khảo thêm nhiều tài liệu liên quan. Tuy nhiên, do thời gian hạn chế và bản thân còn chưa có nhiều kinh nghiệm trong nghiên cứu khoa học, chắc chắn bản luận văn vẫn còn nhiều thiếu sót. Tôi rất mong được nhận sự chỉ bảo của các Thầy Cô giáo và các góp ý của bạn bè, đồng nghiệp để luận văn được hoàn thiện hơn. Hà Nội, ngày 12 tháng 06 năm 2011 Nguyễn Thị Chinh Trang 7 MỤC LỤC LỜI CẢM ƠN................................................................................................... 6 LỜI NÓI ĐẦU ................................................................................................. 10 Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN .................... 12 1. Khái niệm bài toán Tin học ....................................................................... 12 2. Khái niệm thuật toán ................................................................................. 12 3. Các tính chất của thuật toán ...................................................................... 13 4. Độ phức tạp và xác định độ phức tạp của thuật toán.................................. 14 5. Chi phí thực hiện thuật toán ...................................................................... 18 6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung học Phổ thông Chuyên .................................................................................. 18 6.1. Một số khái niệm cơ bản về đồ thị ...................................................... 18 6.1.1. Khái niệm đồ thị (Graph).............................................................. 18 6.1.2. Các khái niệm cơ bản ................................................................... 19 6.2. Bài toán tìm kiếm trên đồ thị .............................................................. 21 6.2.1. Phát biểu bài toán ......................................................................... 21 6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS ................................. 22 6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS........................ 24 6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số ...................... 24 6.3.1. Phát biểu bài toán ......................................................................... 24 6.3.2. Giới thiệu thuật toán Ford - Bellman ............................................ 25 6.2.3. Giới thiệu thuật toán thuật toán Dijkstra ....................................... 26 6.3.4. Độ phức tạp .................................................................................. 28 6.4. Các thuật toán tìm kiếm trên cây khung.............................................. 28 6.4.1. Bài toán cây khung ....................................................................... 28 6.4.2. Giới thiệu thuật toán Prim ............................................................ 29 6.4.3. Giới thiệu thuật toán Kruskal........................................................ 30 6.4.5. Độ phức tạp ................................................................................. 31 Trang 8 6.5. Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị ........... 32 6.5.1. Phát biểu bài toán ......................................................................... 32 6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: ............................... 33 Chương 2 MÔ PHỎNG THUẬT TOÁN .......................................................... 34 1. Khái niệm và chức năng của mô phỏng..................................................... 34 2. Lịch sử của mô phỏng thuật toán............................................................... 35 3. Hiệu quả của mô phỏng thuật toán trong giảng dạy................................... 37 4. Một số yêu cầu đối với mô phỏng thuật toán............................................. 41 4.1. Mô phỏng đúng theo thuật toán .......................................................... 41 4.2. Cho phép thực hiện theo từng bước .................................................... 41 4.3. Mô phỏng thuật toán phải có tính động ............................................... 41 4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào ......................................... 43 4.5. Có sự phân cấp người học................................................................... 43 5. Quy trình mô phỏng thuật toán.................................................................. 43 5.1. Nghiên cứu và phân tích giải thuật...................................................... 43 5.2. Mô phỏng dữ liệu vào và kết quả đầu ra ............................................. 44 5.3. Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước .. 45 5.4. Tổng hợp mô phỏng theo các bước ..................................................... 47 5.5. Sơ đồ cấu trúc chung của hệ thống mô phỏng ..................................... 47 6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán48 6.1. Một số hệ thống mô phỏng thuật toán chung ...................................... 49 6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt ................................ 52 6.3. Xây dựng hệ thống từ đầu................................................................... 53 Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ....................................................................... 54 1. Mục đích ................................................................................................... 54 2. Những yêu cầu thực tế .............................................................................. 54 3. Đề xuất cho hệ thống mới ......................................................................... 55 4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị ......................... 56 Trang 9 4.1. Lựa chọn công cụ lập trình ................................................................. 57 4.2. Chức năng mô phỏng của các thuật toán được cài đặt ......................... 59 4.2.1 Mô phỏng thuật toán tìm kiếm....................................................... 59 4.2.2. Mô phỏng thuật toán Dijkstra ....................................................... 61 4.2.3. Mô phỏng thuật toán Ford – Bellman ........................................... 63 4.2.4. Mô phỏng thuật toán Prim ............................................................ 63 4.2.5. Mô phỏng thuật toán Kruskal ....................................................... 65 4.2.6. Thuật toán tìm chu trình Hamilton................................................ 66 5. Giới thiệu chương trình............................................................................. 66 5.1. Tổng quan về hệ thống........................................................................ 66 5.1.1. Các đối tượng xây dựng cấu trúc đồ thị ........................................ 67 5.1.2. Công cụ vẽ hình ảnh để mô phỏng................................................ 70 5.1.3.Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng 70 5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt .......... 71 Chương 4 KẾT LUẬN ..................................................................................... 80 1. Những kết quả đạt được ............................................................................ 80 2. Hướng phát triển ....................................................................................... 81 DANH MỤC TÀI LIỆU THAM KHẢO .......................................................... 82 PHỤ LỤC ........................................................................................................ 84 Trang 10 LỜI NÓI ĐẦU Cách đây gần ba thập kỉ (khoảng những năm 80 của thế kỉ XX), ở nhiều nước trên thế giới mô phỏng thuật toán đã được sử dụng trong việc giảng dạy các môn Khoa học máy tính như một công cụ hữu hiệu để mô tả thuật toán một cách trực quan, khoa học. Không những vậy nó còn cho người học biết chi tiết từng bước hoạt động của thuật toán cùng với cấu trúc dữ liệu đi kèm thông qua việc mô tả bằng đồ họa. Những năm gần đây, ở Việt Nam môn Tin học đã được đưa vào chương trình của học sinh trung học phổ thông như là một môn học chính thức. Tuy nhiên trên thực tế, một số trường chuyên trên cả nước đã tuyển sinh học sinh chuyên Tin từ cuối những năm 80 của thế kỉ XX. Những học sinh này cần nắm chắc kiến thức cơ bản về Tin học như: các cấu trúc dữ liệu trừu tượng: stack, queue, cây, cây nhị phân, cây nhị phân tìm kiếm, các chiến lược thiết kế thuật toán: tham lam, quay lui, quy hoạch động… Trong đó, lý thuyết về đồ thị và thuật toán trên đồ thị là một lĩnh vực rộng và phức tạp. Việc hiểu và cài đặt tốt các thuật toán đó đòi hỏi thời gian và công sức rất lớn. Hiện nay, việc truyền đạt các thuật toán trên đồ thị cho học sinh chuyên Tin gặp rất nhiều khó khăn. Có nhiều rất nhiều lý do: Các thuật toán đó khó hình dung, việc tổ chức dữ liệu cho nó cũng phức tạp, thời gian giảng dạy trên lớp có hạn, tài liệu tham khảo có thể tự đọc, tự học vẫn còn ít…. Trong khuôn khổ đề tài này, chúng tôi xây dựng một chương trình nhằm mô phỏng hoạt động của ba thuật toán giải ba bài toán cơ bản trên đồ thị theo phân phối chương trình của Bộ Giáo dục với hai mục đích: để học sinh có thể dễ dàng nắm bắt tư tưởng cũng như từng bước hoạt động cụ thể của các thuật toán, để giáo viên có thể làm cho bài giảng về các thuật toán này trở nên dễ hiểu, dễ tiếp thu hơn. Nội dung luận văn được chia thành 3 chương: Trang 11 Chương I. Những kiến thức cơ bản về thuật toán. Ở chương này, chúng tôi trích nêu khái niệm về bài toán và thuật toán. Các tính chất của thuật toán, xác định độ phức tạp của thuật toán…Cuối cùng, chúng tôi giới thiệu ba thuật toán quan trọng trên đồ thị mà học sinh THPT sẽ được học. Chương II. Mô phỏng thuật toán. Chương này chúng tôi trình bày khái niệm mô phỏng, các chức năng của mô phỏng và các vấn đề liên quan như: lịch sử mô phỏng, nghiên cứu về hiệu quả của nó trong giảng dạy và một số yêu cầu đối với việc mô phỏng thuật toán nói chung. Chương III. Phân tích thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị. Ở chương 3, chúng tôi trình bày về quá trình phân tích, thiết kế và xây dựng hệ thống mô phỏng trên ba thuật toán: thuật toán tìm kiếm (tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng), thuật toán tìm đường đi ngắn nhất (thuật toán Dijsktra) và thuật toán tìm cây khung cực tiểu trên đồ thị vô hướng có trọng số (thuật toán Prim)… Trang 12 Chương 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ THUẬT TOÁN 1. Khái niệm bài toán Tin học Trong phạm vi tin học, người ta quan niệm bài toán là một công việc nào đó mà con người muốn máy tính thực hiện. [xem 1] Khi dùng máy tính để giải bài toán, ta cần quan tâm tới 2 vấn đề: Dữ liệu cần được đưa vào máy tính (Input) là gì và cần lấy ra (Output) thông tin gì? Nói một cách khác, cho một bài toán là việc mô tả rõ Input và Output của bài toán. Vấn đề còn lại là: Làm thế nào để từ Input ta có được Output? 2. Khái niệm thuật toán Khác với Toán học (các yêu cầu của bài toán thường là chứng minh sự tồn tại đáp án chứ không yêu cầu tìm một cách chi tiết để tìm ra đáp án đó), giải một bài toán Tin học là việc đi tìm một lời giải cụ thể, tường minh để đưa ra Output của bài toán dựa trên Input đã cho. Việc chỉ ra một cách tìm Output của bài toán được gọi là một thuật toán. Có nhiều cách phát biểu khái niệm về thuật toán. Dưới đây là cách phát biểu được chọn để đưa vào sách giáo khoa Tin học phổ thông: Khái niệm về thuật toán: thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự nhất định để sau khi thực hiện dãy các thao tác đó, từ input ta có output cần tìm [xem 1]. Trong lĩnh vực máy tính, cụm từ “thuật toán” đôi khi người ta dùng bằng một từ khác: “giải thuật”. Ví dụ về một thuật toán: Nhập vào một số nguyên dương N, kiểm tra số đó có là số nguyên tố hay không? Lời giải: Input: Số nguyên dương N. Output: Có/không tương ứng với N có là nguyên tố hay không? Trang 13 Ý tưởng: Một số nguyên gọi là nguyên tố khi nó chỉ có ước là 1 và chính nó. Từ định nghĩa suy ra: - Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc; - Nếu 1< N < 4 thì thông báo N là số nguyên tố rồi kết thúc; - Nếu N  4 và không có ước trong khoảng từ 2 đến ][ N thì N là nguyên tố. Thuật toán: Có nhiều cách mô phỏng khác nhau. Dưới đây là cách mô phỏng thuật toán dạng liệt kê các bước: Bước 1. Nhập số nguyên dương N; Bước 2. Nếu N = 1 thì thông báo là N không nguyên tố rồi kết thúc; Bước 3. Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc; Bước 4. i  2; Bước 5. Nếu (*)][ Ni  thì thông báo N là nguyên tố rồi kết thúc; Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bước 7. i  i + 1 rồi quay lại bước 5; 3. Các tính chất của thuật toán Dựa trên khái niệm về thuật toán và ví dụ ở trên ta thấy các thao tác trong thuật toán phải được mô tả đủ chi tiết để một đối tượng cứ tiến hành thực hiện theo đúng thứ tự các thao tác đó là có thể cho ra output dựa trên input tương ứng. Một thuật toán phải đảm bảo được các tính chất sau: Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo. Trang 14 Tính đúng đắn: Sau khi thực hiện thuật toán ta phải nhận được đúng Output cần tìm. Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện. Tính tổng quát: Thuật toán là đúng đắn với mọi bộ dữ liệu đầu vào của bài toán. Tính hiệu quả: - Hiệu quả về thời gian: Ta quan tâm tới thời gian cần thiết để thực hiện xong thuật toán đó. Thời gian đó phải nằm trong giới hạn cho phép. - Hiệu quả về không gian: Dung lượng bộ nhớ cần thiết để lưu trữ các đối tượng như bộ Input, bộ Output, kết quả trung gian và chương trình được dùng để thực hiện thuật toán. - Dễ cài đặt: thuật toán đó liệu có chuyển được thành chương trình bằng một ngôn ngữ lập trình nào đó hay không. Trước khi xây dựng thuật toán cho một bài toán nào đó, trước tiên phải xác định được Input và Output là gì, thử trên một số ví dụ cụ thể để định hướng cho việc xây dựng thuật toán. [xem 1] 4. Độ phức tạp và xác định độ phức tạp của thuật toán Một thuật toán chỉ có thể giải một bài toán, nhưng một bài toán có thể giải bằng nhiều thuật toán khác nhau. Làm thế nào để lựa chọn một thuật toán tốt để giải một bài toán đã cho? Tất nhiên, người lập trình thường chọn thuật toán dễ hiểu, dễ cài đặt. Theo đó, chương trình viết ra ít có khả năng có lỗi, việc nâng cấp chương trình dễ dàng và nhiều người có thể thực hiện được. Nhưng nếu hiệu quả của thuật toán (về mặt thời gian và không gian nhớ) là yêu cầu quan trọng thì cần chọn một thuật toán chạy nhanh và sử dụng tài nguyên có sẵn một cách hiệu quả. Như vậy dựa vào đâu để có thể kết luận thuật toán này “nhanh” hơn thuật toán kia? Trang 15 Có một cách để biết được thuật toán nào nhanh hơn bằng cách viết các chương trình bằng cùng một ngôn ngữ lập trình cho các thuật toán rồi so sánh trên các bộ Input giống nhau trên cùng một hệ thống để kết luận thuật toán nào nhanh, thuật toán nào chậm. Tuy nhiên cách này không chính xác và tốn nhiều thời gian. Một cách khác để đánh giá thuật toán là dựa vào tiêu chí mỗi câu lệnh của chương trình nguồn sẽ thực hiện bao nhiêu lần trên một tập dữ liệu vào. Việc đánh giá đó không chỉ đánh giá, so sánh trong việc lựa chọn thuật toán mà còn có thể hiệu chỉnh, cải tiến thuật toán đã có tốt hơn. Khi đánh giá thời gian thực hiện thuật toán ta chú ý đặc biệt đến các phép toán mà số lần thực hiện không ít hơn các phép toán khác – ta gọi là phép toán tích cực của thuật toán. Cách đánh giá thời gian thực hiện thuật toán độc lập với hệ thống máy tính dẫn đến khái niệm về Độ phức tạp của thuật toán. Thời gian thực hiện một thuật toán bằng chương trình máy tính phụ thuộc vào rất nhiều yếu tố. Một yếu tố cần chú ý nhất đó là kích thước của dữ liệu đầu vào. Dữ liệu càng lớn thì thời gian xử lý càng chậm. Nếu gọi n là kích thước dữ liệu đưa vào thì thời gian thực hiện của một thuật toán có thể biểu diễn một cách tương đối như một hàm của n: T(n). Thực tế, T(n) không những chỉ phụ thuộc vào kích thước n mà còn phụ thuộc vào đặc tính, tình trạng thực tế của bộ dữ liệu đầu vào. Ví dụ, với thuật toán sắp xếp dãy số đã cho thành dãy tăng dần thì thời gian sắp xếp còn phụ thuộc vào dãy đầu vào đã là dãy tăng dần, dãy được sinh ngẫu nhiên hay được sắp xếp theo thứ tự ngược lại. Vì thế cần phải xem xét các trường hợp tốt nhất, trung bình và xấu nhất. [Xem 2] Việc xác định độ phức tạp của một thuật toán bất kỳ có thể rất phức tạp. Tuy nhiên, trong thực tế, đối với một số thuật toán ta có thể phân tích bằng một số quy tắc đơn giản: 4.1. Quy tắc max Trang 16 Nếu thuật toán T có thời gian thực hiện T(n) =O(f(n)+g(n)) thì có thể coi T có độ phức tạp là O(max(f(n), g(n))) 4.2. Quy tắc tổng Nếu thuật toán T gồm hai đoạn thuật toán liên tiếp T1 và T2 và nếu T1 có thời gian thực hiện T1(n) = O(f(n)), T2 có thời gian thực hiện là T2(n) = O(g(n)) thì thời gian thực hiện T sẽ là: T(n) = T1(n) + T2(n) = O(f(n)+ g(n)) 4.3. Quy tắc nhân Nếu đoạn chương trình T có thời gian thực hiện là T(n) = O(f(n)). Khi đó, nếu thực hiện k(n) lần đoạn chương trình T với k(n) = O(g(n)) thì độ phức tạp sẽ là O(g(n).f(n)) 4.4. Một số tính chất Theo định nghĩa về độ phức tạp tính toán ta có một số tính chất: a) Nếu một thuật toán có độ phức tạp là hằng số, tức là thời gian thực hiện không phụ thuộc vào kích thước dữ liệu vào thì ta ký hiệu độ phức tạp tính toán của thuật toán đó là O(1). b) Với một thuật toán có độ phức tạp cấp logarit của f(n), người ta ký hiệu là O(logf(n)) mà không cần ghi cơ số của logarit. c) Với P(n) là một đa thức bậc k thì O(P(n)) = O(nk). Vì thế, một thuật toán có độ phức tạp cấp đa thức, người ta thường ký hiệu là O(nk) d) Một thuật toán có cấp là các hàm như 2n, n!, nn được gọi là một thuật toán có độ phức tạp hàm mũ. Những thuật toán như vậy trên thực tế thường có tốc độ rất chậm. Các thuật toán có cấp là các hàm đa thức hoặc nhỏ hơn hàm đa thức thì thường nhanh hơn các thuật toán hàm mũ. Tuy nhiên, khi chọn một thuật toán để giải một bài toán thực tế phải có một sự mềm dẻo nhất định dựa vào những điều kiện thực tế cho phép. Trang 17 Dưới đây là một số hàm số hay dùng để ký hiệu độ phức tạp tính toán và bảng giá trị của chúng để tiện theo dõi sự tăng của hàm theo đối số n. Hàm N logN NlogN N2 N3 2n 1 0 0 1 1 2 2 1 2 4 8 4 4 2 8 16 64 16 8 3 24 64 512 256 16 4 64 256 409 65536 32 5 160 1024 32768 4292967296 Ví dụ: Tính giá trị của đa thức P(x)=anxn+an-1xn-1+ ... +a1x+a0 với a0, a1, ..., an, x nhập từ bàn phím. Thuật toán 1: 1.Input n, a0, a1,a2,…an, x; 2. S:=a0; 3.for i := 1 to n do begin 3.1 p:=1; 3.2 for j := 1 to i do p:= p*x; 3.3 S:= S+ai*p; End; 4. Output s; Với mỗi giá trị i của vòng lặp 3, vòng lặp 3.2 thực hiện i vòng lặp nên khi n = i nó thực hiện đủ n vòng lặp. Vậy vòng lặp 3 thực hiện 2 )1( nn lần câu lệnh sau do nên thời gian tính toán tỉ lệ thuận với n2. Vậy độ phức tạp tính toán của thuật toán trên là O(n2). Thuật toán 2: Vì xn =x * xn-1 nên có thể tận dụng kết quả của lần tính trước cho lần tính sau: Trang 18 1. Input n, a0, a1,a2,…an, x; 2. S := a0;P:=1; 3. for i := 1 to n do begin 3.1 P:=p*x; 3.1 S:= S+p; End; 4. Output S; Hai lệnh 2 và 4 đều có độ phức tạp tính toán là O(1). Vòng lặp 3 cần thực hiện n lần hai thao tác tính S và p.Vậy số lần thực hiện lệnh 3 là 2n. Do vậy, độ phức tạp tính toán của thuật toán trên là O(n). 5. Chi phí thực hiện thuật toán Khái niệm độ phức tạp tính toán đặt ra là để đánh giá chi phí thực hiện một thuật toán về mặt thời gian. Nhưng chi phí thực hiện thuật toán còn có rất nhiều yếu tố khác nữa: không gian bộ nhớ phải sử dụng là một ví dụ. Tuy nhiên, trên phương diện phân tích lý thuyết, ta chỉ có thể xét tới vấn đề thời gian bởi việc xác định các chi phí khác nhiều khi rất mơ hồ và phức tạp. Đối với người lập trình thì khác, một thuật toán với độ phức tạp dù rất thấp cũng sẽ là vô dụng nếu như không thể cài đặt được trên máy tính, chính vì vậy khi bắt tay cài đặt một thuật toán, ta phải biết cách tổ chức dữ liệu một cách khoa học, tránh lãng phí bộ nhớ không cần thiết. Có một quy luật tương đối khi tổ chức dữ liệu: Tiết kiệm được bộ nhớ thì thời gian thực hiện thường sẽ chậm hơn và ngược lại. Biết cân đối, dung hoà hai yếu tố đó là một kỹ năng cần thiết của người lập trình. [Xem 2] 6. Ba bài toán trên mô hình đồ thị được đưa vào giảng dạy trong trường Trung học Phổ thông Chuyên 6.1. Một số khái niệm cơ bản về đồ thị 6.1.1. Khái niệm đồ thị (Graph) Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E). Trong đó: Trang 19 V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V. Một số hình ảnh của đồ thị: Đồ thị vô hướng Đồ thị có hướng 6.1.2. Các khái niệm cơ bản Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Ta có một số khái niệm sau [xem 3- tập 1]: Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. Đa đồ thị: G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v. Đồ thị vô hướng: G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v)  (v, u) Đồ thị có hướng: G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v)  (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô Trang 20 hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u). Ví dụ: Vô hướng Có hướng Vô hướng Có hướng Đơn đồ thị Đa đồ thị Cạnh liên thuộc, đỉnh kề, bậc Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e  E, nếu e = (u, v) thì ta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident) với đỉnh u và đỉnh v. Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì số cạnh liên thuộc với v cũng là số đỉnh kề với v. Đối với đồ thị có hướng G = (V, E). Xét một cung e  E, nếu e = (u, v) thì ta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e. Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: Bán bậc ra của v ký hiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số cung đi vào đỉnh đó 1 2 3 4 5 Trang 21 Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u = x0, x1, ..., xk = v) thoả mãn (xi, xi+1)  E (là 1 cạnh của đồ thị) với i: (0  i  k). Đỉnh u gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không có cạnh nào đi qua hơn 1 lần gọi là đường đi đơn. Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu trình. tương tự ta có khái niệm chu trình đơn. 6.2. Bài toán tìm kiếm trên đồ thị 6.2.1. Phát biểu bài toán Cho đồ thị G = (V, E) và s và t là hai đỉnh của đồ thị. Yêu cầu: Hãy chỉ ra một đường đi từ s đến t (nếu có). Ví dụ: Xét một đồ thị vô hướng và một đồ thị có hướng dưới đây: Trên cả hai đồ thị, (1, 2, 3, 4) là đường đi đơn độ dài 3 từ đỉnh 1 tới đỉnh 4. Bởi (1, 2) (2, 3) và (3, 4) đều là các cạnh (hay cung. Làm sao để duyệt tất cả các đỉnh có thể đến được từ một đỉnh xuất phát nào đó? Vấn đề này đưa về một bài toán liệt kê mà yêu cầu của nó là không được bỏ sót hay lặp lại bất kỳ đỉnh nào. Vì vậy, cần phải xây dựng những thuật toán cho phép duyệt một cách hệ thống các đỉnh, những thuật toán như vậy gọi là những thuật toán tìm kiếm trên đồ thị. Trong lý thuyết đồ thị, người ta quan Trang 22 tâm đến hai thuật toán cơ bản nhất: thuật toán tìm kiếm theo chiều sâu và thuật toán tìm kiếm theo chiều rộng. 6.2.2. Giới thiệu thuật toán tìm kiếm DFS và BFS a. Thuật toán tìm kiếm theo chiều sâu DFS (Depth – First – Search) Tư tưởng của thuật toán có thể trình bày như sau: Bắt đầu từ s, mọi đỉnh u kề với s tất nhiên sẽ đến được từ s. Với mỗi đỉnh u đó, những đỉnh v kề với u cũng đến được từ s... Ý tưởng đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u. Để quá trình duyệt không lặp lại bất kì đỉnh nào, ta dùng kỹ thuật đánh dấu, khi thăm một đỉnh, ta sẽ đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không thăm lại đỉnh đó nữa. Vấn đề còn lại: Để in ra được đường đi từ đỉnh xuất phát s, trong quá trình duyệt DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại “vết” đường đi từ u tới v bằng cách đặt trace[v] := u, tức là trace[v] là đỉnh liền trước v trong đường đi từ s tới v. Khi quá trình tìm kiếm theo chiều sâu kết thúc, đường đi từ S tới F sẽ là: t  Trace[t]  …. Trace[u1] ... Trace[s]  s. Truy ngược đường đi này sẽ cho ta hành trình đi từ s đến t. Có thể mô tả thủ tục DFS dạng giả mã như sau: Procedure DFS(uV); Begin ; ; ; Begin Trace[v] := u; {Truy vết đường đi} DFS(v); {Gọi đệ quy duyệt bắt đầu với v} Trang 23 End; End; Begin ; ; DFS(s); <Output: - Nếu t chưa bị đánh dấu thì kết luận: Không có đường từ s->t>; - Nếu t đã bị đánh dấu thì dựa vào Trace tìm đường đi từ s->t>; >; End. b. Thuật toán tìm kiếm theo chiều rộng BFS (Breadth – First – Search) Ý tưởng của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Khi thăm một đỉnh ta sẽ lên lịch thăm tất cả các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần s hơn sẽ được duyệt trước). Ví dụ: Bắt đầu, ta thăm đỉnh s. Quá trình thăm S sẽ lên lịch duyệt những đỉnh (u1, u2, ..., up) kề với s (những đỉnh gần s nhất). Tiếp theo sẽ thăm đỉnh u1, khi thăm u1 sẽ lại lên lịch duyệt những đỉnh (v1, v2 ..., vq) kề với u1. Nhưng rõ ràng các đỉnh này "xa" s hơn những đỉnh u nên chúng chỉ được duyệt đến khi tất cả những đỉnh u đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm u1 sẽ là: (u2, u3..., up, v1, v2, ..., vq). Do việc lập lịch như mô tả ở trên nên cần phải xếp hàng cho các đỉnh đã lên lịch theo đúng thứ tự. Khi thêm đỉnh nào đó ta sẽ thêm vào cuối hàng (vì đỉnh lên lịch sau chắc chắn xa hơn các đỉnh đã lên lịch (vào hàng) rồi. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi (Queue). Ta sẽ dựng giải thuật như sau: Bước 1: Khởi tạo: free[s] = true; free[v] = false v V\{s} First:=1; Last:=1; Queue[Last]:=s;//Queue chỉ chứa s Trang 24 Bước 2: Lặp cho tới khi Queue rỗng: u := pop;//lấy u khỏi hàng đợi free[u]:= false; Xét v V: nếu v chưa được thăm: Free[v] = false;//đánh dấu đã thăm Trace[v] = u; Push(v);//đẩy v vào hàng đợi, chờ được thăm Bước 3: Truy vết tìm đường đi hoặc thông báo không thấy đường. 6.2.3. Độ phức tạp tính toán của thuật toán DFS và BFS Quá trình tìm kiếm trên đồ thị bắt đầu từ một đỉnh có thể thăm tất cả các đỉnh còn lại, khi đó cách biểu diễn đồ thị [xem 3 – tập 1] có ảnh hưởng lớn tới chi phí về thời gian thực hiện giải thuật: Trong trường hợp ta biểu diễn đồ thị bằng danh sách kề, cả hai thuật toán BFS và DFS đều có độ phức tạp tính toán là O(n + m) = O(max(n, m)). Đây là cách cài đặt tốt nhất. Nếu ta biểu diễn đồ thị bằng ma trận kề thì độ phức tạp tính toán trong trường hợp này là O(n + n2) = O(n2). Nếu ta biểu diễn đồ thị bằng danh sách cạnh, thao tác duyệt những đỉnh kề với đỉnh u sẽ dẫn tới việc phải duyệt qua toàn bộ danh sách cạnh, đây là cài đặt tồi nhất, nó có độ phức tạp tính toán là O(n.m). 6.3. Bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số 6.3.1. Phát biểu bài toán Khái niệm đồ thị có trọng số: Đồ thị có trọng số là một bộ ba G = (V, E, w) trong đó, G = (V, E) là đồ thị, w là hàm được định nghĩa: )( : ewe REw   Bài toán đó phát biểu dưới dạng tổng quát như sau: Cho đồ thị có trọng số G = (V, E,w) là đồ thị không có chu trình âm. Trang 25 Yêu cầu: Hãy tìm một đường đi ngắn nhất (tổng trọng số qua các đỉnh trên đường đi) từ đỉnh xuất phát s  V đến đỉnh đích t  V. Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào. Trong trường hợp như vậy, có thể đặt vấn đề tìm đường đi cơ bản (đường đi không có đỉnh lặp lại) ngắn nhất. Vấn đề đó là một vấn đề hết sức phức tạp mà ta sẽ không bàn tới ở đây. Dưới đây, chúng tôi giới thiệu hai thuật toán giải bài toán này là thuật toán Ford – Bellman và thuật toán Dijkstra. 6.3.2. Giới thiệu thuật toán Ford - Bellman Thuật toán Ford-Bellman có thể phát biểu rất đơn giản: Với đỉnh xuất phát S. Gọi d(v) là khoảng cách từ S tới v. Ban đầu d(S) được khởi gán bằng 0 còn các d(v) với v  S được khởi gán bằng +. Sau đó ta tối ưu hoá dần các d(v) như sau: Xét mọi cặp đỉnh u, v của đồ thị, nếu có một cặp đỉnh u, v mà d(v) > d(u) + c(u, v) thì ta đặt lại d(v) := d(u) + c(u, v). Tức là nếu độ dài đường đi từ S tới v lại lớn hơn tổng độ dài đường đi từ S tới u cộng với chi phí đi từ u tới v thì ta sẽ huỷ bỏ đường đi từ S tới v đang có và coi đường đi từ S tới v chính là đường đi từ S tới u sau đó đi tiếp từ u tới v. Chú ý rằng ta đặt c[u, v] = + nếu (u, v) không là cung. Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kỳ một nhãn d[v] nào nữa. Tính dừng của thuật toán: Tại bước lặp 0: Bước khởi tạo d(S) = 0; d(v) := + với v  S: thì dãy d(v) chính là độ dài đường đi ngắn nhất từ S tới v đi qua không quá 0 cạnh Trang 26 Giả sử tại bước lặp thứ i, d(v) bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh, thì do tính chất: đường đi từ S tới v qua không quá i + 1 cạnh sẽ phải thành lập bằng cách: lấy một đường đi từ S tới một đỉnh u nào đó qua không quá i cạnh, rồi đi tiếp tới v bằng cung (u, v). Nên độ dài đường đi ngắn nhất từ S tới v qua không quá i + 1 cạnh sẽ được tính bằng giá trị nhỏ nhất trong các giá trị: (Nguyên lý tối ưu Bellman) Độ dài đường đi ngắn nhất từ S tới v qua không quá i cạnh Độ dài đường đi ngắn nhất từ S tới u qua không quá i cạnh cộng với trọng số cạnh (u, v) (u) Nên sau bước lặp tối ưu các d(v) bằng công thức d(v)bước i+1 = min(d(v)bước i, d(u)bước i+ c(u, v)) thì các d(v) sẽ bằng độ dài đường đi ngắn nhất từ S tới v qua không quá i + 1 cạnh. Sau bước lặp tối ưu thứ n - 1, ta có d(v) = độ dài đường đi ngắn nhất từ S tới v qua không quá n - 1 cạnh. Vì đồ thị không có chu trình âm nên sẽ có một đường đi ngắn nhất từ S tới v là đường đi cơ bản (qua không quá n - 1 cạnh). Tức là d(v) sẽ là độ dài đường đi ngắn nhất từ S tới v. Vậy thì số bước lặp tối ưu hoá sẽ không quá n - 1 bước. Nếu mỗi bước ta mô tả dưới dạng: for u := 1 to n do for v := 1 to n do d(v) := min(d(v), d(u) + c(u, v)); Thì do sự tối ưu bắc cầu (dùng d(u) tối ưu d(v) rồi lại có thể dùng d(v) tối ưu d(w) nữa...) nên chỉ làm tốc độ tối ưu nhãn d(v) tăng nhanh lên chứ không thể giảm đi được. 6.2.3. Giới thiệu thuật toán thuật toán Dijkstra Thuật toán Dijkstra (E.Dijkstra - 1959) có thể mô tả như sau: Trang 27 Bước 1: Khởi tạo Với đỉnh v  V, gọi nhãn d[v] là độ dài đường đi ngắn nhất từ s tới v. Ta sẽ tính các d[v]. Ban đầu d[v] được khởi gán bằng w[s, v]. Nhãn của mỗi đỉnh có hai trạng thái tự do hay cố định, nhãn tự do có nghĩa là có thể còn tối ưu hơn được nữa và nhãn cố định tức là d[v] đã bằng độ dài đường đi ngắn nhất từ s tới v nên không thể tối ưu thêm. Để làm điều này ta có thể sử dụng kỹ thuật đánh dấu: Free[v] = TRUE hay FALSE tuỳ theo d[v] tự do hay cố định. Ban đầu các nhãn đều tự do. Bước 2: Lặp Cố định nhãn: Chọn trong các đỉnh có nhãn tự do, lấy ra đỉnh u là đỉnh có d[u] nhỏ nhất, và cố định nhãn đỉnh u. Sửa nhãn: Dùng đỉnh u, xét tất cả những đỉnh v và sửa lại các d[v] theo công thức: d[v] := min(d[v], d[u] + c[u, v]) Bước lặp sẽ kết thúc khi mà đỉnh đích t được cố định nhãn (tìm được đường đi ngắn nhất từ s đến t); hoặc tại thao tác cố định nhãn, tất cả các đỉnh tự do đều có nhãn là + (không tồn tại đường đi). Có thể đặt câu hỏi, ở thao tác 1, tại sao đỉnh u như vậy được cố định nhãn, giả sử d[u] còn có thể tối ưu thêm được nữa thì tất phải có một đỉnh t mang nhãn tự do sao cho d[u] > d[t] + c[t, u]. Do trọng số c[t, u] không âm nên d[u] > d[t], trái với cách chọn d[u] là nhỏ nhất. Tất nhiên trong lần lặp đầu tiên thì S là đỉnh được cố định nhãn do d[s] = 0. Bước 3: Kết hợp với việc lưu vết đường đi trên từng bước sửa nhãn, thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (d[t] = +). Có thể mô tả ngắn gọn thuật toán bằng giả mã như sau: Bước 1: d[s] = 0 ; d[v] = + (v  V\{s}); u = s; Trang 28 Bước 2: Lặp nếu u  t (với u  S) 2.1. Nếu d[v] > d[u] + c[u,v] thì d[v] = min{d[v], d[u] + c[u, v]} trace[v]=u (với v  S - tập các đỉnh đã tối ưu) 2.2 Chọn v có d[v] nhỏ nhất //v=0 không có đường 2.3 Nếu v  0 thì thêm v vào S; u = v Bước 3: In ra đường đi tối ưu từ s đến t hoặc thông báo vô nghiệm. 6.3.4. Độ phức tạp Nếu đồ thị có nhiều đỉnh, ít cạnh, ta có thể sử dụng danh sách kề kèm trọng số để biểu diễn đồ thị, tuy nhiên tốc độ của thuật toán Dijkstra vẫn khá chậm vì trong trường hợp xấu nhất, nó cần n lần cố định nhãn và mỗi lần tìm đỉnh để cố định nhãn sẽ mất một đoạn chương trình với độ phức tạp O(n). Vậy độ phức tạp của thuật toán Dijkstra là O(n2). Để tăng tốc độ, người ta thường sử dụng cấu trúc dữ liệu Heap để lưu các đỉnh chưa cố định nhãn. Heap ở đây là một cây nhị phân hoàn chỉnh thoả mãn: Nếu u là đỉnh lưu ở nút cha và v là đỉnh lưu ở nút con thì d[u]  d[v] (Đỉnh r lưu ở gốc Heap là đỉnh có d[r] nhỏ nhất). 6.4. Các thuật toán tìm kiếm trên cây khung 6.4.1. Bài toán cây khung Khái niệm cây khung: Cho đồ thị G = (V, E) vô hướng, liên thông và T = (V,E’) là một đồ thị con của G (E’  E). Khi đó, T được gọi là cây khung (cây bao trùm) nếu T liên thông và không có chu trình đơn Cho G = (V, E, w) là đồ thị vô hướng liên thông có trọng số, với một cây khung T của G, ta gọi trọng số của cây T là tổng trọng số các cạnh trong T. Yêu cầu: Trong số các cây khung của G, chỉ ra cây khung có trọng số nhỏ nhất. Trang 29 Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị, và bài toán đó gọi là bài toán xây dựng cây khung nhỏ nhất. Dưới đây ta sẽ xét một trong hai thuật toán thông dụng để giải bài toán cây khung nhỏ nhất của đơn đồ thị vô hướng có trọng số. 6.4.2. Giới thiệu thuật toán Prim Một trong hai thuật toán quan trọng để giải bài toán tìm cây khung nhỏ nhất là thuật toán Prim. Thuật toán đó có thể phát biểu hình thức như sau: Đơn đồ thị vô hướng G = (V, E,w). Xét cây T trong G và một đỉnh v, gọi khoảng cách từ v tới T là trọng số nhỏ nhất trong số các cạnh nối v với một đỉnh nào đó trong T: d[v] = min{w[u, v]  uT} Ban đầu khởi tạo cây T chỉ gồm có mỗi đỉnh {1}. Sau đó cứ chọn trong số các đỉnh ngoài T ra một đỉnh gần T nhất, kết nạp đỉnh đó vào T đồng thời kết nạp luôn cả cạnh tạo ra khoảng cách gần nhất đó. Cứ làm như vậy cho tới khi: Hoặc đã kết nạp được tất cả n đỉnh thì ta có T là cây khung nhỏ nhất Hoặc chưa kết nạp được hết n đỉnh nhưng mọi đỉnh ngoài T đều có khoảng cách tới T là +. Khi đó đồ thị đã cho không liên thông, ta thông báo việc tìm cây khung thất bại. Về mặt kỹ thuật cài đặt, ta có thể làm như sau: Sử dụng mảng đánh dấu Free. Free[v] = TRUE nếu như đỉnh v chưa bị kết nạp vào T. Gọi d[v] là khoảng cách từ v tới T. Ban đầu khởi tạo d[1] = 0 còn d[2] = d[3] = ... = d[n] = +. Tại mỗi bước chọn đỉnh đưa vào T, ta sẽ chọn đỉnh u nào ngoài T và có d[u] nhỏ nhất. Khi kết nạp u vào T rồi thì rõ ràng các nhãn d[v] sẽ thay đổi: d[v]mới := min(d[v]cũ, v[u, v]). Vấn đề chỉ có vậy (chương trình rất giống thuật toán Dijkstra, chỉ khác ở công thức tối ưu nhãn). Trang 30 Có thể mô tả thuật toán Prim bằng đoạn giả mã sau: Bước 1: Khởi tạo: T = {s} d[s] = 0, u = s (s - đỉnh xuất phát) d[v]=+∞(v ∉ T) Bước 2: Lặp N-1 lần (N số đỉnh của đồ thị): 2.1 Cập nhật các đỉnh kề với u ở ngoài T Nếu d[v] > w[u,v] trace[v] = u, d[v] = w[u,v] 2.2 Chọn v (v ∉ T) mà d[v] nhỏ nhất Nếu d[v] = +∞ đến bước 3 2.3 Kết nạp v vào T, u = v Bước 3: In ra cây khung hoặc thông báo vô nghiệm. 6.4.3. Giới thiệu thuật toán Kruskal Thuật toán Kruskal dựa trên mô hình xây dựng cây khung bằng thuật toán hợp nhất [xxx], chỉ có điều thuật toán không phải xét các cạnh với thứ tự tuỳ ý mà xét các cạnh theo thứ tự đã sắp xếp: Với đồ thị vô hướng G = (V, E) có n đỉnh. Khởi tạo cây T ban đầu không có cạnh nào. Xét tất cả các cạnh của đồ thị từ cạnh có trọng số nhỏ đến cạnh có trọng số lớn, nếu việc thêm cạnh đó vào T không tạo thành chu trình đơn trong T thì kết nạp thêm cạnh đó vào T. Cứ làm như vậy cho tới khi: Hoặc đã kết nạp được n - 1 cạnh vào trong T thì ta được T là cây khung nhỏ nhất Hoặc chưa kết nạp đủ n - 1 cạnh nhưng hễ cứ kết nạp thêm một cạnh bất kỳ trong số các cạnh còn lại thì sẽ tạo thành chu trình đơn. Trong trường hợp này đồ thị G là không liên thông, việc tìm kiếm cây khung thất bại. Như vậy có hai vấn đề quan trọng khi cài đặt thuật toán Kruskal: Thứ nhất, làm thế nào để xét được các cạnh từ cạnh có trọng số nhỏ tới cạnh có trọng số lớn. Ta có thể thực hiện bằng cách sắp xếp danh sách cạnh theo thứ tự không giảm của trọng số, sau đó duyệt từ đầu tới cuối danh sách cạnh. Trang 31 Nên sử dụng các thuật toán sắp xếp hiệu quả để đạt được tốc độ nhanh trong trường hợp số cạnh lớn. Trong trường hợp tổng quát, thuật toán HeapSort là hiệu quả nhất bởi nó cho phép chọn lần lượt các cạnh từ cạnh trọng nhỏ nhất tới cạnh trọng số lớn nhất ra khỏi Heap và có thể xử lý (bỏ qua hay thêm vào cây) luôn. Thứ hai, làm thế nào kiểm tra xem việc thêm một cạnh có tạo thành chu trình đơn trong T hay không. Để ý rằng các cạnh trong T ở các bước sẽ tạo thành một rừng (đồ thị không có chu trình đơn). Muốn thêm một cạnh (u, v) vào T mà không tạo thành chu trình đơn thì (u, v) phải nối hai cây khác nhau của rừng T, bởi nếu u, v thuộc cùng một cây thì sẽ tạo thành chu trình đơn trong cây đó. Ban đầu, ta khởi tạo rừng T gồm n cây, mỗi cây chỉ gồm đúng một đỉnh, sau đó, mỗi khi xét đến cạnh nối hai cây khác nhau của rừng T thì ta kết nạp cạnh đó vào T, đồng thời hợp nhất hai cây đó lại thành một cây. 6.4.5. Độ phức tạp Xét về độ phức tạp tính toán, thuật toán Prim có độ phức tạp là O(n2). Tương tự thuật toán Dijkstra, nếu kết hợp thuật toán Prim với cấu trúc Heap sẽ được một thuật toán với độ phức tạp O((m+n)logn). Đối với thuật toán Kruskal, ta có thể chứng minh được rằng thao tác GetRoot có độ phức tạp là O(log2n), còn thao tác Union là O(1). Giả sử ta đã có danh sách cạnh đã sắp xếp rồi thì xét vòng lặp dựng cây khung, nó duyệt qua danh sách cạnh và với mỗi cạnh nó gọi 2 lần thao tác GetRoot, vậy thì độ phức tạp là O(mlog2n), nếu đồ thị có cây khung thì m  n-1 nên ta thấy chi phí thời gian chủ yếu sẽ nằm ở thao tác sắp xếp danh sách cạnh bởi độ phức tạp của HeapSort là O(mlog2m). Vậy độ phức tạp tính toán của thuật toán là O(mlog2m) trong trường hợp xấu nhất. Tuy nhiên, phải lưu ý rằng để xây dựng cây khung thì ít khi thuật toán phải duyệt toàn bộ danh sách cạnh mà chỉ một phần của danh sách cạnh mà thôi. Trang 32 6.5.Bài toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị 6.5.1. Phát biểu bài toán Khái niệm chu trình Hamilton: Cho đồ thị G = (V, E) có n đỉnh Chu trình (x1, x2, ..., xn, x1) được gọi là chu trình Hamilton nếu xi  xj với 1  i < j  n Đường đi (x1, x2, ..., xn) được gọi là đường đi Hamilton nếu xi  xj với 1  i < j  n Có thể phát biểu một cách hình thức: Chu trình Hamilton là chu trình xuất phát từ 1 đỉnh, đi thăm tất cả những đỉnh còn lại mỗi đỉnh đúng 1 lần, cuối cùng quay trở lại đỉnh xuất phát. Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Bài toán tìm chu trình Hamilton: Cho đồ thị G = (V, E) có n đỉnh, m cạnh. Yêu cầu: Hãy chỉ ra một chu trình Hamilton của đồ thị đã cho. Để tìm chu trình Hamilton, ta quan tâm đến các định lý sau: Định lý 1: Đồ thị vô hướng G, trong đó tồn tại k đỉnh sao cho nếu xoá đi k đỉnh này cùng với những cạnh liên thuộc của chúng thì đồ thị nhận được sẽ có nhiều hơn k thành phần liên thông. Thì khẳng định là G không có chu trình Hamilton. Mệnh đề phản đảo của định lý này cho ta điều kiện cần để một đồ thị có chu trình Hamilton Định lý 2 (Định lý Dirac (1952)): Đồ thị vô hướng G có n đỉnh (n  3). Khi đó nếu mọi đỉnh v của G đều có deg(v)  n/2 thì G có chu trình Hamilton. Đây là một điều kiện đủ để một đồ thị có chu trình Hamilton Định lý 3: Đồ thị có hướng G liên thông mạnh và có n đỉnh. Nếu 2 )(deg nv  và 2 )(deg nv  với mọi đỉnh v thì G có chu trình Hamilton Trang 33 6.5.2. Giới thiệu thuật toán tìm chu trình Hamilton: Dưới đây ta sẽ cài đặt một chương trình liệt kê tất cả các chu trình Hamilton xuất phát từ đỉnh 1, các chu trình Hamilton khác có thể có được bằng cách hoán vị vòng quanh. Lưu ý rằng cho tới nay, người ta vẫn chưa tìm ra một phương pháp nào thực sự hiệu quả hơn phương pháp quay lui để tìm dù chỉ một chu trình Hamilton cũng như đường đi Hamilton trong trường hợp đồ thị tổng quát. Bước 1. Khởi tạo: free[u] = true với u thuộc G Bước 2. Visit(i): Thăm đỉnh ở bước thứ i 2.1 u = đỉnh vừa thăm xong Xét các đỉnh v kề u và free[v] = true 2.2 Ghi nhận đỉnh ở bước thứ i 2.3 Nếu (i =n) và (u kề với 1) đến Bước 3 2.4 Đánh dấu thăm v và Vitsit(i+1); Bước 3. Truy vết tìm đường đi (nếu có) Trang 34 Chương 2 MÔ PHỎNG THUẬT TOÁN 1. Khái niệm và chức năng của mô phỏng Mô phỏng thuật toán là quá trình mô tả cấu trúc dữ liệu, các thao tác của một chương trình bằng đồ hoạ [Stasko 1990]. Mô phỏng thuật toán được thiết kế nhằm giúp người dùng hiểu thuật toán, đánh giá thuật toán và gỡ lỗi khi cài đặt chương trình [xem 12] Một chương trình lập trình trên máy tính sẽ chứa các cấu trúc dữ liệu của thuật toán mà nó sẽ thực hiện. Trong khi thực hiện chương trình đó, giá trị thực của cấu trúc dữ liệu thay đổi dựa trên từng bước hoạt động của thuật toán. Mô phỏng thuật toán sử dụng đồ hoạ để biểu diễn sự thay đổi trạng thái của cấu trúc dữ liệu cho từng bước hoạt động của nó một cách trực quan, khoa học. Trong suốt quá trình biểu diễn, người dùng có thể quan sát việc thực thi thuật toán theo từng bước để có thể biết chi tiết về thuật toán cũng như hiểu một cách tường tận về thuật toán đó. Ví dụ: Một chương trình mô phỏng thuật toán phân tích LR phân tích trên 1 chuỗi kí tự. Chương trình chứa ba cấu trúc: bảng chuyển, một ngăn xếp (stack) và 1 xâu kí tự. Khi thực hiện, chương trình minh hoạ bằng việc đối sánh các trạng thái trong bảng chuyển và và thực hiện từng thao tác trên ngăn xếp để tách xâu kí tự. Các chỉ dẫn, kí hiệu trên xâu vào và các phần tử trong ngăn xếp ở mỗi trạng thái sẽ lần lượt thay đổi trong khi thực hiện thuật toán. Đây là một công việc khá khó khăn để nắm bắt nếu một học sinh chỉ sử dụng hình vẽ và các xâu kí tự. Mô phỏng thuật toán có thể chỉ ra tất cả các thông tin và sự thay đổi đồng thời ở từng bước bằng đồ hoạ. Ta có thể quan sát bằng hình vẽ dưới đây: Trang 35 Hình. 1 Mô phỏng một bước hoạt động của thuật toán Bên cạnh việc giúp người dùng hiểu rõ thuật toán, mô phỏng thuật toán cũng có thể dùng để gỡ lỗi chương trình một cách dễ dàng hơn. Để sử dụng mô phỏng thuật toán trong việc gỡ lỗi, người dùng ghi chú các trạng thái thực trên chương trình của họ để đưa ra các lệnh mô phỏng đầu ra và những bước làm cho thuật toán không cho ra kết quả như mong muốn. 2. Lịch sử của mô phỏng thuật toán Năm 1981 Ronald Baecker tại đại học Toronto đã thiết kế đoạn video “Sorting Out Sorting”. Đây là mốc đánh dấu sự phát triển của lĩnh vực mô phỏng. Từ đó, các giảng viên đã sử dụng hệ thống mô phỏng để giảng dạy các môn thuật toán. Từ những năm 1980 đến đầu những năm 90 của thế kỉ XX, có 2 hệ thống được phát triển đã gây ảnh hưởng đến tất cả những hệ thống về sau đó là BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition-based Animation GeneratiOn) [Stasko 1990]. BALSA – I là hệ thống mô phỏng thuật toán nổi tiếng được biết đến đầu tiên, được viết bởi giáo sư Marc Brown và Robert Sedgewick (Đại học Brown – Mỹ). BALSA – I là chương trình mô phỏng thuật toán tương tác. Nó đưa ra Trang 36 nhiều khung nhìn về cấu trúc dữ liệu và có thể thực hiện nhiều thuật toán một cách đồng thời. Sự phát triển của nó là động lực thúc đẩy các nghiên cứu khác trong lĩnh vực này. Một hệ thống khác, TANGO, do John Stasko (Đại học Brown – Mỹ) viết vào đầu những năm 90. Điểm nổi bật của hệ thống này là giới thiệu mô hình chuyển cho thiết kế mô phỏng và framework cho hệ thống mô phỏng thuật toán. Nó giới thiệu một khái niệm mới về framework (sau này có rất nhiều hệ thống sử dụng nó như một cấu trúc cơ bản) Từ khi hai hệ thống này được công bố, các hệ thống con của nó cũng được phát triển. BALSA – II (1988). TANGO có rất nhiều phiên bản. Một trong số đó là XTANGO và POLKA. POLKA được thiết kế cho các thuật toán chạy song song. Nó là hệ thống mô phỏng thuật toán 2D hướng đối tượng và mở rộng trong 3D, POLKA 3D. POLKA 3D cung cấp cách nhìn 3D và các cơ sở như góc, hình cầu, hình khối…. Người dùng không yêu cầu phải biết kiến thức về đồ họa 3D để sử dụng POLKA 3D. SAMBA là hệ thống mô phỏng tương tác thông dịch, nó đọc các lệnh ASCII và thực hiện các thao tác mô phỏng tương ứng. Phiên bản của SAMBA cài bằng Java và có thể xem chi tiết tại trang web Một số hệ thống mô phỏng nổi tiếng khác là Zeus, Leonardo, CATAI, Mocha. Zeus (Brown 1991) được phát triển tại đại học Brown cùng với hệ thống BALSA và BALSA – II. Nó được coi là phần mềm tương tác trực quan hóa. Nó hỗ trợ việc đồng bộ các khung nhìn và cho phép người dung chỉnh sửa các khung nhìn này và thay đổi biểu diễn của dữ liệu. Zeus được thực thi trong môi trường đa xử lý và đa tuyến, nó cũng cho phép thực thi các thuật toán song song. Leonardo là hệ thống mô phỏng các chương trình C. Nó tích hợp phát triển với mô phỏng của các chương trình C vào cùng một môi trường. CATAI mô phỏng các chương trình C++. Nó dựa trên kĩ thuật đối tượng phân phối và cho phép nhiều người dùng chia sẻ cùng một mô phỏng thông qua “lớp” ảo. Việc giao tiếp Trang 37 và đồng bộ giữa các trạm và thuật toán được mô phỏng được đảm bảo bởi server có sử dụng kĩ thuật CORBA. Mocha là mô hình phân phối với kiến trúc client – server, nó phân đoạn một cách tối ưu các thành phần của hệ thống mô phỏng thông thường. Nó vượt qua các tồn tại của X - window và mô hình Java. Trong mô hình Mocha chỉ có mã giao diện được xuất tới máy của người dùng. Khi thuật toán chay trên server thì đoạn mã giao diện lại chạy trên máy người dùng. Hiện tại, một số lượng lớn các chương trình mô phỏng đã được viết ra. Hầu hết trong số chúng rất phổ biến và sử dụng phức tạp. Các phần mềm này được thiết kế nhằm mục đích giáo dục hoặc các nghiên cứu. Một vài chương trình có cấu trúc phức tạp và yêu cầu hỗ trợ kĩ thuật cao. Rõ ràng, điều này ít thực tế, chúng ta mong muốn một phần mềm nhỏ gọn và linh hoạt, có cấu trúc đơn giản. 3. Hiệu quả của mô phỏng thuật toán trong giảng dạy Trên thế giới, hệ thống mô phỏng đã được sử dụng rộng rãi trong việc dạy học ngành khoa học máy tính. Đã có một số lượng các sinh viên được đào tạo bằng các chương trình mô phỏng để thấy được hiệu quả của nó trong giảng dạy nhưng kết quả rất khác nhau. Có thể đưa ra một vài ví dụ như sau: Giáo sư Brown (Đại học Brown) năm 1984 đã sử dụng phần mềm BALSA – I để dạy môn học lập trình và môn cấu trúc dữ liệu và giải thuật. Hệ thống này sử dụng để trực quan hóa chương trình dạy học. Ông viết trong bản báo cáo rằng việc sử dụng các đoạn mô phỏng kèm vào các bài giảng là một chứng minh cho việc “tốc độ hiểu bài của học sinh tăng lên” so với cách giảng dạy truyền thống. Stasko (Đại học Brown) năm 1997 sử dụng SAMBA – chương trình mô phỏng của hệ thống XTANGO để dạy môn thuật toán. Ông yêu cầu các sinh viên sử dụng hệ thống để thêm vào các mô phỏng của chính bài tập của mình. Kết quả chỉ ra rằng sinh viên rất có hứng thú với các chương trình mô phỏng và Trang 38 chính chương trình mô phỏng đã khuyến khích sự sáng tạo của học sinh. Rõ ràng, nhờ có chương trình mô phỏng mà các sinh viên hiểu các thuật toán nhanh hơn, nhớ được lâu hơn. Tuy nhiên, việc sử dụng chương trình mô phỏng trong dạy học không phải lúc nào cũng đem lại kết quả tốt. Stasko (1993) đã thử nghiệm dạy 2 nhóm sinh viên với cùng một nội dung bài học về HEAP – một dạng cấu trúc dữ liệu trừu tượng. Một nhóm học thuật toán dựa trên mô tả một cách khái niệm. Nhóm còn lại học bài dựa trên chương trình mô phỏng tương tác. Mặc dù kết quả cho thấy nhóm được học có mô phỏng điểm cao hơn nhóm còn lại nhưng sự chênh lệch không đủ để thấy được lợi ích của việc mô phỏng. Tương tự, Byrne (1996) cũng làm 2 thí nghiệm tương tự và kết quả thu được cũng không chỉ rõ được lợi ích của việc mô phỏng. Mặc dầu vậy, những kết quả đó không làm cho việc mô phỏng thuật toán mất đi những điểm mạnh của nó mà nó hướng người dùng đến một cách nhìn khác về thuật toán mô phỏng. Kết quả chỉ ra rằng để đạt được hiệu quả tối ưu khi dùng thuật toán mô phỏng là dùng nó như một cầu nối với các nhân tố khác. Lawrence đã sử dụng hệ thống XTANGO và POLKA để giảng dạy về thuật toán Kruskal. Tất cả sinh viên của nhóm học có mô phỏng có tác động rõ rệt. Thực nghiệm cũng cho thấy rằng để người học tiếp thu nhanh hơn thì nên để cho họ tự học và tự tạo cho mình tập dữ liệu hơn là các dữ liệu do giáo viên tự chuẩn bị từ trước. Hơn nữa, năm 1999 nghiên cứu của giáo sư Kehoe chỉ ra tính hiệu quả của việc sử dụng mô phỏng trong giảng dạy thuật toán bằng cách chia học viên thành các nhóm để dạy về thuật toán BINOMIAL HEAP – một dạng cấu trúc đặc biệt của HEAP. Một nhóm tự học thuật toán bằng cách dùng phần mềm mô phỏng, một nhóm học bằng cách đọc sách có các hình vẽ mô tả. Kết quả chỉ ra rằng nhóm học qua phần mềm có khả năng cài đặt thuật toán tốt hơn nhóm còn Trang 39 lại (nhưng không phải là tất cả các thành viên đều như vậy) và họ nói rằng nhờ có mô phỏng mà họ có thể hiểu thuật toán nhanh hơn. Báo cáo của Kehoe chứng minh rằng cách hiệu quả để sử dụng thuật toán mô phỏng trong việc dạy học có thể đạt được kết quả cao hơn đó là sử dụng nó như là một hệ thống “mở” và hướng tự học (như là giao bài tập về nhà chẳng hạn). Như vậy, việc mô phỏng thuật toán hiệu quả ở chỗ coi nó là một tài liệu học được sử dụng cùng với các tài liệu khác cùng với các hướng dẫn về cách thức hoạt động của chương trình tương ứng với các thao tác của thuật toán. Bài báo cũng chỉ ra rằng mô phỏng thuật toán là một cách thuận lợi cho việc học cách thức hoạt động của thuật toán. Nếu như mô phỏng không phải lúc nào cũng tạo điều kiện thuận lợi cho việc học tập tốt thì ít nhất nó có thể chỉ ra rằng một thuật toán cần học có thể dễ tiếp cận hơn. Giáo sư Stasko cũng chỉ ra rằng cần có một vài điều kiện để thuật toán mô phỏng có hiệu quả hơn trong giảng dạy. Một trong những điều kiện đó là kết hợp mô phỏng thuật toán với các trích dẫn giải thích cho dễ hiểu (chú thích), việc mô phỏng sẽ hiển thị cùng với các mô tả một cách hình thức về các thao tác đó. Một điều kiện nữa là hệ thống mô phỏng thuật toán nên có khả năng chạy lại (replay) cho phép người dùng quan sát các thao tác quan trọng. Một vài chương trình có thể chỉ ra trạng thái trước, trạng thái sau. Thêm vào đó, các phản hồi từ phía người học cũng rất cần thiết để cải tiến chương trình mô phỏng cho tốt hơn. Mặc dù kết quả thực nghiệm chỉ ra rằng không phải lúc nào mô phỏng cũng mang lại lợi ích tốt nhưng nó cũng không chỉ ra rằng mô phỏng không mang lại hiệu quả trong giảng dạy. Trên thực tế, có những nghiên cứu chỉ ra tính không hiệu quả của một chương trình mô phỏng nhưng điều đó không làm cho việc mô phỏng mất đi tính ưu việt mà là một cách để ta phải xem lại chương trình đó, cải tiến chương trình đó cho nó hiệu quả hơn với người học. Trang 40 Tóm lại, để một chương trình mô phỏng có hiệu quả và mang lại lợi ích cho người học thì việc thiết kế và phát huy tính động trong chương trình là một yếu tố rất quan trọng. Các tính chất sau đây cũng là cần thiết: Truy cập mở: Người học có thể tự do truy cập vào các hệ thống mô phỏng. Đó là, bên cạnh việc có truy cập vào các hệ thống ở trường học, họ có thể truy cập vào hệ thống từ nhà hoặc bất cứ nơi nào khác khi họ cần đến. Chủ động điều khiển mô phỏng: Người học sẽ có thể tạo ra bộ dữ liệu của riêng mình khi sử dụng hệ thống. Trong khi tự định nghĩa bộ dữ liệu vào cũng có thể giúp đỡ học sinh xây dựng sự hiểu biết ban đầu, hệ thống nên có cả hai lựa chọn: tự xây dựng dữ liệu hoặc dùng bộ dữ liệu vào mặc định của hệ thống. Khả năng tương tác giữa người học và hệ thống: Hệ thống mô phỏng phải có khả năng tương tác với người học, nghĩa là cho phép người học xem được kết quả, cho phép dừng thuật toán ở bất cứ thời điểm nào để quan sát, xem lại dữ liệu ban đầu và chạy tiếp, chạy từng bước, huỷ, quay lại, chạy nhanh, chạy chậm để thuật toán cho ra kết quả mong muốn. Tương ứng với câu lệnh giả mã mô tả thuật toán sẽ là bước mô phỏng trên đồ thị do người học tự mô tả. Đón nhận thông tin phản hồi: Hệ thống ghi nhận lại những góp ý từ người học để dần dần cải tiến hệ thống cho hiệu quả hơn. Các hệ thống mô phỏng thuật toán có nền tảng phụ thuộc nhau. Với sự tiến bộ của công nghệ mới, sự phổ dụng của WWW và sự phát triển của ngôn ngữ Java, các nhà lập trình chuyển sang lĩnh vực mô phỏng thuật toán trực tuyến trên mạng. Một vài lập trình viên kết hợp cả đa phương tiện vào chương trình của họ. Việc sử dụng hệ thống mô phỏng thuật toán đã giải quyết triệt để các yếu điểm của cách dạy học truyền thống và có thể đào tạo từ xa. Trang 41 4. Một số yêu cầu đối với mô phỏng thuật toán 4.1. Mô phỏng đúng theo thuật toán Để mô phỏng một thuật toán nào đó, các bước thực hiện chỉ dẫn trên đồ họa phải phản ánh đúng theo nội dung của thuật toán đã đưa ra để đảm bảo rằng người học học đúng thuật toán mình yêu cầu. 4.2. Cho phép thực hiện theo từng bước Thông thường, khi học một thuật toán phải dùng đến chương trình mô phỏng để minh họa trong lúc học tập hoặc nghiên cứu thì thuật toán đó thường không phải là thuật toán đơn giản. Vì vậy, việc để cho người dùng có thể hiểu được thuật toán thông qua chương trình mô phỏng thì chương trình đó phải hết sức “mềm dẻo”: ngoài việc cho phép người dùng đưa dữ liệu vào đúng theo chuẩn bị của họ thì nó còn có thể cho phép chạy thuật toán theo từng bước để họ có thể tiện theo dõi quá trình thay đổi dữ liệu cũng như kết quả của thuật toán sau mỗi bước thực hiện. Ngoài ra, chương trình càng hiệu quả hơn nếu nó cho phép quan sát lại các bước đã thực hiện. 4.3. Mô phỏng thuật toán phải có tính động Vì công việc của mô phỏng là mô tả sự thay đổi về cấu trúc dữ liệu sau mỗi bước thực hiện của thuật toán nên hình ảnh mô phỏng cấu trúc đó cũng phải thay đổi theo từng bước để người học nắm bắt được ý tưởng của thuật toán. Ví dụ: với việc mô phỏng thuật toán tìm kiếm theo chiều rộng, cứ mỗi bước thực hiện xong thuật toán thì hình ảnh mô phỏng cũng phải thay đổi theo. Trong quá trình thực hiện thì đỉnh nào được chọn để xử lý sẽ có thông báo tại đỉnh đó để người dùng quan sát cho dễ. Dưới đây là hình ảnh trước và sau khi một bước thuật toán được thực hiện Trang 42 Một hình ảnh mô phỏng một bước thực hiện của thuật toán Hình ảnh mô phỏng đồ thị sau 1 bước thực hiện (1 thay đổi so với hình ảnh ở trên) Trang 43 4.4. Có thể thực thi với mọi bộ dữ liệu đầu vào Thường các thuật toán để dạy học cho học sinh Chuyên Tin đều là những thuật toán “tốt” và có ứng dụng để giải quyết một lớp bài toán trong tin học. Vì vậy, chương trình mô phỏng thuật toán cần đảm bảo chạy “tốt” đối với mọi bộ dữ liệu đầu vào: trường hợp tốt, trường hợp xấu, trường hợp ngẫu nhiên…. 4.5. Có sự phân cấp người học Thông thường, mức độ tiếp thu trong một giờ học của học sinh không giống nhau, có những học sinh hiểu bài nhanh nhưng cũng có những học sinh nắm bắt bài chậm hơn. Vì vậy, thuật toán mô phỏng cũng cần phải có những chức năng “mềm dẻo” với các đối tượng học. Ví dụ, có thể có chức năng lựa chọn độ trễ cho mỗi thao tác để phù hợp với mức độ quan sát của từng đối tượng học khác nhau hoặc cho phép chạy đi chạy lại một thuật toán trên một bộ dữ liệu vào… 5. Quy trình mô phỏng thuật toán 5.1.Nghiên cứu và phân tích giải thuật Bước đầu tiên trong quá trình giải một bài toán Tin học là xác định bài toán. Ở bước này, dựa trên phát biểu của bài toán ta phải xác định rõ Input (dữ liệu đầu vào) và Output (kết quả) của bài toán là gì và mối quan hệ giữa chúng. Thông tin đó cần được nghiên cứu một cách cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho, các đại lượng phát sinh trong quá trình giải toán và lựa chọn ngôn ngữ lập trình thích hợp. Tiêu chí để thiết kế hoặc lựa chon thuật toán thường dựa trên hai yếu tố là thời gian và không gian cần thiết để thực hiện thuật toán, trong đó yếu tố thời gian là đặc biệt quan trọng. Ngoài ra, trên thực tế khi lựa chọn thuật toán người ta còn quan tâm sao cho việc cài đặt thuật toán đó bằng một ngôn ngữ lập trình được dễ dàng, ít tốn công sức của người lập trình. Đối với những bài toán nhỏ số Trang 44 lần cần giải bài toán không nhiều nên tiêu chí sau cùng thường được ưa chuộng để lựa chọn thuật toán. Sau khi chứng minh được tính đúng đắn của giải thuật (có thể bằng suy luận Toán học hoặc chứng minh trên bộ dữ liệu mẫu phủ kín các trường hợp có thể xảy ra với bài toán) ta tiến hành cài đặt thuật toán trên một ngôn ngữ lập trình cụ thể. Để việc cài đặt thuật toán nhanh, thường người ta diễn tả lại thuật toán đủ chi tiết 5.2.Mô phỏng dữ liệu vào và kết quả đầu ra Mô phỏng dữ liệu vào là cách chọn hình thức hiển thị cho cấu trúc dữ liệu tương ứng với giải thuật. Việc lựa chọn mô hình mô phỏng cho dữ liệu vào quyết định tính hiệu quả của chương trình mô phỏng. Hình thức hiển thị này phải dễ hiểu, dễ gây hứng thú cho người học muốn tìm hiểu thuật toán. Ví dụ: với chương trình mô phỏng các thuật toán trên đồ thị, dữ liệu vào sẽ là một đồ thị bao gồm tập các nút và các cạnh nối các nút với nhau. Ta sẽ thể hiện các nút là 1 hình tròn màu xanh có tên nút ở giữa. Cạnh nối sẽ nối hai nút của đồ thị bằng một đường thẳng (nếu có trọng số thì trọng số đó sẽ nằm giữa vị trí giữa của hai nút). Như vậy, đồ thị được xây dựng rất trực quan và người học có thể quan sát dễ dàng những thay đổi trên đồ thị khi thực hiện các bước của giải thuật. Trang 45 Hình vẽ: Dữ liệu đầu vào: một đồ thị có hướng gồm 6 đỉnh, 7 cạnh Việc đưa dữ liệu vào (như đã phân tích trong phần 4 – chương 2) là một yếu tố quan trọng quyết định tính hiệu quả của mô phỏng thuật toán. Nên chương trình mô phỏng cần phải có nhiều cơ chế đưa dữ liệu vào, ví dụ như: - Đề xuất một số dữ liệu mẫu: Chương trình sẽ chuẩn bị một số dữ liệu mẫu từ trước để người học có thể học thuật toán ngay mà không phải chuẩn bị dữ liệu đầu vào. - Sinh ngẫu nhiên: để cho chương trình tự sinh một đồ thị tùy ý - Sinh dữ liệu thủ công: người học dùng công cụ của chương trình cung cấp để tự tạo đồ thị theo cách của mình. Đây là cách để giải quyết các băn khoăc của người học về thuật toán (với trường hợp này thì kết quả sẽ là thế nào? Với đồ thị đặc biệt này thì thuật toán có chạy không dừng hay không?.....) 5.3.Chia thuật toán thành nhiều bước nhỏ rồi mô phỏng theo từng bước Việc chia thuật toán thành nhiều bước nhỏ rất có ý nghĩa trong việc lập trình. Nó làm cho thuật toán ban đầu trở nên đơn giản, rõ ràng và dễ hiểu hơn. Trang 46 Ví dụ: thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số - thuật toán Dijsktra: Cho đồ thị G = (V, E) - V tập các đỉnh và E là tập các cạnh Thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh s tới đỉnh t. Gọi S là tập các đỉnh đã xác định được đường đi ngắn nhất từ s tới các đỉnh này và d[u] là độ dài đường đi ngắn nhất từ s tới u. Sau đây là giải thuật: Bước 1) Khởi tạo S = {s}, d[s] = 0, d[u] = + với u S Bước 2)Chọn u = s Lặp nếu u t Xét các đỉnh v (với v  S) 2.1 Cập nhật d[v] = min{d[v], d[u] + c[u, v]} và trace[v] = u nếu d[v] > d[u] + c[u,v] 2.2 Chọn v có d[v] là nhỏ nhất 2.3 Thêm v vào S, u = v Bước 3) In ra d[t] và đường đi từ s đến t Và ta sẽ mô phỏng theo từng bước của thuật toán như sau: Trang 47 Hình vẽ: Một bước mô phỏng của thuật toán Dijsktra 5.4. Tổng hợp mô phỏng theo các bước Cuối cùng, sau khi mô phỏng được từng bước của thuật toán ta tiến hành ghép các bước mô phỏng lại để được mô hình mô phỏng hoàn chỉnh: thao tác đưa dữ liệu vào, tiến hành chạy theo từng bước, quan sát những thay đổi của cấu trúc dữ liệu sau mỗi bước và quan sát kết quả cuối cùng khi thuật toán đã chạy xong. 5.5.Sơ đồ cấu trúc chung của hệ thống mô phỏng Có một số hệ thống mô phỏng thuật toán được viết bằng ngôn ngữ lập trình Java với cùng một kiến trúc như sau: Hình: Sơ đồ cấu trúc của một hệ thống mô phỏng Thuật toán (giả mã) Đồ họa mô phỏng hoạt động của thuật toán File kịch bản Kênh mô phỏng Các hàm mô phỏng Màn hình trình diễn mô phỏng Trang 48 - Kênh mô phỏng: Đóng vai trò như một kênh truyền giữa hệ thống mô phỏng và người dùng cuối. Nó đọc một file kịch bản do người dùng chuẩn bị từ trước chuyển sang cho các hàm mô phỏng mô phỏng thuật toán và đưa kết quả lên màn hình bằng đồ họa. - Các hàm mô phỏng: chứa chức năng vẽ các đối tượng được mô phỏng lên màn hình trình diễn mô phỏng. - Màn hình trình diễn mô phỏng: cung cấp môi trường đồ họa để hiển thị kết quả cho người dùng cuối quan sát. Một ví dụ về chuẩn bị file kịch bản và hình ảnh các bước mô phỏng được mô tả ở phần phụ lục của luận văn này. Hình ảnh thể hiện kết quả cuối cùng của thuật toán Dijsktra 6. Đề xuất lựa chọn công cụ để phát triển chương trình mô phỏng thuật toán Trong mục này, chúng ta sẽ phân tích các cách tiếp cận để xây dựng hệ thống mô phỏng và tính khả thi của chúng. Ta sẽ xem xét một vài công cụ mô phỏng thuật toán để xây dựng hệ thống mô phỏng phù hợp. Trang 49 Có ba cách tiếp cận có thể để xây dựng hệ thống mô phỏng thuật toán. Cách tiếp cận thứ nhất là lựa chọn hệ thống mô phỏng thuật toán cung cấp các công cụ chung để xây dựng các thành phần tương tác cho hệ thống mô phỏng (sử dụng lại tài nguyên sẵn có). Cách tiếp cận thứ hai là lựa chọn một chương trình mô phỏng một thuật toán đã có (dạng open source), sửa đổi, nâng cấp thành hệ thống mới. Cách tiếp cận cuối cùng là phân tích thiết kế hệ thống từ đầu. 6.1. Một số hệ thống mô phỏng thuật toán chung Có một số chương trình mô phỏng thuật toán theo ý người dùng. Hay nói cách khác là đưa thuật toán, đưa cấu trúc dữ liệu, đưa dữ liệu vào trên một file kịch bản theo quy định chung của chương trình mô phỏng. Nếu file kịch bản đưa vào phù hợp với ngữ cảnh của chương trình đó (nghĩa là có thể mô tả cấu trúc dữ liệu bằng đồ họa của chương trình) thì nó sẽ mô phỏng các bước của thuật toán theo đúng sự chuẩn bị của người dùng. Các hệ thống này thường được viết bằng ngôn ngữ Java có cùng kiến trúc như đã đề cập trong phần 5 – chương 2 của luận văn này. Ta sẽ phân tích từng hệ thống để thấy được những ưu và nhược điểm của từng hệ thống. JSAMBA JSAMBA (xem html) là một phiên bản viết bằng Java của hệ thống mô phỏng POLKA (như đã giới thiệu trong phần lịch sử phát triển thuật toán mô phỏng). JSAMBA cung cấp các đối tượng như: đoạn văn bản (text), đoạn thẳng (lines), hình chữ nhật (rectangle), tam giác (triangle), hình tròn (circles) và đa giác (polygon). Nó có thể vẽ các đối tượng được mô phỏng bằng một tốc độ khá nhanh. Hình ảnh ít bị “giật giật” hình khi chạy mô phỏng. Nó cho phép người dùng thay đổi kích thước của các đối tượng được mô phỏng. Ưu điểm Trang 50 Có thể sử dụng cho các chương trình được viết bằng bất kì một ngôn ngữ nào. Nó sử dụng các thư viện có sẵn của Java để mô phỏng và tận dụng được mọi ưu điểm của Java, dễ tiếp cận qua các trình duyệt web hiện nay. Hạn chế Phải chuẩn bị trước một file kịch bản theo đúng yêu cầu của chương trình. Điều này là một hạn chế lớn đối với học sinh trong việc tự học (vì nếu chúng biết chuẩn bị file kịch bản cho mô phỏng theo đúng quy cách của chương trình thì đã không cần phải học lập trình nữa!) Đối với giáo viên, một hạn chế nổi bật của Jsamba là không hỗ trợ bất kì một cấu trúc dữ liệu có sẵn nào. Điều này làm cho chương trình trở nên gọn và đóng kín nhưng mặt khác nó cũng gây nên một hạn chế là việc chuẩn bị file kịch bản là rất phức tạp vì phải mô hình hóa các cấu trúc dữ liệu đi kèm. JAWAA (Java and Web – based Algorithm Animation) JAWAA ( hoạt động tương tự như Jsamba. Nó là một ngôn nhữ gồm các lệnh đơn giản để tạo ra những mô phỏng cấu trúc dữ liệu vào hiển thị chúng trên trình duyệt web. Các lệnh được sinh trong file kịch bản và chạy bởi Jawaa Applet. JAWAA cung cấp các lệnh cho phép tạo và di chuyển một số đối tượng cơ bản: hình tròn, đoạn thẳng, đoạn văn bản và khối hình chữ nhật và một số cấu trúc dữ liệu cơ bản: mảng, stack, queue, danh sách, cây và đồ thị. Tốc độ vẽ và mô phỏng nhanh. Các đối tượng mô phỏng được vẽ lại trên màn hình nhờ việc sử dụng kĩ thuật bộ nhớ đệm đôi trong đó bao gồm hai hình ảnh: một được vẽ lên màn hình, một được lưu trữ trong bộ nhớ. Một đặc điểm nữa của Jawwa là nó cung cấp một số điều khiển cho người dùng: các nút lệnh bắt đầu, dừng, chạy từng bước và lựa chọn tốc độ thể hiện mỗi bước của thuật toán trên màn hình. Ưu điểm Trang 51 Cũng giống như Jsamba, Jawaa cũng là một phần mềm mô phỏng được viết bằng Java nên nó có mọi ưu điểm của ngôn ngữ Java. Ngoài ra, Jawaa còn cung cấp các cấu trúc dữ liệu cơ bản: stack, queue, list, tree….. nên người dùng có thể mô hình những cấu trúc dữ liệu này dễ dàng hơn JSAMBA. Các lệnh trong file kịch bản có thể được thực hiện riêng biệt hoặc trong một khối lệnh. Một ưu điểm nữa là Jawaa cho phép dùng miễn phí. Nhược điểm JAWAA không cho phép người dùng xem lại các bước đã mô phỏng nên việc muốn xem lại một thao tác nào đó đồng nghĩa với việc quan sát lại toàn bộ mô phỏng của một thuật toán. Hơn nữa, vì có cùng mô hình với JSAMBA nên JAWAA cũng yêu cầu một file kịch bản riêng. Đây là một hạn chế lớn đối với trình độ của học sinh trung học phổ thông. JANIME JANIME ( được viết bởi Noonan (trường đại học William và Mary). Đây cũng là một hệ thống mô phỏng trên nền web với mục đích phục vụ giảng dạy và được viết bằng java. JANIME rất giống với JAWWA, nó cũng cung cấp một số cấu trúc dữ liệu (mảng, stack và queue) và các hình vẽ cơ bản như: đoạn văn bản, hình chữ nhật, hình tròn, đoạn thẳng và đa giác. Mặc dù, JANIME chứa ít cấu trúc dữ liệu hơn JAWWA nhưng nó chứa sẵn nhiều lệnh kịch bản hơn và nhiều công cụ điều khiển hơn trong khi mô phỏng. Ưu điểm Trang 52 Tương tự như JAWWA nên nó có hầu hết các ưu điểm giống như JAWWA và một ưu điểm của JANIME là cho phép quan sát lại các bước đã thực hiện. Nhược điểm Mặc dù có nhiều ưu điểm hơn cả Jawwa nhưng nói chung các phần mềm mô phỏng có cùng một mô hình thường có nhược điểm giống nhau. Đều khó cho việc tự học của học sinh cũng như thời gian chuẩn bị các file kịch bản của giáo viên khi giảng dạy. Một nhược điểm nữa của Janime là không được dùng “miễn phí”. 6.2. Sử dụng công cụ mô phỏng thuật toán riêng biệt Có một số chương trình mô phỏng cụ thể về một thuật toán nào đó được viết rất nhiều và miễn phí trên mạng. Hình vẽ dưới đây hiển thị các kết quả khi tìm kiếm bằng google với khóa là “Algorithm Animation”. Chỉ trong 0.07s có tới 2.820.000 kết quả Trang 53 Sử dụng các chương trình này có một lợi ích là chỉ việc học cách sử dụng mà không mất thời gian xây dựng. Hình ảnh mô phỏng khá đa dạng và phong phú. Các thuật toán được mô phỏng tương đối nhiều. Tuy nhiên, các chương trình này được xây dựng một cách riêng rẽ (của các tác giả khác nhau), không có một hệ thống quy chuẩn nhất định. Có thể là của một trường đại học nổi tiếng (ví dụ: software/ AlgAnim/alg_anim.html) nhưng cũng có thể chỉ là một bài tập cá nhân ( code.html). Những chương trình này không có một hệ thống kiểm định tính đúng sai. Nếu học sinh “tự học” một mô hình mô tả sai cách thức hoạt động (có thể vì tự tìm được một mô hình mô phỏng của thuật toán) thì thật là “nguy hiểm” nếu người học tiếp thu theo đúng mô hình đó. 6.3. Xây dựng hệ thống từ đầu Khi hệ thống hiện tại không phù hợp với người dùng (có thể vì: không được đầu tư ngân sách, không hợp ngữ cảnh…) dẫn đến phát sinh yêu cầu một hệ thống mới. Hệ thống này sẽ bắt đầu được xây dựng từ nền tảng hoàn toàn mới dựa trên mô tả thực của người dùng. Trang 54 Chương 3 PHÂN TÍCH THIẾT KẾ HỆ THỐNG MÔ PHỎNG MỘT SỐ THUẬT TOÁN TRÊN ĐỒ THỊ 1.Mục đích Hệ thống được xây dựng nhằm giúp giáo viên có thể sử dụng như một công cụ giảng dạy các thuật toán trên đồ thị. Nó cũng có thể giúp học sinh chuyên Tin tự tìm hiểu thuật toán khi học các thuật toán trên đồ thị với cách thức hoạt động theo mô tả của thuật toán và những thay đổi trực quan bằng đồ họa. 2.Những yêu cầu thực tế Năm 2009, Bộ Giáo dục và Đào tạo cho xuất bản bộ Tài liệu giáo khoa chuyên Tin (3 tập - Hồ Sĩ Đàm chủ biên). Đây là tài liệu giới thiệu các thuật toán cơ bản, thường dùng. Bộ sách này có thể dùng cho giáo viên và học sinh Trung học phổng thông, Trung học cơ sở có thể làm tài liệu tham khảo. Tuy nhiên, để giúp học sinh có thể tự chuẩn bị trước các thuật toán ở nhà và giúp giáo viên làm rõ những thắc mắc của học sinh về thuật toán cơ bản và các cải tiến có thể làm giảm độ phức tạp của các thuật toán đó cần phải có thêm những công cụ giúp làm hiệu quả hơn cho công việc chuẩn bị của học sinh cũng như dẫn giải của giáo viên trong khi giảng bài. Chương trình mô phỏng của chúng tôi hướng tới mục tiêu đó. Mô phỏng một cách có hệ thống các thuật toán cơ bản mà học sinh chuyên sẽ học (theo phân phối chương trình chuyên). Đó là các thuật toán: bài toán tìm kiếm trên đồ thị, bài toán tìm đường đi ngắn nhất và bài toán tìm cây khung cực tiểu trên đồ thị vô hướng. Như đã phân tích trong mục 7 chương 2 về một số phần mềm mô phỏng, đã có nhiều trang web giới thiệu chương trình mô phỏng về các thuật toán miễn phí ở trên mạng Internet. Nhưng tổng hợp lại, các chương trình đó đều có chứa những nhược điểm có thể chỉ ra như sau: Trang 55 - Hầu hết các chương trình này đều là một dạng bài tập. Hay nói cách khác, người viết chỉ hoàn thiện một thuật toán riêng lẻ, các thuật toán được giới thiệu một cách rời rạc. ( .cs.auckland.ac.nz /~jmor159/PLDS210/alg_anim.html) - Hầu hết các chương trình chỉ giới thiệu về thuật toán sau đó cho phép người dùng chạy thử trên một mẫu dữ liệu có sẵn ( plet.htm). Hay nói cách khác các chương trình mô phỏng chỉ làm một việc là trình chiếu cho người sử dụng nhìn thấy các bước hoạt động của thuật toán đó. Việc theo dõi kịp các bước đó để hiểu đã thuật toán đã là một thử thách. Việc đó còn khó hơn đối với người bắt đầu học một thuật toán cụ thể nào đó chưa kể đến là các thuật toán đó đều trừu tượng. - Cũng đã có trang web giới thiệu 2 thuật toán Kruskal và Dijsktra cùng với việc cho phép người dùng quan sát mã nguồn của thuật toán (ở ngôn ngữ Java) nhưng việc giới thiệu này đòi hỏi người dùng muốn hiểu thuật toán phải biết một chút về Java. Vì vậy, hệ thống cũng khó phổ biển ở Việt Nam được vì ngôn ngữ lập trình mà học sinh Việt Nam được học là ngôn ngữ lập trình Free Pascal và Turbo Pascal và C. - Chưa cho phép người dùng đưa dữ liệu của mình vào để thử nghiệm thuật toán. 3. Đề xuất cho hệ thống mới Hệ thống mới cho phép người dùng quan sát hoạt động của thuật toán đồng thời trên dữ liệu mẫu và trên đoạn giả mã của thuật toán đó. Hệ thống còn cho phép chạy toàn thuật toán, chạy từng bước, lùi một bước để tiện quan sát những thay đổi trên đoạn giả mã và trên dữ liệu mẫu. Trang 56 Hệ thống cũng cho phép người học đưa dữ liệu vào (là đồ thị có hướng, vô hướng, có trọng số hoặc không trọng số tùy theo thuật toán mà người học lựa chọn). 4. Thiết kế hệ thống mô phỏng một số thuật toán trên đồ thị Mô hình được áp dụng cho chương trình mô phỏng trong luận văn này là mô hình thác nước. Các bước phân tích thiết kế gồm: Sơ đồ quy trình phân tích và thiết kế các nhiệm vụ khi thuật toán mô phỏng. Chi tiết về các bước của quá trình này đã được giới thiệu trong phần 5 – chương 3 của luận văn này. Nghiên cứu và phân tích giải thuật Xây dựng mô hình mô phỏng dữ liệu vào và dữ liệu ra Tách giải thuật mô phỏng thành nhiều bước nhỏ Tổng hợp các bước mô phỏng thành giải thuật hoàn chỉnh Kiểm nghiệm giải thuật bằng cách quan sát dữ liệu ra của từng bước nhỏ Trang 57 4.1. Lựa chọn công cụ lập trình Trong luận văn này, chúng tôi không xem xét ngôn ngữ C# một cách tách biệt, nó luôn đồng hành với "Bộ khung .NET". C# là một trình biên dịch hướng .NET, nghĩa là tất cả các mã của C# luôn luôn chạy trên trên môi trường .NET Framework. Điều đó dẫn đến 2 hệ quả sau: Cấu trúc và các lập luận C# được phản ánh các phương pháp luận của .NET ngầm bên dưới. Trong nhiều trường hợp, các đặc trưng của C# thậm chí được quyết định dựa vào các đặc trưng của .NET, hoặc thư viện lớp cơ sở của .NET. Trong Microsoft Intermediate Language (thường được viết tắt là "Intermediate Language", hay "IL") tương tự như ý tưởng về mã Java byte, nó là một ngôn ngữ cấp thấp với những cú pháp đơn giản (dựa trên cơ sở mã số hơn là text), chính điều này sẽ làm cho quá trình dịch sang mã máy nhanh hơn. Hiểu kĩ các cú pháp này sẽ mang lại những lợi ích đáng kể. Hướng đối tượng Dữ liệu mẫu đưa vào chương trình được mô phỏng bằng đồ họa: - Dữ liệu mẫu - Dữ liệu trực tiếp - Mô phỏng theo từng bước - Mô phỏng tự động toàn bộ thuật toán - Đồ thị đã được mô phỏng bằng đồ họa: những thay đổi trên hình vẽ qua các bước thực thi thuật toán. Input Thuật toán Output Mô hình bài toán mô phỏng thuật toán Trang 58 Như mọi ngôn ngữ lập trình hướng đối tượng khác, C# có các tính năng đóng kín, kế thừa và đa hình. Mỗi lớp của C# bao gồm các trường và phương thức tương ứng. Trong đó: Trường: là dữ liệu chỉ trạng thái của đối tượng. Phương thức: là các khả năng của đối tượng trả lời các tác động đến nó. Độc lập nền Trước tiên, độc lập nền có nghĩa là các file chứa mã lệnh có thể chạy trên bất kì nền nào, vào thời gian chạy trình biên dịch cuối sẽ hoạt động và mã có thể chạy trên một nền cụ thể. Nói cách khác việc dịch mã nguồn sang Intermediate Language cho phép độc lập nền trong .NET, nó giống như cách dịch mã nguồn sang Java byte code cung cấp sự độc lập nền trong Java. Sự cải tiến trong thực thi Mặc dù chúng ta đã so sánh với Java, IL thật sự có một chút khả quan hơn Java. IL luôn là trình biên dịch mạnh, ngược lại Java byte code thì thường là thông dịch. Một trong những bất lợi của Java là vào lúc thực thi quá trình dịch từ java byte code sang mã máy tốn nhiều tài nguyên. Thay vì phải dịch toàn bộ ứng dụng một lần, trình biên dịch JIT sẽ biên dịch từng phần mã khi nó được gọi. Khi mã được dịch rồi, mã kết quả sẽ được giữ lại cho tới khi thoát khỏi ứng dụng, chính vì thế nó không phải biên dịch lại trong lần chạy kế tiếp. Microsoft quả quyết rằng cách xử lí này có hiệu lực cao hơn là dịch toàn bộ ứng dụng, bởi vì có trường hợp một khối lượng lớn mã của ứng dụng không bao giờ được sử dụng trong thời gian chạy. Khi sử dụng trình biên dịch JIT, các đoạn mã này sẽ không bao giờ được dịch. Chính vì thế nhà cung cấp hi vọng rằng mã IL sẽ thực thi nhanh như là mã máy. Lời lí giải là, lần dịch cuối cùng trong thời gian chạy, trình biên dịch JIT sẽ biết chính xác loại vi xử lí mà chương trình sẽ chạy. Có nghĩa là nó có thể tối ưu Trang 59 mã thi hành cuối cùng bằng cách tham chiếu đến các đặc trưng của từng các bộ lệnh ứng với các loại vi xử lí đó. Trình biên dịch JIT có thể thực hiện tối ưu giống như Visual Studio 6, ngoài ra nó còn có thể tối ưu cho các loại vi xử lí cụ thể mà mã chương trình sẽ chạy. Tương hoạt giữa các ngôn ngữ Chúng ta đã biết cách thức IL cho phép độc lập nền, trình biên dịch JIT có thể cải thiện quá trình thực thi. Tuy nhiên, IL cũng làm cho tương hoạt giữa các ngôn ngữ trở nên dễ dàng hơn. Bạn có thể biên dịch IL từ một ngôn, và mã này sau đó có thể tương hoạt với IL được biên dịch bởi một ngôn ngữ khác. Bảo mật và hiệu quả cao C# là một thành phần của bộ Visual Studio .NET dành cho lập trình môi trường mạng nên nó có khả năng bảo mật cao. Cấu trúc câu lệnh khá đơn giản, khả chuyển, giao diện đồ họa, dễ sử dụng. Làm được tất cả những gì Java có thể làm được. 4.2. Chức năng mô phỏng của các thuật toán được cài đặt 4.2.1 Mô phỏng thuật toán tìm kiếm Khung chương trình cho phép người dùng nhập đồ thị để mô phỏng: tạo một đồ thị mới, tạo một đồ thị đã chuẩn bị từ trước: Trang 60 Màn hình mô phỏng được chia thành 3 phần. Phần giả mã, phần trạng thái của các đối tượng trong quá trình thực hiện thuật toán và phần hình ảnh đồ thị. Người dùng có thể lựa chọn thực hiện thuật toán trên đồ thị có hướng hoặc vô hướng. Chương trình mô phỏng cố gắng làm rõ cách thức hoạt động của thuật toán theo từng bước giã mã ở trên theo cách: Công cụ để tạo đồ thị cho mô phỏng Khung giả mã Khung mô phỏng bằng hình ảnh đồ thị Khung trạng thái Trang 61 Tại khung giả mã: Chứa đoạn giả mã của thuật toán tìm kiếm tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các cạnh trên đường đi tìm thấy sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.2. Mô phỏng thuật toán Dijkstra Khung chương trình cho phép người dùng nhập đồ thị để mô phỏng: Khung chương trình mô phỏng thuật toán: Trang 62 Việc mô phỏng thuật toán Dijkstra trong chương trình cho phép người dùng có thể lựa chọn trên 2 loại đồ thị: Đồ thị vô hướng có trọng số hoặc đồ thị có hướng có trọng số. Cũng giống như việc mô phỏng cho bài toán tìm kiếm, màn hình mô phỏng được chia thành ba phần: - Khung giả mã: Mô tả thuật toán Dijkstra bằng giả mã dạng liệt kê. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. - Khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được sửa nhãn, đỉnh mới kết nạp vào tập các đỉnh đã được tối ưu nhãn…. - Khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng, các giá trị đã tối ưu thể hiện chi phí ngắn nhất từ đỉnh xuất phát đến các đỉnh trung gian được tô màu đỏ. Các cạnh trên đường đi tìm thấy sẽ được tô màu đỏ hoặc một thông báo không tìm thấy đường đi từ đỉnh xuất phát đến đỉnh đích để người học quan sát kết quả một cách trực quan. Khung giả mã của thuật toán Khung mô phỏng trên đồ thị Khung trạng thái của thuật toán Trang 63 4.2.3. Mô phỏng thuật toán Ford – Bellman Vì thuật toán Ford – Bellman cũng là thuật toán tìm đường đi ngắn nhất giữa hai cặp đỉnh của đồ thị có trọng số giống như Dijkstra nên dưới đây, chúng tôi chỉ xin giới thiệu về màn hình là việc của chương trình (còn ý nghĩa các khung làm việc giống hệt thuật toán Dijkstra. 4.2.4. Mô phỏng thuật toán Prim Do thuật toán Prim tìm cây khung nhỏ nhất chỉ được thực hiện trên đồ thị vô hướng có trọng số nên trong chương trình mô phỏng người dùng không có các lựa chọn như các thuật toán trên, chỉ có thể nhập cho đồ thị vô hướng có trọng số. Khung chương trình mô phỏng cũng tương tự như các thuật toán đã mô tả ở trên. Khung chương trình để người dùng nhập dữ liệu đầu vào: Khung giả mã của thuật toán Khung mô phỏng trên đồ thị Khung trạng thái của thuật toán Trang 64 Khung chương trình mô phỏng: Tại khung giả mã: Chứa đoạn giả mã của thuật toán Prim tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Khung giả mã Khung mô phỏng bằng hình ảnh đồ họa Khung trạng thái Trang 65 Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các đỉnh đã được kết nạp vào cây và các cạnh thuộc sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.5. Mô phỏng thuật toán Kruskal Do thuật toán Kruskal tìm cây khung nhỏ nhất chỉ được thực hiện trên đồ thị vô hướng có trọng số nên trong chương trình mô phỏng người dùng không có các lựa chọn như các thuật toán trên, chỉ có thể nhập cho đồ thị vô hướng có trọng số. Khung chương trình mô phỏng cũng tương tự như các thuật toán đã mô tả ở trên. Khung chương trình để người dùng nhập dữ liệu đầu vào: Khung chương trình mô phỏng: Trang 66 Tại khung giả mã: Chứa đoạn giả mã của thuật toán Kruskal tương ứng với lựa chọn của người dùng. Thuật toán thực hiện đến bước nào thì bước đó đổi màu cho người dùng tiện quan sát. Tại khung trạng thái: Ghi nhận và hiển thị những thay đổi của tập các đỉnh đã được thăm, đỉnh đang được xét…. Tại khung đồ thị: Hình ảnh đồ thị sẽ thay đổi theo mỗi bước thuật toán thực hiện qua. Các đỉnh đã được thăm qua sẽ được tô màu vàng. Các đỉnh đã được kết nạp vào cây và các cạnh thuộc sẽ được tô màu đỏ để người học quan sát kết quả một cách trực quan. 4.2.6. Thuật toán tìm chu trình Hamilton 5. Giới thiệu chương trình 5.1.Tổng quan về hệ thống Hệ thống mô phỏng được chia thành các module nhỏ. Mỗi module thực hiện một chức năng riêng biệt. Có 2 module chính: Module GraphTool: Thực hiện công việc thiết kế giao diện dành cho quá trình mô phỏng. Từ việc nhập đồ thị mới, người dùng lựa chọn thuật toán mô phỏng và mô phỏng theo kịch bản đã được “dựng” sẵn. Khung giả mã Khung mô phỏng bằng hình ảnh đồ họa Khung trạng thái Trang 67 Module Model: Thực hiện cài đặt các mô hình thuật toán, lưu trữ các thông tin cần thiết và lên kịch bản cho quá trình mô phỏng. Giữa hai module này luôn có mối quan hệ khăng khít với nhau. Một module thực thi thuật toán do người dùng lựa chọn sau đó lên kịch bản để mô phỏng. Module còn lại tiếp nhận kịch bản từ module kia và mô phỏng theo kịch bản đã được dựng sẵn theo đúng mô hình thuật toán đã được thực thi để trình chiếu tới người học. Để việc mô phỏng có thể áp dụng được với nhiều thuật toán khác nhau, tại mỗi module, việc cài đặt các công cụ hỗ trợ cho quá trình mô phỏng và dựng kịch bản mô phỏng chúng tôi luôn dựng ở dạng tổng quát. Thêm vào đó là một số công cụ riêng rẽ, thể hiện đặc trưng của mỗi thuật toán. Dưới đây là một số đối tượng dùng chung cho quá trình mô phỏng: 5.1.1. Các đối tượng xây dựng cấu trúc đồ thị  Entity: chứa 3 thuộc tính: + Key: tên của đỉnh trong đồ thị + Value: Trọng số của cạnh (trong trường hợp đồ thị là vô hướng thì trọng số = 1 nghĩa là 2 đỉnh có cạnh nối, = 0 nghĩa là không có cạnh nối) + IsDirection: đánh dấu đồ thị ban đầu là có hướng hay vô hướng. public class Entity { public virtual string Key { get; set; } public virtual int Value { get; set; } public static bool IsDirection {get; set;}  Đối tượng Graph: gồm các thuộc tính: + Tập các đỉnh Vertexs + Tập các cạnh. public class Graph { public Graph() { Vertexs = new HashSet(); } Trang 68 public HashSet Vertexs { get; set; } public int GetEdgeValue(string fromKey, string toKey) { Vertex from = GetVertex(fromKey); if (from.ConnectTo(toKey)) { return from.GetEdge(fromKey, toKey).Value; } return int.MaxValue; } public Vertex GetVertex(string key) { foreach (Vertex v in Vertexs) { if (v.Key == key) return v; } throw new Exception("Key is not exist."); } }  Vertex: Chứa các thuộc tính về đỉnh + Kế thừa các thuộc tính của lớp Entity + Phương thức: ConnectTo: xác định đỉnh kề với đỉnh đang xét NextToVertex: Xác định tập các đỉnh kề với đỉnh đang xét. AddEdge: Thêm 1 cạnh (cung) có 1 đầu mút là đỉnh đang xét. RemoveEdge: Loại bỏ 1 cạnh (cung) có 1 đầu mút là đỉnh đang xét. public class Vertex : Entity { private Dictionary _edges = new Dictionary<string, Edge>(); private IList _nextToVertexs = new List(); public bool ConnectTo(string keyTo) { string edgeKey = this.Key + ">" + keyTo; if (_edges.ContainsKey(edgeKey)) return true; if (Entity.IsDirection == false) { edgeKey = keyTo + ">" + this.Key; if (_edges.ContainsKey(edgeKey)) return true; } return false; } Trang 69 public void AddEdge(Edge edge) { _edges.Add(edge.Key, edge); if (edge.FromVertexKey != Key) { _nextToVertexs.Add(edge.FromVertexKey); } else if (edge.ToVertexKey != Key) { _nextToVertexs.Add(edge.ToVertexKey); } } public void RemoveEdge(Edge edge) { _edges.Remove(edge.Key); if (edge.FromVertexKey != Key) { _nextToVertexs.Remove(edge.FromVertexKey); } else if (edge.ToVertexKey != Key) { _nextToVertexs.Remove(edge.ToVertexKey); } } public void RemoveAllEdges() { _edges.Clear(); } public Edge GetEdge(string fromKey, string toKey) { if (string.IsNullOrEmpty(fromKey) || string.IsNullOrEmpty(toKey)) throw new ArgumentNullException("Key is not alowed null."); string edgeKey = fromKey + ">" + toKey; if (_edges.ContainsKey(edgeKey)) return _edges[edgeKey]; else if (Entity.IsDirection == false) { edgeKey = toKey + ">" + fromKey; return _edges[edgeKey]; } throw new Exception("Not found edge"); } public IList GetNextToVertexs() { return _nextToVertexs; }  Edge: chứa các thuộc tính về đỉnh thừa kế từ lớp Entity bao gồm 2 thông số: + Cạnh được nối từ FromVertexKey đến ToVertexKey. + Trọng số của cạnh (trong trường hợp đồ thị không trọng số thì ta dùng giá trị này để đánh dấu có cạnh nối giữa 2 đỉnh hay không). Trang 70 public class Edge : Entity { public override string Key { get { return FromVertexKey + ">" + ToVertexKey; } set { base.Key = value; } } public string FromVertexKey { get; set; } public string ToVertexKey { get; set; } }  Một cái “túi” để “đựng” các bước thực hiện theo thuật toán để mô phỏng. public class BagStep { private IList _steps = new List(); public void AddStep(Step step) { _steps.Add(step); } public IList Steps { get { return _steps; } } } 5.1.2. Công cụ vẽ hình ảnh để mô phỏng  CanvasDrawing: Xây dựng toàn bộ đồ thị nền trước, trong và sau khi mô phỏng.  EdgeDrawing: vẽ cạnh trước, trong và sau khi thực hiện thuật toán mô phỏng.  EntityDrawing: Chuyển đổi 2 chế độ: chế độ cho phép người dùng nhập một đồ thị đầu vào và chế độ mô phỏng.  VertexDrawing: vẽ đỉnh trước, trong và sau khi thực hiện thuật toán mô phỏng, những thay đổi giá trị trên các đỉnh cũng được thể hiện trên hình vẽ. 5.1.3. Chức năng chi tiết của các công cụ hỗ trợ cho quá trình mô phỏng Thủ tục Chức năng Trang 71 public void AddEdgeDrawing(string fromVertex, string toVertex, int value) Vẽ một cạnh private void RemoveVertexDrawing(VertexDrawing vertexDrawing){} Vẽ đỉnh public bool IsInShortestPath { get; set; } Chứa đựng thông tin về các cạnh trên đường đi ngắn nhất của thuật toán Dijkstra public bool IsInSpanningTree { get; set; } Chứa đựng thông tin về các cạnh thuộc cây khung của thuật toán Prim public bool IsInFindingPath { get; set; } Chứa đựng thông tin về các cạnh trên đường đi từ đỉnh xuất phát đến đỉnh kết thúc của thuật toán tìm kiếm DFS và BFS private void DrawAtDesignMode(DrawingContext drawingContext) Chế độ đồ họa trong khi xây dựng dữ liệu đầu vào private void DrawAtRunMode(DrawingContext drawingContext) Chế độ đồ họa trong khi thực hiện mô phỏng trên đồ thị đã cho public void AddEdgeDrawing(EdgeDrawing e) {} public void RemoveEdgeDrawing(EdgeDrawing e) {} public void ReRender(){} public void RemoveAllEdgeDrawings(){} Các công cụ hỗ trợ quá trình thiết kế dữ liệu đầu vào bằng hình vẽ và quá trình mô phỏng. 5.2. Giới thiệu các công cụ hỗ trợ mô phỏng do người dùng cài đặt Như đã nói ở trên, chúng tôi dùng C# là ngôn ngữ cài đặt chương trình mô phỏng là để tận dụng các ưu điểm của nó. Việc mô phỏng trong chương trình được chia thành các module, các chức năng hỗ trợ việc mô phỏng lại được chia thành các module nhỏ hơn, đóng kín với các module khác. Các lớp độc lập nhau có thể coi như một kiểu dữ liệu để khai báo trong chương trình khi cần sử dụng. 7.3.1 Tìm kiếm: Tìm kiếm theo mô hình DFS: Chương trình con: Trang 72  DFS mô phỏng: Module: GraphTool.Searching.DFSForm  DFS thực thi thuật toán và “lên” kịch bản: GraphTool.Model.DFS Kiến trúc: Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Các công cụ trong chương trình: private Dictionary _trace =new Dictionary<string, string>(); private Dictionary _free = new Dictionary(); public Graph Graph { get; set; } public string VertexKeyStart {get; set;} public string VertexKeyEnd {get; set;} private BagStep _steps = new BagStep();  Công cụ thuật toán:các thuật toán trợ giúp cho thuật toán chính: Thủ tục Chức năng public void Execute() Thực thi thuật toán. private void GetResult() Lấy kết quả và lưu trữ vào các bước cho vào túi. public BagStep GetBagStep() Lấy túi đã đựng các bước để chuyển qua mô phỏng. private void DfsAlgorithms(Vertex u) Chương trình đệ quy thực hiện việc thăm theo mô hình DFS từ một đỉnh u tới các đỉnh kề với nó. private void Initialize() Khởi tạo các thông số đồ thị dựa trên mô hình đồ thị mà người dùng đưa vào trước khi thực hiện thuật toán. Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc DFS mô phỏng: Module: GraphTool.Sear ching.DFSForm DFS thực thi thuật toán: GraphTool.Mo del.DFS Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.DFS thực hiện thuật toán Trang 73 private void UpdateTrace(string after, string before) Thực hiện công việc truy vết. private void UpdateInfoAtStepEnd() Hoàn thiện thuật toán. Ghi nhận các cạnh đã đi qua theo mô hình DFS. Các bước sẽ được lưu trữ trong túi. public class StepStartDFS() Step kế thừa của lớp Step, khởi tạo đỉnh xuất phát public class StepEndDFS : Step Ghi nhận những cạnh đã thăm trong quá trình thực hiện theo thuật toán DFS và truy vết. public class DfsStep1 : Step public class DfsStep21 : Step public class DfsStep22 : Step public class DfsStep23 : Step public class DfsStep3 : Step Các bước được làm mịn trong quá trình mô phỏng thuật toán DFS. Thừa kế từ lớp Step Tìm kiếm theo mô hình BFS: Chương trình con:  BFS mô phỏng: Module: GraphTool.Searching.BFSForm  BFS thực thi thuật toán: GraphTool.Model.BFS Kiến trúc: Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Các công cụ sử dụng trong chương trình: private Dictionary _trace = new Dictionary(); private Dictionary _free = new Dictionary(); public Graph Graph { get; set; } private Queue _Q = new Queue(); public string VertexKeyStart { get; set; } public string VertexKeyEnd { get; set; } Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc BFS mô phỏng: Module: GraphTool.Sear ching.BFSForm BFS thực thi thuật toán: GraphTool.Mo del.BFS Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.BFS thực hiện thuật toán Trang 74 private BagStep _steps = new BagStep();  Các chương trình con và chức năng của chúng: Thủ tục Chức năng public void Execute() Thực thi thuật toán. private void GetResult() Lấy kết quả và lưu trữ vào các bước cho vào túi. public BagStep GetBagStep() Lấy túi đã đựng các bước để chuyển qua mô phỏng. private void BfsAlgorithms(Vertex u) Chương trình đệ quy thực hiện việc thăm theo mô hình BFS từ một đỉnh u tới các đỉnh kề với nó. private void Initialize() Khởi tạo các thông số đồ thị dựa trên mô hình đồ thị mà người dùng đưa vào trước khi thực hiện thuật toán. private void UpdateTrace(string after, string before) Thực hiện công việc truy vết. private void UpdateInfoAtStepEnd() Hoàn thiện thuật toán. Ghi nhận các cạnh đã đi qua theo mô hình BFS. Các bước sẽ được lưu trữ trong túi. Public class StepStart1() Step kế thừa của lớp Step, khởi tạo đỉnh xuất phát Public class StepEnd1 : Step Ghi nhận những cạnh đã thăm trong quá trình thực hiện theo thuật toán BFS và truy vết. Public class BfsStep1 : Step Public class BfsStep21 : Step Public class BfsStep22 : Step Public class BfsStep23 : Step Public class BfsStep3 : Step Các bước được làm mịn trong quá trình mô phỏng thuật toán BFS. 7.3.2 Dijsktra Chương trình con  Dijsktra mô phỏng: Module: GraphTool.Searching.dijkstraForm  Dijkstra thực thi thuật toán: GraphTool.Model.dijkstra: thực thi theo đúng thuật toán và lưu lại các bước đã thực hiện vào trong một cái túi (BagStep) dùng trong mô phỏng. Kiến trúc: Trang 75 Chức năng: các công cụ và chức năng của chúng trong mô hình cài đặt  Công cụ sử dụng trong module: private HashSet _vertexGone = new HashSet(); private HashSet _vertexGo = new HashSet(); private Dictionary _trace = new Dictionary<string, string>(); private Dictionary _distance = new Dictionary(); private BagStep _steps = new BagStep(); public Graph Graph { get; set; } public string VertexKeyStart { get; set; } public string VertexKeyEnd { get; set; } public BagStep GetBagStep()  Các chương trình con và chức năng của chúng: Thủ tục Chức năng public void Execute() Thực hiện thuật toán Dijkstra public void Initialize(); Khởi tạo các thông số cần thiết cho thuật toán private void UpdateEdgeGo(Vertex u) Sửa nhãn cho tất cả các đỉnh chưa được chọn khi mới cố định đỉnh u Trả lại các bước thuật toán đã thực hiện trên bộ dữ liệu đầu vào để chương trình mô phỏng bắt đầu làm việc Dijkstra mô phỏng: Module: GraphTool.Dijk tra.DijktraFor m Dijkstra thực thi thuật toán: GraphTool.Mo del.Dijkstra Chuyển mô hình đồ thị mà người dùng đã chuẩn bị cho Module Model.Dijkstra thực hiện thuật toán Trang 76 private void UpdateTrace(string after, string before) Cập nhật vết cho đường đi trong khi thực hiện thuật toán private void UpdateInfoAtStepEnd() Ghi lại các thông số cuối cùng để dựng kịch bản cho mô phỏng private void AddVertextToVertexGone(Vertex gone) Kết nạp thêm một đỉnh vào tập S (các đỉnh đã cố định nhãn) private void AddStepStart() Ghi nhận bước đi đầu tiên của thuật toán Dijkstra trên đồ thị vừa chọn. private void AddStepStart12(string key) private void AddStepUpdateVertexValue() private void AddStepUpdateVertexValueStep11() private void AddStepUpdateVertexValueStep12() private void AddStepChooseVertexMin(string key) private void AddStepAddVertex() private void AddStepEnd() Cập nhật các bước để lên kịch bản mô phỏng public class StepStart : Step { public string VertexStart { get; set; } private Dictionary _d = new Dictionary(); public void UpdateVertexValue(Dictionary d) { foreach (string key in d.Keys) { _d.Add(key, d[key]); } } public Dictionary GetDistanceInfomation() { return _d; } Kịch bản cho mô phỏng: Bước khởi đầu: Xây dựng các thông số ban đầu từ đồ thị do người dùng chuyển vào thành Input cho thuật toán. public class StepEnd : Step { private IList _edgesInShotestPath = new List(); public void UpdateEdgeInfosInShotestPath(Dictionary<string , string> trace, string keyEnd, string keyStart) { Bước cuối cùng: sau khi thực hiện thuật toán Dijkstra, lớp StepEnd lưu giữ lại toàn bộ thông số cần thiết để mô phỏng: các cạnh thuộc đường đi ngắn nhấ