tailieunhanh - Ứng dụng thuật toán nhánh cận để giải một số bài toán tối ưu liên quan đến chu trình Hamilton dựa trên bài toán TSP

Bài báo này trình bày cách vận dụng thuật toán nhánh cận để giải một số bài toán tối ưu liên quan đến chu trình Hamilton dựa trên bài toán TSP tương ứng. | TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT Tập 7, Số 2, 2017 205–216 205 ỨNG DỤNG THUẬT TOÁN NHÁNH CẬN ĐỂ GIẢI MỘT SỐ BÀI TOÁN TỐI ƯU LIÊN QUAN ĐẾN CHU TRÌNH HAMILTON DỰA TRÊN BÀI TOÁN TSP Đỗ Như Ana* Khoa Công nghệ Thông tin, Trường Đại học Nha Trang, Khánh Hoà, Việt Nam a Lịch sử bài báo Nhận ngày 05 tháng 01 năm 2017 | Chỉnh sửa ngày 08 tháng 04 năm 2017 Chấp nhận đăng ngày 10 tháng 05 năm 2017 Tóm tắt Bài toán người du lịch (Traveling Salesman Problem, viết tắt TSP) là một trong những bài toán tối ưu tổ hợp nổi bật thuộc lớp NP-khó. Thuật toán tốt nhất hiện nay để giải TSP là thuật toán nhánh-cận có độ phức tạp thời gian tính toán dạng hàm mũ. Bài báo này trình bày cách vận dụng thuật toán nhánh-cận để giải một số bài toán tối ưu liên quan đến chu trình Hamilton dựa trên bài toán TSP tương ứng. Từ khóa: Bài toán người du lịch; Bài toán tối ưu tổ hợp; Chu trình Hamilton; Đường Hamilton; NP-đầy đủ; NP-khó; Thuật toán nhánh-cận. 1. GIỚI THIỆU Phần này trình bày một số khái niệm và kiến thức cơ bản của lý thuyết đồ thị liên quan đến bài toán người du lịch và thuật toán nhánh-cận giải TSP. Nội dung của phần này chủ yếu được tham khảo trong tài liệu Combinatorial Optimization: Theory and Algorithms của Korter và Vygen (2002), và tài liệu The Traveling Salesman Problem của Lawler và Lenstra (1985). Không giảm tính tổng quát, trong phần này chúng tôi không mô tả chi tiết quá trình tính toán của thuật toán nhánh-cận cho TSP, kết quả của thuật toán được xác định dễ dàng và chính xác thông qua các ví dụ minh họa đơn giản. Một số kết quả cơ bản của lý thuyết NP-đầy đủ được tham khảo tại tài liệu Theory of computational complexity của Ding (2001). * Tác giả liên hệ: Email: andn@ 206 . TẠP CHÍ KHOA HỌC ĐẠI HỌC ĐÀ LẠT [ĐẶC SAN CÔNG NGHỆ THÔNG TIN] Đường Hamilton và chu trình Hamilton Xét đồ thị có hướng G (V , E) , trong đó V là tập các đỉnh, E là tập các cung. Một hành trình (walk) trong G là một dãy W v0 e1v1e2 .,el vl , trong đó v0 , v1 ,.,vl là các

• Toán học
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Chu trình Hamilton
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Tóm tắt luận văn Thạc sĩ Kỹ thuật
• Tìm hiểu bài toán người du lịch
• Thuật toán tối ưu đàn kiến ACO
• Luận văn Thạc sĩ Kỹ thuật
• Thuật toán ACO vào bài toán người du lịch
• Bài giảng Toán rời rạc
• Toán rời rạc
• Tài liệu Toán rời rạc
• Phân tích bài toán người du lịch
• Người du lịch
• Phân tích thuật toán
• Thiết kế thuật toán
• Giải thuật toán
• Bài tập giải thuật
• Cài đặt thuật toán
• Thuật toán di truyền
• Giải thuật di truyền
• Công nghệ thông tin
• Ứng dụng thuật toán di truyền
• Khoa học máy tính
• Giải thuật toán di truyền
• Giải thuật toán tối ưu hóa
• Thuật toán tìm kiếm
• Giải thuật tìm kiếm
• Giải thuật di truyền
• Davis' Order Crossover
• Giải quyết bài toán TSP
• Thiết kế vi mạch
• Bài toán tối ưu
• Bài toán tổng quát
• Bài toán cái túi
• Bài toán đóng thùng
• Giải thuật meta heuristic
• Tối ưu hóa tổ hợp
• Giải thuật tìm kiếm cục bộ
• Lý thuyết khoa học máy tính
• Bài giảng Bài toán tối ưu tổ hợp
• Thuật toán Johnson
• Toán kinh tế
• Phân tích thiết kế giải thuật
• Thuật toán tham lam
• Bài toán đường đi ngắn nhất
• Bài toán cây bao trùm nhỏ nhất
• Bài toán tô màu
• Bài toán các khoảng không giao nhau
• Phương pháp nhánh cận
• Bài toán về Phương pháp nhánh cận
• Meta heuristic
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Nguyên lý heuristic
• tài liệu về heuristic
• ứng dụng heuristic
• bài toán phân công công việc
• Trí tuệ nhân tạo
• Lập trình tiến hóa
• Cấu trúc dữ liệu
• Thuật giải di truyền
• Tối ưu số
• Tối ưu tổ hợp