Download miễn phí Đề tài Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
MỤC LỤC
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
http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-01-07-de_tai_tim_cay_khung_co_trong_luong_nho_nhat_bang.NUWV86Ys3v.swf /tai-lieu/de-tai-ung-dung-tren-liketly-53861/Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ĐÁ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
MSSV
THƯỞNG
(Tối đa 1 điểm)
ĐIỂM
1
Huỳnh Hải Đăng
1081642
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 toá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 toá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
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
&
TỔNG QUAN
@&
Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài toán tối ưu có nhiều ứng dụng trong thực tế. Nó là bài toán tìm hệ thống liên thông với chi phí nhỏ nhất. Hai thuật toán tìm cây bao trùm nhỏ nhất thường được nhắc đến là thuật toán Prim và thuật toán Krusskal.
Cho G=(X,E) là một đồ thị liên thông. Ngoà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 toá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 toá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 toá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à toá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ề toá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à toán học Vojtěch Jarník và do Prim hoà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
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.
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.
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 ngoài T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T.
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.
- 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
- Tìm kiếm tài liệu
- Giải bài toán mẫu trên giấy
- Phân tích giải bài toán bằng ngôn ngử giả
- Cài đặt các cấu trúc dữ liệu cần thiết và 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
- Cải tiến chương trình chạy trên chế độ đồ 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.
- Viết báo cáo
LÝ THUYẾT
&
I. Các khái niệm chính.
Một đồ thị G bao gồm một tập hợp V các đỉnh và một tập hợp E các cạnh, ký hiệu G=(V,E).
Các đỉnh còn được gọi là nút (node) hay điểm (point). Các cạnh nối giữa hai đỉnh, hai đỉnh này có thể trùng nhau.
Đồ thị được gọi là liên thông nếu với mõi cặp cạnh i,j bất ky luôn tìm được đường đi nối i với j.
Hai đỉnh có cạnh nối nhau gọi là hai đỉnh kề (adjacency). Một cạnh nối giữa hai đỉnh v, w có thể coi như là một cặp điểm (v,w).
Nếu các cạnh trong đồ thị G có thứ tự thì G gọi là đồ thị có hướng (directed graph).
Nếu các cạnh trong đồ thị G không có thứ tự thì đồ thị G là đồ thị vô hướng (undirected graph).
Đường đi trong đồ thị là một dãy các đỉnh:
sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là: " " i = 2, 3, … , k-1, k : (xi-1, xi) Î E.
Ta nói rằng đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk. Số cạnh của đường đi được gọi là độ dài của đường đi đó.
Đường đi đơn là đường đi mà các đỉnh trên nó khác nhau từng đôi.
Đồ thị ...
