- NGUYỄTHỊ KIM 88 ỀN THÔC SĨ OÁN CÂYỄN ĐỨC NHƯƠNGÔNG Y NGHĨA G 1 Lý do chọn đề tài Bài toán Xây dựng cây khung chi phí lộ trình nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCT) là một trong các bài toán quen thuộc trong lĩnh vực thiết kế mạng. - Kết quả của bài toán có thể được áp dụng rất nhiều trong việc xây dựng các hệ thống mạng nhằm tối ưu chi phí đường đi trung bình giữa các nút mạng, đặc biệt là ở các mạng ngang hàng khi các nút có xác suất truyền tin, độ ưu tiên là như nhau. - Bài toán đã được chứng minh là thuộc lớp NP-hard nên vì thế cho đến nay người ta vẫn chưa tìm được một thuật giải có độ phức tạp đa thức cho bài toán này. - Các phương pháp được đưa ra chủ yếu là sử dụng các thuật toán đánh giá xấp xỉ với những cận dưới về độ tốt của kết quả. - Gần đây một phương pháp đang nổi lên và thu hút được nhiều chú ý trong việc giải quyết các bài toán tối ưu là hệ thống giải thuật bầy kiến (Ant Colony Optimization). - Giải thuật này mô phỏng hành vi của kiến dò đường trong tự nhiên để tạo ra các kiến nhân tạo với những hành vi tương tự nhằm áp dụng cho các bài toán tối ưu. - Trong đồ án này chúng ta sẽ trình bày về nghiên cứu áp dụng giải thuật kiến nhằm giải quyết bài toán MRCT và so sánh kết quả thu được với một số phương pháp trước đây. - Bên cạnh đó, chúng ta còn tiến hành phân tích những khía cạnh của giải thuật kiến trong bài toán MRCT. - Mục đích nghiên cứu của luận văn + Hiểu bài toán cây khung chi phí lộ trình nhỏ nhất. - Hiểu thuật toán bày kiến + Phát triển thuật toán bày kiến giải bài toán cây khung chi phí lộ trình nhỏ nhất. - Nội dung chính của luận văn Chương 1: Giới thiệu bài toán cây khung chi phí lộ trình nhỏ nhất. - Chương này giới thiệu bài toán cây khung chi phí lộ trình nhỏ nhất và ứng dụng của nó. - Đồng thời, chương này cũng trình bày một cách tổng quan về các hướng tiếp cận cũng như các thuật toán được biết đến hiện nay để giải giải quyết bài toán. - Chương này trình bày các cơ sở lý thuyết về đồ thị, cây khung của đồ thị và thuật toán bày kiến. - Chương 3: Giải thuật kiến cho bài toán cây khung chi phí lộ trình nhỏ nhất. - Chương này trình bày nội dung của thuật toán bày kiến để giải bài toán cây khung chi phí lộ trình nhỏ nhất, xác định hàm dò đường của kiến, các thông số. - Chương 4: Cài đặt và thử nghiệm Chương này mô tả về chương trình cài đặt và kết quả thử nghiệm của chương trình. - Phần thử nghiệm trình bày kết quả thử nghiệm cho việc xác định các thông số. - Và sau đó trình bày kết quả thử nghiệm trên các bộ dữ liệu Ơclit với các thông số. - Kết luận Bài toán MRCT là một trong các bài toán NP-hard kinh điển hiện nay tuy nhiên nó lại không nhận được nhiều chú ý từ các nhà nghiên cứu do tính chất phức tạp của việc xây dựng các hàm heuristic và phương pháp tiếp cận. - Các thuật toán hiện nay chủ yếu là các thuật toán xấp xỉ được chứng minh rằng kết quả cho ra sẽ không vượt trước (1. - Với việc chúng ta áp dụng khá thành công thuật toán MMAS cho bài toán MRCT đã phần nào cho thấy đây có thể là một phương pháp đúng đắn trong việc tiếp cận bài toán MRCT. - Mặc dù kết quả của thuật toán chúng ta đề xuất ra đã khá tốt tuy nhiên có thể còn cải tiến được hơn nữa bởi như kết quả thử nghiệm, thuật toán của chúng ta tỏ ra hiệu quả hơn thuật toán của Wong nhưng lại không tốt bằng thuật toán ABC, và khi số lượng đỉnh và số lượng cạnh của đồ thị khá lớn, thuật toán của chúng ta tỏ ra không hiệu quả.Trong tương lai chúng ta sẽ nghiên cứu kỹ lưỡng hơn vấn đề này và cải tiến hơn nữa hàm heuristic để có thể cho ra các chiến lược tìm kiếm tối ưu hơn.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt