ĐỀ TÀI: CÂy bao trùm nhỏ nhất học viên thực hiệN
tải về 0.76 Mb.
|
ATHTTT DDOS
- Điều hướng trang này:
- 2. Nguyễn Văn Bảy MSHV: 2184801011008 LỚP: MCOM021A HƯỚNG DẪN KHOA HỌC: PGS. TS. Nguyễn Hòa TP. HỒ CHÍ MINH, NĂM 2022 MỤC LỤC
|
TRƯỜNG ĐẠI HỌC MỞ THÀNH PHỐ HỒ CHÍ MINH KHOA ĐÀO TẠO SAU ĐẠI HỌC oOo TIỂU LUẬN PHÂN TÍCH THIẾT KẾ THUẬT TOÁN NÂNG CAO ĐỀ TÀI: CÂY BAO TRÙM NHỎ NHẤT HỌC VIÊN THỰC HIỆN 1. Hồ Minh Duy MSHV: 2184801011009 2. Nguyễn Văn Bảy MSHV: 2184801011008 LỚP: MCOM021A HƯỚNG DẪN KHOA HỌC: PGS. TS. Nguyễn Hòa TP. HỒ CHÍ MINH, NĂM 2022 MỤC LỤC 1.Giới thiệu bài toán 3 2.Cơ sở lý thuyết 5 3.Các thuật toán tìm MST 7 Giới thiệu bài toánBài toán cây bao trùm (cây khung) nhỏ nhất, tiếng Anh gọi là Minimum Spanning Tree (MST) của đồ thị, là một trong số những bài toán tối ưu trên đồ thị, có nhiều ứng dụng khác nhau trong đời sống. Để minh họa thuật toán, chúng ta tham khảo một vài mô hình thực tế tiêu biểu của bài toán: Ví dụ đầu tiên là bài toán xây dựng đường giao thông (Hình 1): giả sử ta muốn xây dựng một hệ thống đường nối n thành phố, sao cho giữa các thành phố bất kì luôn có đường đi. Bài toán đặt ra là tìm MST trên đồ thị, mỗi thành phố ứng với một đỉnh sao cho tổng chi phí xây dựng đường đi là nhỏ nhất. Hình 1: Minh họa bài toán xây dựng đường giao thông1 Ở một ví dụ khác là bài toán nối mạng máy tính (Hình 2): một công ty A cần nối mạng một hệ thống gồm n máy tính đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là c[i, j], i, j = 1, 2, . . . , n (thông thường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Công ty này yêu cầu tìm cách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất. Hình 2: Minh họa hệ thống mạng máy tính2 MST là một trong những vấn đề tổ hợp được nghiên cứu nhiều nhất với các ứng dụng thực tế trong bố cục tích hợp quy mô rất lớn VLSI (Very Large Scale Integrated), truyền thông không dây và mạng phân tán. Nói đến ứng dụng trực tiếp của MST trong thiết kế mạng, nó được sử dụng trong các thuật toán xấp xỉ, như bài toán nhân viên bán hàng đi du lịch, bài toán cắt giảm tối thiểu đa thiết bị đầu cuối và đối sánh hoàn hảo có trọng số chi phí tối thiểu. Các ứng dụng thực tế khác là: phân tích Cluster; nhận dạng chữ viết; phân đoạn hình ảnh. Các vấn đề gần đây trong sinh học và y học như phát hiện ung thư, hình ảnh y tế và Proteomics, An ninh quốc gia cùng khủng bố sinh học, chẳng hạn như phát hiện sự lây lan của chất độc qua các quần thể, … cũng ứng dụng MST để hỗ trợ rất nhiều. Đó là một vài ví dụ điển hình cho việc ứng dụng cây bao trùm nhỏ nhất vào đời sống, như vậy câu hỏi đặt ra là cần có giải thuật nào tối ưu cách thức chọn ra được đường đi ngắn nhất, với chi phí được tối thiểu hóa? Tiểu luận này sẽ tiến hành nghiên cứu các thuật toán và có những hình thức so sánh để nói lên ưu nhược điểm của từng chuyên gia, mà họ đã từng đề xuất ra lời giải cho bài toán này. tải về 0.76 Mb. Chia sẻ với bạn bè của bạn:
|