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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN 1
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN 2
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
3
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
4
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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,
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
5
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
6
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN 7
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ị
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
8
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ 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:
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
9
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ụ:
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
10
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
11
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ụ:
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
12
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
13
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ó:
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
14
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị - 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.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
15
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị - 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:
1. Khởi tạo: chọn một đỉnh bất kì cho vào T. Chẳng hạn T = {s}
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
16
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 2. 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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
17
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
18
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị 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ế.
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
19
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
Tài liệu tham khảo
1. Đ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.
2. Vũ Đình Hòa, Giáo trình Lí thuyết đồ thị, NXB Đại học sư phạm, 2007.
3. 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
4. Burgiel, H. & Raymond, M. (2004), Simple N-gon Counter, www.math.
uiuc.edu/~burgiel/Java/Ngons/ (accessed Nov 2004).
5. http://www.cs.duke.edu/csed/jawaa2/
6. http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Prim.shtml
7. http://students.ceid.upatras.gr/~papagel/project/prim.htm
8. http://students.ceid.upatras.gr/~papagel/project/adjoin.htm
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
20
