Cây khung nhỏ nhất: Tìm kiếm bằng giải thuật Prim (Đề tài)

Đề 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í

SVTH: Huỳnh Hải Đăng Trang 1/17

ĐÁ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

Nguy

ễn Th

ành Quí

001945

SINH VIÊN THỰC HIỆN :

STT HỌ VÀ TÊN MSSV THƯỞNG

ối đa 1 điểm)

ĐIỂM

1 Huỳnh Hải Đăng 1081642

I. HÌNH THỨC

(

ố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

ố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

ối đa 0,5 điểm)

 Các khái niệm sử dụng trong đề tài



ế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)



ớ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

(

ố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

Đề 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í

SVTH: Huỳnh Hải Đăng Trang 2/17

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à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í

SVTH: Huỳnh Hải Đăng Trang 3/17

    

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

Đề 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í

SVTH: Huỳnh Hải Đăng Trang 4/17

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.

Đề 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í

SVTH: Huỳnh Hải Đăng Trang 5/17

- 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 tốn

mẫu trên giấy

- Phân tích giải

bài tố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

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

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi