Đề tài: Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim

Đề Tài:Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim GVHD: Nguyễn Thành Quí ĐÁNH GIÁ KẾT QUẢ THỰC HIỆN NIÊN LUẬN 1 (Học kỳ II, Niên khóa 2008-2009) GIÁO VIÊN HƯỚNG DẪN : STT HỌ VÀ TÊN MSCB 1 Nguyễn Thành Quí 001945 SINH VIÊN THỰC HIỆN : STT HỌ VÀ TÊN 1 Huỳnh Hải Đăng MSSV 1081642 THƯỞNG ĐIỂM (Tối đa 1 điểm) I. HÌNH THỨC( Tối đa 0,5 điểm) Bìa (tối đa 0,25 điểm)  Các tiêu đề : Trường ĐHCT, Khoa CNTT, Bộ môn  Các niên luận : 1  Tên đề tài  Giáo viên hướng dẫn : chức danh, họ tên  Thông tin về sinh viên thực hiện : họ tên, mã số, lớp  Năm thực hiện Bố cục (tối đa 0,25 điểm)  Nhận xét của giáo viên hướng dẫn và giáo viên chấm  Mục lục : cấu trúc chương, mục và tiểu mục  Phụ lục (nếu có)  Tài liệu tham khảo II. NỘI DUNG (Tối đa 3,5 điểm) Tổng Quan (tối đa 0,5 điểm)  Mô tả bài tốn, mục tiêu cần đạt được (0,25 điểm)  Hướng giải quyết và kế hoạch thực hiện (0,25 điểm) Lý thuyết (tối đa 0,5 điểm)  Các khái niệm sử dụng trong đề tài  Kết quả vận dụng lý thuyết trong đề tài Ứng dụng (tối đa 2,0 điểm)  Phân tích yêu cầu bài tốn, xây dựng các cấu trúc dữ liệu cần thiết (0,5 điểm)  Giải thuật (Lưu đồ - Ngôn ngữ giả ) (1,0 điểm)  Giới thiệu chương trình (0,5 điểm) Kết luận (tối đa 0,5 điểm)  Nhận xét kết quả đạt được  Hạn chế  Hướng phát triển III. CHƯƠNG TRÌNH DEMO (Tối đa 5,0) Giao diện thân thiện với người dùng (tối đa 1,0 điểm) Hướng dẫn sử dụng (0,5 điểm) Kết quả thực hiện đúng với kết quả cảu phần ứng dụng (3,5 điểm) Cần Thơ, ngày 4 tháng 4 năm 2010 GIÁO VIÊN HƯỚNG DẪN SVTH: Huỳnh Hải Đăng Trang 1/17 Đề Tài:Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim GVHD: Nguyễn Thành Quí NHẬN XÉT CỦA GIÁO VIÊN      ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Cần Thơ, ngày….. tháng ...... năm ...... Giáo viên hướng dẫn MỤC LỤC SVTH: Huỳnh Hải Đăng Trang 2/17 Đề Tài:Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim GVHD: Nguyễn Thành Quí      NHẬN XÉT CỦA GIÁO VIÊN ................................................................................................. 2 MỤC LỤC ................................................................................................................................. 3 TỔNG QUAN............................................................................................................................ 4 I. Các mục tiêu cần đạt được ................................................................................................... 4 II. Hướng giải quyết ............................................................................................................... 4 III. Kế họach thực hiện........................................................................................................... 5 LÝ THUYẾT ............................................................................................................................. 6 I. Các khái niệm chính............................................................................................................ 6 II. Các cách biểu diễn đồ thị................................................................................................... 7 III. Duyệt các đỉnh của đồ thị.................................................................................................. 8 IV .Giải thuật Prim................................................................................................................. 8 Ứng Dụng.................................................................................................................................10 I. Lưu đồ giải thuật Prim........................................................................................................10 II. Lưu đồ duyệt cây theo chiều sâu tại đỉnh i .........................................................................11 III. Lưu đồ duyệt cây theo chiều rộng tại đỉnh i .....................................................................11 IV. Giới thiệu chương trình ................................................................................................... 12 KẾT LUẬN- ĐÁNH GIÁ.........................................................................................................16 I. Kết quả đạt được ................................................................................................................16 II. Hạn chế của chương trình..................................................................................................16 III. Hướng phát triển..............................................................................................................16 PHỤ LỤC.................................................................................................................................17 Hướng dẫn sử dụng ...............................................................................................................17 Các tài liệu tham khảo...............................................................................................................17 SVTH: Huỳnh Hải Đăng Trang 3/17 Đề Tài:Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim GVHD: Nguyễn Thành Quí TỔNG QUAN  Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài tốn tối ưu có nhiều ứng dụng trong thực tế. Nó là bài tốn tìm hệ thống liên thông với chi phí nhỏ nhất. Hai thuật tốn tìm cây bao trùm nhỏ nhất thường được nhắc đến là thuật tốn Prim và thuật tốn Krusskal. Cho G=(X,E) là một đồ thị liên thông. Ngồi ra, một hàm trọng số W(e), xác định trên tập các cạnh E của G. Cả hai thuật tốn Prim và Kruskal đều dựa trên tư tưởng của các giải thuật tham ăn : Ở mỗi bước của thuật tốn ta chọn và bổ sung vào cây cạnh có trọng số nhỏ nhất có thể. Ở đây ta chỉ đề cập đến thuật tốn Prim Giải thuật Prim Vài nét về R. C. Prim Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà tốn học và khoa học máy tính Mỹ. Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông nhận bằng Ph.D. về tốn học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi nhà tốn học Vojtěch Jarník và do Prim hồn thiện vào năm 1957. asd Mô tả Gọi T là cây bao trùm sẽ xây dựng 1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào. 2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc. 3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngồi T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T. 4. Quay lại 2. I. Các mục tiêu cần đạt được: - Dữ liệu được nhập từ bàn phím là một ma trận trọng số. - Thiết kế giải thuật Prim và xuất ra màn hình cây khung có trọng lượng nhỏ nhất. II. Hướng giải quyết: - Viết chương trình nhập vào 1 ma trận trọng số. - Sử dụng giải thuật Prim để tìm được cây khung có trọng lượng nhỏ nhất. SVTH: Huỳnh Hải Đăng Trang 4/17 Đề Tài:Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim GVHD: Nguyễn Thành Quí - Xuất ra màn hình đồ họa các bước trong trong giải thuật Prim. III. Kế hoạch thực hiện Tuần 1 Tuần 2 Tuần 3 Tuần 4 - Phân tích yêu cầu - Cài đặt các cấu trúc dữ liệu cần thiết và - Cải tiến chương - Viết báo cáo trình chạy trên chế - Tìm kiếm tài liệu - Giải bài tốn mẫu trên giấy - Phân tích giải bài tốn bằng ngôn ngử giả kiểm tra tính đúng đắn của chúng - Viết chương trình chạy trên chế độ text. - Kiểm tra tính đúng đắn của chương trình độ đồ họa - Kiểm tra vét cạn tất cả các trường hợp. - Cải tiến để chương trình có thể chịu được các sai xót ở khâu nhập liệu. SVTH: Huỳnh Hải Đăng Trang 5/17 ... - tailieumienphi.vn