Báo cáo Nghiên cứu khoa học: Mô phỏng một số thuật toán đồ thị

MỤC LỤC Mục lục 1. Lý do chọn đề tài …………………………………………………………….3 2. Những kiến thức cơ sở ………………………………………………………3 2.1. Khái niệm thuật toán ……………………………………………….3 2.2. Các đặc trưng của thuật toán ……………………………………….4 2.3. Độ phức tạp thuật toán ……………………………………………..4 3. Tổng quan về mô phỏng thuật toán ………………………………………….4 3.1. Khái niệm mô phỏng thuật toán ……………………………………4 3.2. Lịch sử mô phỏng thuật toán ……………………………………….5 3.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….6 3.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………8 4. Tổng quan về đồ thị ………………………………………………………….8 4.1. Định nghĩa đồ thị …………………………………………………...9 4.2. Phân loại đồ thị ……………………………………………………..9 4.3. Cây khung và cây khung nhỏ nhất …………………………………10 4.4. Các phương pháp biểu diễn đồ thị ………………………………....10 5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….11 5.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….11 5.1.1. Mục đích……………………………………………………..11 5.1.2. Đặc điểm …………………………………………………….11 5.1.3. Kết quả phân tích…………………………………………….12 5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...14 5.2.1. Màn hình nền hệ thống mô phỏng…………………………...14 5.2.2. Giao diện chính và chức năng trình mô phỏng ……………..14 6. Cài đặt mô phỏng thuật toán đồ thị …………………………………………15 6.1. Công cụ lập trình …………………………………………………..15 6.2. Cài đặt thuật toán Prim …………………………………………….16 6.2.1. Bài toán ……………………………………………………..16 6.2.2. Ý tưởng thuật giải …………………………………………..16 6.3. Cài đặt các lớp trong chương trình…………………………………17 6.3.1. Lớp cơ sở …………………………………………………..17 6.3.2. Lớp Prim ……………………………………………………18 6.3.3. Lớp Main …………………………………………………...18 7. Kết luận ……………………………………………………………………18 8. Hướng phát triển …………………………………………………………..18 Tài liệu tham khảo 1. Lý do chọn đề tài Lý thuyết đồ thị là một vấn đề hết sức phức tạp, hơn nữa nó chiếm một vị trí quan trọng trong khối kiến thức cơ sở của ngành công nghệ thông tin. Để hiểu được lý thuyết về đồ thị cũng như hiểu được hoạt động của các thuật toán trên đồ thị cần phải có thời gian tìm hiểu lâu dài. Việc dạy và học về đồ thị trong nhà trường cũng gặp nhiều khó khăn. Các thuật toán khiến cho người học khó hiểu, khó hình dung nhất là với những người mới bắt đầu học Tin ví dụ như thuật toán Dijkstra và nếu chỉ với các dòng lệnh của thuật toán, người dạy đôi khi cũng rất khó truyền đạt cho người học ý tưởng, hoạt động của thuật toán như thế nào. Sử dụng việc mô phỏng các thuật toán trên đồ thị sẽ giải quyết được vấn đề này. Bởi vì việc mô phỏng với giao diện đồ hoạ, rất trực quan, có chú giải từng bước, đồng thời với giao diện đồ họa trực quan như vậy, người sử dụng có thể tương tác với hệ thống mô phỏng. Mô phỏng sẽ giúp cho người học nhanh chóng hiểu được bản chất, hiểu được từng câu lệnh trong thuật toán hoạt động như thế nào, đồng thời đánh giá được tính đúng đắn của thuật toán. Còn đối với người dạy, mô phỏng sẽ giúp cho người dạy dễ dàng truyền đạt ý tưởng của thuật toán, giúp cho quá trình giảng dạy thuận lợi hơn. Hơn nữa, mô phỏng làm cho người học cảm thấy hứng thú hơn khi tiếp xúc với các thuật toán trên đồ thị. Mô phỏng cũng là một công cụ giảng dạy hiệu quả cho người dạy và cũng là một tư liệu học tập tốt. Như vậy mô phỏng thuật toán nói chung và mô phỏng các thuật toán đồ thị nói riêng mang lại nhiều lợi ích trong việc dạy và học về lý thuyết đồ thị. Đồng thời nó cũng góp phần quan trọng vào việc ứng dụng công nghệ thông tin vào việc giảng dạy trong nhà trường. Thuật toán về đồ thị chiếm một số lượng khá lớn, tuy nhiên số lượng thuật toán được mô phỏng và đưa vào áp dụng để giảng dạy thì còn hạn chế. Cũng có nhiều trang Web về mô phỏng thuật toán đồ thị nhưng hầu hết chưa có hệ thống. Cao học K15 cũng có một luận văn mô phỏng thuật toán đồ thị như thuật toán Dijkstra, thuật toán Kruskal. Vì vậy trong khuôn khổ nghiên cứu của mình, em xin tiếp tục nghiên cứu việc mô phỏng một số thuật toán đồ thị như thuật toán Prim, các thuật toán tìm kiếm theo chiều rộng, chiều sâu trên đồ thị. 2. Những kiến thức cơ sở 2.1. Khái niệm thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên cấu trúc dữ liệu sao cho: với một bộ dữ liệu vào, sau một số hữu hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định. 2.2. Các đặc trưng của thuật toán - Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, đa nghĩa. Thực hiện đúng các bước của thuật toán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra. - Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng lại và cho kết quả sau một số hữu hạn bước. Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng quá trình đã định, ta phải đạt được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu bài toán. Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kì bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau. - Tính khả thi: Kích thước dữ liệu phải đủ nhỏ, thuật toán phải được máy tính thực hiện trong thời gian cho phép, thuật toán phải dễ hiểu và dễ cài đặt. 2.3. Độ phức tạp thuật toán Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được gọi là O(g(n)) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho: f(n) ≤ c.g(n) với mọi n ≥ n0 Nghĩa là nếu xét những giá trị n ≥ n0 thì hàm f(n) sẽ bị chặn trên bởi một hằng số nhân với g(n). Khi đó, nếu f(n) là thời gian thực hiện của một giải thuật thì ta nói giải thuật đó có cấp là g(n) (hay độ phức tạp tính toán là O(g(n))). 3. Tổng quan về mô phỏng thuật toán 3.1. Khái niệm mô phỏng thuật toán Mô phỏng thuật toán (Algorithm Animation) là quá trình tách dữ liệu, thao tác, ngữ nghĩa và tạo mô phỏng đồ họa cho quá trình trên [Stasko 1990]. Mô phỏng thuật toán được thiết kế để giúp người dùng có thể hiểu thuật toán, đánh giá chương trình và sửa lỗi chương trình. Một chương trình máy tính chứa các cấu trúc dữ liệu của thuật toán mà nó thực thi. Trong quá trình thực thi chương trình, các giá trị trong cơ sở dữ liệu được thay đổi. Mô phỏng thuật toán sử dụng biểu diễn đồ họa để biểu diễn cấu trúc dữ liệu và chỉ ra sự thay đổi giá trị trong cơ sở dữ liệu trong mỗi trạng thái. Thông qua đó, người sử dụng có thể xem được từng bước thực thi chương trình và nhờ vậy có thể hiểu chi tiết được thuật toán. Mô phỏng thuật toán cũng được dùng để đánh giá một chương trình đã có bằng cách cung cấp các mô phỏng cho các thành phần của hệ thống, nhờ đó có thể kiểm tra được hiệu năng của hệ thống. Bên cạnh việc giúp người sử dụng hiểu hơn về hệ thống, mô phỏng thuật toán còn được dùng để giúp thực hiện quá trình dò lỗi dễ dàng hơn. Để sử dụng mô phỏng thuật toán trong quá trình dò lỗi của một chương trình, người sử dụng chú thích vào các trạng thái của chương trình để tạo ra các lệnh mô phỏng, sau đó chúng sẽ được đưa vào hệ thống mô phỏng thuật toán để tạo mô phỏng. Người sử dụng có thể xem chương trình của họ đã thực hiện như thế nào, các giá trị dữ liệu ở mỗi bước và một bước sẽ ảnh hưởng tới các bước sau như thế nào. Nó sẽ giúp người sử dụng tìm ra tất cả các lỗi có thể xảy ra trong chương trình. 3.2. Lịch sử mô phỏng thuật toán Mô phỏng thuật toán đã được xây dựng từ hai thập kỷ gần đây. Nhưng chương trình mô phỏng thuật toán đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories khi mô phỏng ngôn ngữ liên kết danh sách vào năm 1966. Mô phỏng thuật toán phát triển mạnh vào đầu những năm 80 của thế kỷ 20. Vào năm 1981, video (sorting out sorting) được xây dựng bởi Ronald Baecker ở đại học Toronto được coi là khởi điểm của lĩnh vực mô phỏng thuật toán. Từ đó các nhà giáo dục đã sử dụng mô phỏng thuật toán để trợ giúp quá trình dạy học. Giữa những năm 80 và đầu những năm 90, hai hệ thống có ảnh hưởng mạnh đến về sau được phát triển và có ý nghĩa lớn trên tất cả những hệ thống sau này. Hai hệ thống này là BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition-based Animation GeneratiOn) [Stasko 1990]. Từ khi hai hệ thống của BALSA và TANGO được phát triển, các hệ thống đi sau của hai hệ thống đáng chú ý này cũng được phát triển. Với việc phát triển của công nghệ mới, tính phổ dụng của mạng toàn cầu và sự tiến hóa của ngôn ngữ lập trình Java, những người phát triển đã xây dựng những hệ thống mô phỏng thuật toán trực tuyến, có lợi thế của những hệ thống mở dễ tiếp cận hơn.Một số nhà phát triển cũng hợp nhất việc sử dụng đa phương tiện trong các hệ thống của họ. Việc sử dụng các hệ thống mô phỏng thuật toán không còn bị bó hẹp trong các lớp học truyền thống hoặc phòng thí nghiệm giảng dạy nữa mà đã được mở rộng để dạy từ xa. Trong khoảng hai thập niên gần đây, một số rất lớn các hệ thống mô phỏng thuật toán đã ra đời và phát triển mạnh mẽ. Phần lớn các hệ thống mô phỏng thuật toán đã đề cập trong mục này đều phổ biến hơn và phức tạp hơn các hệ thống đang được sử dụng trong thực tế. Chúng đã được phát triển và sử dụng bởi những nhà chuyên môn, với mục đích giáo dục hoặc nghiên cứu thực nghiệm của họ. Một trong số các hệ thống này có một kiến trúc phức tạp và cần những công nghệ đặc biệt để chạy nó. Chúng ta không có bất kỳ tiện ích nào của các hệ thống này để xây dựng hệ thống mô phỏng các thuật toán đồ thị; thay vào đó, chúng ta đã ước lượng được các hệ thống mô phỏng hiện hữu khác mà kích thước nhỏ hơn và có những kiến trúc đơn giản hơn. 3.3. Tác dụng của mô phỏng thuật toán trong dạy học Các hệ thống mô phỏng thuật toán được sử dụng rộng rãi như công cụ hỗ trợ giảng dạy trong ngành giáo dục khoa học máy tính. Một số nghiên cứu thực nghiệm đã ước lượng hiệu quả của chúng trong giáo dục và kết quả nhận được có thay đổi. Những tác dụng của việc áp dụng mô phỏng thuật toán trong dạy học được ghi nhận lại như sau: Việc sử dụng các hoạt cảnh mô phỏng thuật toán gây hứng thú cho người học, làm tăng tính sáng tạo của người học. Sử dụng mô phỏng kết hợp với phương pháp thuyết trình truyền thống làm tăng tốc độ hiểu biết cho người học. Ngoài ra mô phỏng giúp cho người học dễ hiểu thuật toán hơn thông qua các bước mô phỏng trực quan kết hợp với mã nguồn chương trình. Tuy nhiên việc sử dụng mô phỏng thuật toán không phải lúc nào cũng đem lại hiệu quả. Các nghiên cứu thực nghiệm của Stasko (1993) và Bynre (1996) đã cho kết quả là giữa nhóm sinh viên sử dụng mô phỏng và nhóm không sử dụng mô phỏng thì hiệu quả đạt được không có sự chênh lệch là mấy. Những kết quả thí nghiệm bất lợi này gợi ý những yếu tố quan trọng khác trong việc sử dụng mô phỏng thuật toán. Các kết quả đã thông báo rằng để đạt được hiệu quả mô phỏng thuật toán đầy đủ thì điều quan trọng là mô phỏng được sử dụng phối hợp với những yếu tố khác. Phải để sinh viên tự mình sử dụng, điều khiển quá trình mô phỏng và phải để họ tự tạo những bộ dữ liệu của riêng mình. Để mô phỏng thuật toán mang lại hiệu quả cao nhất, nó phải thoả mãn những yêu cầu sau đây : Thứ nhất, sử dụng mô phỏng thuật toán phải song song với những chỉ dẫn, có hệ thống trợ giúp sử dụng, phải có mô phỏng từng bước để người học hiểu từng bước của giải thuật, có khả năng quay lui để ngườu học có thể quay lại những bước quan trọng, đồng thời lấy ý kiến phản hồi từ sinh viên để cải thiện chương trình mô phỏng thuật toán tốt hơn. Hai là phải biết xây dựng mô phỏng hiệu quả : mô phỏng cái gì, mô phỏng như thế nào, hình ảnh ra sao,... Một chương trình mô phỏng thuật toán hiệu quả phải đáp ứng được các yêu cầu : Truy cập mở (Open access): Người dùng có thể truy cập hệ thống mô phỏng mở. Hơn nữa, nếu có cài đặt hệ thống mô phỏng trong trường học, thì họ có thể truy cập tới hệ thống này từ nhà hoặc từ bất cứ nơi nào khác. Mô phỏng một cách có điều khiển (Control animation): Người dùng có thể tự tạo tập dữ liệu của chính mình khi sử dụng hệ thống mô phỏng. Trong khi các tập dữ liệu được cài đặt sẵn cũng có thể giúp đỡ sinh viên có những sự hiểu biết ban đầu, hệ thống nên có cả 2 tùy chọn này. Tương tác (Ineractivity): Hệ thống mô phỏng phải cung cấp được sự Tương tác giữa người dùng và hệ thống. Sự tương tác bao gồm: người dùng xem theo từng bước, hủy, chạy nhanh tới một bước mong muốn, hay xem lại từ đầu, ... Lịch sử (History): Hệ thống mô phỏng cho phép người dùng xem lại các bước trước trong quá trình thực hiện. Phản hồi (Feedback): Phải tiếp thu phản hồi của sinh viên về việc sử dụng hệ thống mô phỏng để ước lượng hiệu quả của hệ thống cũng như để cải thiện hệ thống. 3.4. Một số yêu cầu đối với mô phỏng thuật toán - Phản ánh đúng nội dung thuật toán : Thuật toán được đưa ra mô phỏng phải chính xác, các bước thực hiện thuật toán phải trực quan và phản ánh đúng theo nội dung thuật toán đã đưa ra để đảm bảo tính đúng đắn của thuật toán. Hệ thống mô phỏng phải được thực hiện theo từng bước : thuật toán thường là trừu tượng, nếu để chương trình chạy tự động thì người dùng sẽ khó hiểu. Vì vậy, cần phải có chế độ thực hiện mô phỏng thuật toán theo từng bước, để người học có thể quan sát, theo dõi sự thay đổi giá trị của từng biến. Nhờ đó, sẽ giúp cho người học hiểu thuật toán rõ hơn và nhanh hơn. Mô tả thuật toán phải có tính động: để mô tả trực quan hóa quá trình thực hiện của thuật toán ta nên đưa vào hình ảnh động (có thể có âm thanh) để thể hiện sự thay đổi của dữ liệu trong quá trình thực thi. Ví dụ như, trong thuật toán tìm cây khung nhỏ nhất - thuật toán Prim, ta đưa vào các đối tượng đồ họa là đỉnh, cạnh. Trong quá trình thực thi thuật toán thì các đỉnh/cạnh được chọn sẽ sáng nhấp nháy và đổi màu, sau khi được chọn thì các đỉnh/cạnh sẽ được tô màu khác với màu ban đầu. Tương ứng với quan sát sự thay đổi trên đồ thị, ta có thể đưa vào đoạn thuật toán thể hiện tương ứng và song song với quá trình duyệt trên đồ thị. Nhờ đó mà thuật toán được thể hiện một cách rõ nét, sinh động, trực quan. giúp người đọc dễ theo dõi, dễ hiểu thuật toán hơn. Thuật toán được thử nghiệm trong mọi trường hợp để đảm bảo thời gian thực hiện tốt nhất : một thuật toán được mô phỏng phải đảm bảo là thuật toán tốt, dễ hiểu và đúng đắn. Muốn vậy ta phải thử nghiệm trong các trường hợp dữ liệu ngẫu nhiên, tốt nhất, xấu nhất. Nếu thuật toán vẫn chạy tốt và trong một thời gian cho phép thì thuật toán mới hiệu quả. Ta không thể chấp nhận một thuật toán đúng mà thời gian chạy quá lớn. - Tạo ra các mức độ khác nhau cho người dùng: Đối tượng học thuật toán thường là các sinh viên. Họ có trình độ tiếp thu khác nhau, nên ta phải đưa ra nhiều chế độ thao tác khác nhau để người học được phép lựa chọn. 4. Tổng quan về đồ thị 4.1. Định nghĩa đồ thị Một đồ thị được hiểu là một bộ hai tập hợp hữu hạn: Tập hợp đỉnh và tập hợp cạnh nối các đỉnh này với nhau. Một đồ thị được mô tả hình thức như sau: G = (V, E) Trong đó V là tập các đỉnh (Vertices) và E là tập các cạnh (Edges). Như vậy có thể coi đồ thị là tập các cặp (u, v) với u và v là hai đỉnh của V. 4.2. Phân loại đồ thị Chúng ta 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). G được gọi là đơn đồ thị nếu giữa hai đỉnh u và v của V có nhiều nhất là một cạnh trong E nối từ u tới v. G được gọi là đa đồ thị nếu giữa hai đỉnh u và v của V có thể có nhiều hơn một cạnh trong E nối từ u tới v. 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 u, v 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. Chu trình của đồ thị: chu trình là một dãy cạnh kế tiếp khép kín sao cho mỗi đỉnh của đồ thị được đi qua không quá một lần. Chu trình được kí hiệu bởi việc đưa ra các cạnh và các đỉnh liên tiếp nhau trên chu trình. Chẳng hạn chu trình C đi qua các đỉnh p1, p2, …, pk và các cạnh e1, e2, …, ek thì ta viết C = (p1, e1, …, pk, ek, p1) Trong trường hợp đồ thị là đồ thị đơn, thì thay vì viết rõ các cạnh và các đỉnh, chu trình được xác định duy nhất qua việc gọi tên các đỉnh nó đi qua. Ví dụ chu trình C ở trên có thể viết thành: C = (p1, p2, …, pk, p1) Số cạnh của chu trình được gọi là độ dài của chu trình và thông thường hay kí hiệu là l(C). 4.3. Cây khung và cây khung nhỏ nhất - Cây là đồ thị vô hướng, liên thông, không có chu trình đơn. Đồ thị vô hướng không có chu trình đơn được gọi là một rừng (hợp của nhiều cây). Như vậy mỗi thành phần liên thông của một rừng là nhiều cây. - Cây khung: Cho G là một đơn đồ thị. Một cây được gọi là cây khung của G nếu nó là một đồ thị con của G và chứa tất cả các đỉnh của G. - Cây khung nhỏ nhất: Nói chung, ta có thể định nghĩa cây khung nhỏ nhất cho một đồ thị G như sau: Nếu mỗi cạnh eij = (vi, vj) có một trọng số cij, thì cây khung nhỏ nhất là một tập hợp các cạnh ký hiệu là Espan, sao cho: C = sum( cij | eij Î Espan ) là nhỏ nhất. 4.4. Các phương pháp biểu diễn đồ thị 4.4.1. Biểu diễn đồ thị bằng ma trận kề Giả sử G = (V, E) là một đơn đồ thị có số đỉnh (kí hiệu |V| là n), không mất tính tổng quát, có thể coi các đỉnh được đánh số 1, 2, …, n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông A = [aij] cấp n. Trong đó: aij = 1 nếu (i, j) Î E aij = 0 nếu (i, j) Ï E Quy ước aii = 0 với mọi i; Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có điều nếu như (i,j) là cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối giữa đỉnh i và j. Ví dụ: 4.4.2. Biểu diễn bằng ma trận liên thuộc Sử dụng ma trận (aij) có kích thước n x m với n là số đỉnh, m là số cạnh của đồ thị. Trước hết ta đánh số các đỉnh của đồ thị từ 1 đến n, còn các cạnh được đánh số từ 1 đến m. Ta gán cho aij giá trị bằng 0 nếu cạnh thứ j không chứa đỉnh i hoặc 1 nếu ngược lại. Ví dụ: 5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị 5.1. Phân tích hệ thống mô phỏng một số thuật toán đồ thị 5.1.1. Mục đích Hệ thống nhằm giúp cho quá trình học tập về cấu trúc dữ liệu và giải thuật được diễn ra một cách thuận lợi hơn. Cụ thể: giúp học sinh, sinh viên dễ hiểu, dễ nắm bắt được thuật toán, có thể hiểu chi tiết thuật toán làm gì và làm như thế nào. Hơn nữa, với ưu điểm là một trang Web nên người học có thể truy cập vào bất kì lúc nào, vào bất kì thời điểm nào. Như vậy người học có thể luyện tập vào bất kì lúc nào sau khi học bài trên lớp. 5.1.2. Đặc điểm Hiện nay, trên mạng cũng đã có khá nhiều trang Web làm về mô phỏng thuật toán, trong đó cũng có một số trang viết về mô phỏng thuật toán đồ thị. Nhưng hầu hết các trang Web đó là của nước ngoài nên chúng được viêt bằng tiếng Anh. Điều này gây khó khăn cho những người không thông thạo tiếng Anh và cả với những người mới học về cấu trúc dữ liệu và giải thuật. Hơn nữa hầu hết các trang đó chỉ giới thiệu thuật toán, sau đó trình chiếu mô phỏng các ví dụ mẫu. Điều này làm cho người học khó hiểu về thuật toán, không nhận biết được thuật toán làm cụ thể những gì, người dùng không thể xem lại các bước trước đó dẫn đến việc học thuật toán không hiệu quả. Một vấn đề nữa là các trang Web đó không kết hợp được việc mô phỏng và hiển thị code của thuật toán. Một số trang có kết hợp được cái đó nhưng hầu hết code thuật toán được viết bằng ngôn ngữ Java, yêu cầu người học phải có một trình độ nhất định thì mới có thể hiểu được thuật toán. Ở thời điểm hiện tại cũng đã có một số rất ít trang Web có giao diện thân thiện với người dùng, chúng vừa cho phép hiển thị đồ thị mẫu, một bên là giả mã của thuật toán, có thể thực hiện mô phỏng từng bước giúp người dùng có thể nắm bắt thuật toán dễ dàng hơn. Nhưng hệ thống đó còn hạn chế là không thể thực hiện quay lui được, sau khi mô phỏng xong một đồ thị, ta không thể thực hiện mô phỏng đối với một đồ thị mới. Ngày nay, với sự bùng nổ công nghệ Web, việc dạy và học không thể dừng lại ở phương pháp truyền thống mà còn kết hợp với trực quan sinh động. Và việc xây dựng một hệ thống mô phỏng thuật toán đồ thị khắc phục những nhược điểm của các hệ thống hiện tại là rất cần thiết. 5.1.3. Kết quả phân tích a. Tìm hiểu hệ thống hiện tại - Hiện tại chưa có Website nào bằng tiếng Việt. - Các mô phỏng thường tách rời với thuật toán, người dùng phải quay lại trang trước đó hoặc một trang khác để xem thuật toán, khó nhận biết hiện tại thuật toán đang chạy ở bước nào. Ví dụ: Hình vẽ mô phỏng thuật toán Prim - Một số hệ thống đã hiện thị thuật toán cùng với mô phỏng của nó nhưng hầu hết là hiển thị cả một đoạn code chương trình, mà hầu hết là viết bằng ngôn ngữ Java, C nên không thuận tiện. - Có một trang Web đã cho hiển thị đoạn code thuật toán bằng ngôn ngữ tựa Pascal kết hợp với mô phỏng, có thể vẽ đồ thị như ý mình muốn để mô phỏng nhưng lại không cho phép người dùng thực hiện từng bước một cách hoàn chỉnh, còn bị lỗi, không có hệ thống menu, không có hướng dẫn thực hiện gây khó khăn cho người sử dụng. b. Các cơ hội cải tiến Từ thực tế là em đã được tiếp xúc và học về cấu trúc dữ liệu và giải thuật, cùng với việc tìm hiểu ý kiến của các sinh viên khoá sau thì việc hiểu các cấu trúc dữ liệu và các thuật toán là rất khó và trừu tượng, nhất là với những thuật toán phức tạp. Việc hiểu và hình dung hoạt động của các thuật toán trên đồ thị lại càng vất vả hơn. Nhu cầu hiện tại của hầu hết những người học cũng như người dạy là việc dạy và học thuật toán được thuận lợi hơn. Như vậy cần có một hệ thống mô phỏng thuật toán hiệu quả, chạy đồng thời một bên là đồ thị, một bên là chương trình viết bằng giả mã. Từ đó phân tích những chức năng cần thiết, cơ bản của hệ thống mô phỏng để mọi người sử dụng có thể tiếp cận một cách dễ dàng. c. Hướng phát triển cho hệ thống mới Thông qua phân tích hệ thống hiện tại và xác định cơ hội cải tiến, hệ thống mới sẽ tạo ra những thay đổi đáng kể so với hệ thống hiện tại nhằm mang lại hiệu quả mong muốn, khắc phục những tồn tại vốn có. Hệ thống mới cho phép chạy đồng thời một bên là đồ thị mẫu, một bên là đoạn giả mã tương ứng. Có thể chạy từng bước để người dùng tiện theo dõi. Hệ thống mô phỏng có hệ thống menu, trợ giúp và các hiển thị trên màn hình đều bằng tiếng Việt. Ngoài ra hệ thống cho phép người dùng có thể vẽ một đồ thị theo ý và thực hiện mô phỏng với nó. 5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị 5.2.1. Màn hình nền của hệ thống mô phỏng Màn hình của hệ thống mô phỏng là một trang Web có giới thiệu tổng quan về các thuật toán đồ thị. Trên đó có trình mô phỏng không hiển thị ngay trên màn hình mà nó được kích hoạt từ một nút nhỏ trên trang Web đó. Sau khi kích hoạt nút đó thì màn hình riêng của trình mô phỏng (hay giao diện của chương trình mô phỏng) sẽ hiện ra. 5.2.2. Giao diện chính và các chức năng của trình mô phỏng Mỗi thành phần của giao diện chính đều thực hiện một chức năng của trình mô phỏng. Giao diện chính của trình mô phỏng thuật toán đồ thị là một màn hình được định dạng chuẩn, được phát triển với một hệ thống thực đơn (menu) tuỳ chọn chung để lựa chọn các chức năng như tạo một đồ thị mới, mở một đồ thị đã có, lựa chọn các thuật toán để thực hiện trên mô phỏng trên một đồ thị (gồm các thuật toán Prim, BFS, DFS và chọn thuật toán nào thì giả mã lệnh tương ứng sẽ thể hiện trên màn hình), ... Ngoài ra còn có tuỳ chọn “Trợ giúp” trong hệ thống thực đơn đó. Giao diện mô phỏng được thiết kế trên nền một Frame chuẩn gồm một thanh menuBar có các menu con, hai Panel là hai vùng để hiển thị: đồ thị dùng để thực hiện mô phỏng và giả mã của thuật toán viết bằng ngôn ngữ tựa Pascal. Thành phần tiếp theo là các nút có chức năng kích hoạt quá trình mô phỏng, gồm có: Nút “Chạy” là nút kích hoạt mô phỏng. Khi chọn nút lệnh này, thì chương trình sẽ thực hiện mô phỏng thuật toán đã chọn trên đồ thị mẫu đã có. Việc thực hiện mô phỏng diễn ra từ đầu đến cuối cho đến khi kết thúc thuật toán mà không dừng lại giữa chừng. Và nó cho ta kết quả cuối cùng. Trong quá trình mô phỏng, những thay đổi trên đồ thị mẫu tương đương với các bước của thuật toán bằng giả mã ở bên cạnh. Chạy đến bước nào của thuật toán thì giả mã lệnh sẽ được tô đậm và đổi màu. Đồng thời với quá trình đó là các cạnh và đỉnh của đồ thị được duyệt và được chọn tương ứng cũng sẽ được chiếu sáng và đổi màu. Nút “Từng bước” là nút cho phép người dùng thực hiện mô phỏng theo từng bước của thuật toán. Mỗi lần chọn nút này thì một bước của thuật toán được thực hiện, đến bước nào thì giả mã lệnh sẽ tô đậm và đổi màu và các đỉnh, cạnh được duyệt tương ứng bước đó sẽ được chiếu sáng và đổi màu. Nút này cho phép người dùng theo dõi việc thực hiện thuật toán một cách chậm, tỉ mỉ từng chi tiết. Nút “Kết thúc” cho phép người dùng dừng công việc mô phỏng bất kì lúc nào. Ngoài ra còn có các thành phần hiển thị khác như các chú thích của quá trình mô phỏng. Các chú thích này có tác dụng để hiển thị những thay đổi trong quá trình mô phỏng qua các bước. Ví dụ đối với mô phỏng thuật toán Prim, các thông tin cần hiển thị tại mỗi bước như đỉnh xuất phát, tổng trọng số nhỏ nhất lúc này là bao nhiêu, các đỉnh/cạnh được chọn là đỉnh/cạnh nào. 6. Cài đặt mô phỏng thuật toán đồ thị 6.1. Công cụ lập trình Báo cáo này sử dụng Java là ngôn ngữ để thực thi bởi vì nó hỗ trợ tốt cho giao diện người dùng và mô phỏng. Trong đó, đáng kể đến là một vài lý do của mô phỏng thuật toán: - Đầu tiên là việc làm cho việc hiểu thuật toán dễ dàng hơn. - Thứ hai là, vấn đề trực quan hóa đã giúp cho cả hai đối tượng, đó là người ứng dụng giải thuật và sinh viên học giải thuật hiểu chi tiết giải thuật. - Mô phỏng một thuật toán có thể khuyến khích người thiết kế vào việc tìm thấy những biến đổi mới của giải thuật. - Java là một ngôn ngữ hướng đối tượng, phân tán, thông dịch, mạnh mẽ, bảo mật và có cấu trúc độc lập - Chương trình Java có thể dịch và thực hiện trong mọi môi trường điều hành, miễn là ở đó có có chương trình thông dịch. Hiện nay có nhiều môi trường hỗ trợ để phát triển phần mềm với Java như: Visual J++, Borland JBuilder, JDK, IntelliJ IDEA 5.1,... Các chương trình ứng dụng độc lập Các chương trình ứng dụng nhúng Applet Các chương trình kết hợp cả hai loại trên 6.2. Cài đặt thuật toán Prim – tìm cây khung nhỏ nhất 6.2.1. Bài toán Input: G = (V, E) liên thông, n đỉnh, m cạnh. Hàm trọng số: φ : E → R+ Output: T = (V, E’) là cây bao trùm nhỏ nhất. 6.2.2. Ý tưởng thuật giải Thuật toán Prim là ứng dụng của thuật toán tìm kiếm theo chiều rộng với tư tưởng tham lam. Ở bước khởi tạo, một cây T được chọn đơn giản nhất với một đỉnh và không có cạnh nào. Trong mỗi bước của thuật toán ta luôn tìm cách bổ sung vào cây một cạnh (cùng với một đỉnh) có trọng số nhỏ nhất trong tất cả các cạnh có thể sao cho nó liên thông và nối một đỉnh nằm trong T với một đỉnh nằm ngoài T, do đó không làm phát sinh chu trình trong T. Thuật toán dừng lại khi tất cả các đỉnh được bổ sung vào cây T. Theo ngôn ngữ tự nhiên, ta có thể mô tả thuật toán như sau: Khởi tạo: chọn một đỉnh bất kì cho vào T. Chẳng hạn T = {s} Nếu còn có đỉnh chưa thuộc T, nhưng kề với một đỉnh trong T thì chọn cạnh có trọng số nhỏ nhất trong số đó cho vào T. Nếu không còn đỉnh nào như vậy thì dừng thuật toán. Ta dùng mảng Tree để lưu các cạnh được chọn. Giải thuật Prim được viết như sau: Procedure PrimAlgo (G: graph; var Tree: set of edges); Var T: set of Nodes; { tập hợp các đỉnh} u, v : Node; Begin Tree := Ø; T := [1]; While T < V do begin {V là tập hợp các đỉnh của G} gọi (u, v) là cạnh ngắn nhất sao cho u Î U và v Î V – U; T := T È [v]; Tree := Tree È [(u, v)]; end; End; Để lập trình, chúng ta phải sử dụng cấu trúc hàng đợi Q có ưu tiên theo tiêu chuẩn giá trị nhỏ nhất. 6.3. Cài đặt các lớp trong chương trình 6.3.1. Các lớp cơ sở Gồm có các class: Node, Edge, GraphCanvas. Node: gồm Gồm tọa độ x, y, và chỉ số no của đỉnh. Khi thuật toán thực thi thì nhãn được đưa vào cho mỗi node. Tại mỗi thời điểm để phân biệt rõ các bước chạy của thuật toán, ta tô màu cho các node. Mỗi node có 3 khả năng tô màu (màu xanh da trời cho node ban đầu, khi được xét đến thì node được tô màu xanh lá cây, khi đã được lựa chọn thì ta tô màu đỏ cho node đó). Edge (lớp thể hiện một cạnh của đồ thị - dùng trong lưa trữ và vẽ đồ thị): Mỗi cạnh được xác định gồm node đầu, node cuối, trọng số của cạnh, màu của cạnh. Khi chạy thuật toán thì các cạnh được tô màu và nhấp nháy sáng. Một cạnh cũng được gán một màu tại mỗi bước thực thi thuật toán, cạnh ban đầu có màu đen, khi được xét cạnh đó sẽ nhấp nháy và chuyển sang màu xanh lá cây, được lựa chọn thì cạnh nhấp nháy và có màu đỏ. GraphCanvas: dùng để vẽ đồ thị. Cụ thể là vẽ các node, các Edge, và sinh đồ thị tổng hợp. Đồng thời hiển thị đồ thị lên Panel. 6.3.2. Lớp Prim Dùng để hiển thị giả mã, đồng thời có các hàm PrimSolve(): void được gọi đến khi kích chọn nút “Chạy” để thực hiện giải thuật Prim tự động và PrimStep(): void được gọi đến khi kích chọn nút “Từng bước” để thực hiện mô phỏng theo từng bước một. Trong lớp này có hàm extractMin(): int dùng để lấy ra cạnh có trọng số nhỏ nhất trong tất cả các cạnh đang chờ được xét. 6.3.3. Lớp Main Dùng để tạo một Applet trên trình duyệt có hỗ trợ Java. Đồng thời cũng là lớp thiết kế màn hình chính của chương trình mô phỏng. Lớp được xây dựng kế thừa từ lớp Applet của gói java.applet. Trong lớp này có sử dụng các gói: import java.applet.Applet; import java.awt.*; import java.awt.event.*; để xây dựng Panel vẽ đồ thị, thực hiện mô phỏng và thể hiện các chú thích cần thiết. 7. Kết luận Báo cáo đã trình bày một cách khá tổng quan về mô phỏng thuật toán, các đặc trưng cơ bản của thuật toán đồ thị và các kỹ thuật lập trình hướng đối tượng với Java để thiết kế chương trình sử dụng giả mã mô phỏng một số thuật toán đồ thị. Trên cơ sở phân tích các đặc trưng của mô phỏng thuật toán, các thuật toán đồ thị, kỹ thuật lập trình Java, báo cáo đã tập trung vào việc phân tích các hệ thống mô phỏng có trên Website hiện nay, từ đó tìm cách áp dụng kỹ thuật lập trình Java để xây dựng hệ thống mô phỏng một số thuật toán đồ thị bằng Tiếng Việt để có thể mang lại nhiều tiện ích cho người dùng, giúp họ dễ hiểu và dễ sử dụng thuật toán. Do thời gian có hạn nên đến thời điểm nộp báo cáo, sản phẩm demo của chương trình chưa hoàn thành một cách trọn vẹn. Trong thời gian tới em hi vọng nhận được sự đóng góp ý kiến của thầy cô và các bạn để em có thể hoàn thành tốt chương trình của mình. 8. Hướng phát triển - Hoàn thành sản phẩm “chương trình mô phỏng một số thuật toán đồ thị” một cách trọn vẹn. - Cài đặt hoàn chỉnh các thuật toán đồ thị đã nêu. - Mở rộng hệ thống mô phỏng: cài đặt thêm các thuật toán về đồ thị như tìm đường một nét Euler, thuật toán liệt kê tất cả các chu trình Haminton của đồ thị, thuật toán mã hoá Huffman. - Phát triển hệ thống: triển khai hệ thống trong thực tế. Tài liệu tham khảo Đoàn Văn Ban, Lập trình hướng đối tượng với Java, NXB khoa học và kỹ thuật, 2005. Vũ Đình Hòa, Giáo trình Lí thuyết đồ thị, NXB Đại học sư phạm, 2007. Thomas H. Cormen Charles E. Leiserson Ronald Rivest, chủ biên Ngọc Anh Thư, Giáo trình thuật toán, Nhà xuất bản thống kê, 2002 Burgiel, H. & Raymond, M. (2004), Simple N-gon Counter, www.math. uiuc.edu/~burgiel/Java/Ngons/ (accessed Nov 2004).