Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tìm kiếm cục bộ trong các vấn đề định tuyến có khoảng thời gian
Tóm tắt
Chúng tôi phát triển các thuật toán tìm kiếm cục bộ cho các vấn đề định tuyến có khoảng thời gian. Các thuật toán được trình bày dựa trên khái niệm hoán đổi k. Sự xuất hiện của các khoảng thời gian giới hạn đưa ra các ràng buộc tính khả thi, việc kiểm tra mà thường yêu cầu O(N) thời gian. Phương pháp của chúng tôi giảm thiểu nỗ lực kiểm tra này xuống O(1). Chúng tôi cũng xem xét vấn đề tìm kiếm các giải pháp ban đầu. Một kết quả về độ phức tạp được đưa ra và một phương pháp xếp chồng theo quy tắc được mô tả.
Từ khóa
#thuật toán tìm kiếm cục bộ #vấn đề định tuyến #khoảng thời gian #ràng buộc khả thi #hoán đổi k #phương pháp xếp chồngTài liệu tham khảo
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (eds.),The Traveling Salesman Problem (Wiley, Chichester, 1985).
S. Lin, Computer solutions to the traveling salesman problem, Bell System Tech. J. 44(1965)2245.