Hướng dẫn tạo chương tình mô phỏng thuật toán dijktra năm 2024
Hôm nay mình xin gửi đến các bạn đang học môn cấu trúc dữ liệu và giải thuật (CTDL>) một công cụ rất là hay ho mà hồi trươc mình cũng có dùng để mô phỏng các thuật toán trông rất trực quan và dễ tiêu hóa. Visualization Tool là một công cụ mô phỏng thuật toán được phát triển bởi David Galles. Ông này là phó giáo sư của trường một trường đại học nào đó ở San Francisco quên rồi :). Không cần quan tâm nhiều ổng là ai, quan trọng là ổng đã tạo ra một công cụ rất bổ ích giúp rất nhiều cho sinh viên tìm hiểu giải thuật. Sau đây, mình xin chỉ ra một số tính năng của công cụ: Giao diện chương trình Công cụ có thể chạy hầu hết các thuật toán phổ biến như: danh sách liên kết, ngăn xếp, hàng đợi, các thuật toán sắp xếp, tạo cây nhị phân, các thuật toán lý thuyết đồ thị, bảng băm, nén huffman, fibonaci… - Xây dựng chương trình mô phỏng cụ thể một số thuật toán trên đồ thị gồm: -Thuật toán tìm kiếmtheo chiều sâu DFS. -Thuật toán tìm kiếm theo chiều rộng BFS. -Thuật toán tìm đường đi ngắn nhất –thuật toán Ford -Bellman. -Thuật toán tìm đường đi ngắn nhất –thuật toán Dijkstra. -Thuật toán tìm cây khung nhỏ nhất trên đồ thị vô hướng có trọng số -thuật toán Prim. -Thuật toán tìm cây khung nhỏ nhất trên đồ thị vô hướng có trọng số -thuật toán Kruskal. -Thuật toán tìm chu trình Hamilton qua tất cả các đỉnh của đồ thị. Bạn đang xem trước 20 trang tài liệu Luận văn Mô phỏng một số thuật toán trên đồ thị, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên 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 |