Ứ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ư An

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.

Toàn văn:

PDF

Các tài liệu tham khảo


Dantzig, G., Fulkerson, D., & Johnson, S. (1954). Solution of large-scale traveling salesman problem. Journal of the Operations Research Society of America, 10(3), 393-410.

Ding, Z. D. (2001). Theory of computational complexity. New Jersey, USA: Wiley-Interscience.

Korter, B., & Vygen, J. (2002). Combinatorial optimization: Theory and algorithms. Berlin,Gemany: Springer.

Lawler, E. L., & Lenstra, J. K. (1985). The traveling salesman problem. New Jersey, USA: John Wiley & Sons.




DOI: http://dx.doi.org/10.37569/DalatUniversity.7.2.239(2017)

Các bài báo tham chiếu

  • Hiện tại không có bài báo tham chiếu.


Copyright (c) 2017 Đỗ Như An

Creative Commons License
Công trình này được cấp phép theo Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Văn phòng Tạp chí Đại học Đà Lạt
Nhà A25 - Số 1 Phù Đổng Thiên Vương, Đà Lạt, Lâm Đồng
Email: tapchikhoahoc@dlu.edu.vn - Điện thoại: (+84) 263 3 555 131

Creative Commons License
Trên nền tảng Open Journal Systems
Thực hiện bởi Khoa Công nghệ Thông tin