Tối đa chuỗi số mũ thêm

Question

Tôi biết nó đã được chứng minh NP-hoàn thành, và đó là ok. Tôi hiện đang giải quyết nó với nhánh và giới hạn nơi tôi đặt giới hạn trên ban đầu ở số phép nhân sẽ lấy thuật toán nhị phân/nhân nhị phân bình thường, và nó đưa ra câu trả lời đúng, nhưng tôi không hài lòng với việc chạy thời gian (có thể mất vài giây cho các con số khoảng 200). Đây là một vấn đề NP-complete, tôi không mong đợi bất cứ điều gì ngoạn mục; nhưng thường có những thủ thuật để có được thời gian thực tế dưới sự kiểm soát một chút.

Có cách nào nhanh hơn để thực hiện điều này trong thực tế không? Nếu vậy, chúng là gì?

Answer 1

Điều này giống như phần 4.6.3 "Đánh giá quyền hạn" trong Knuth Vol 2 Thuật toán bán số. Điều này đi vào chi tiết đáng kể để cung cấp cho các phương pháp tiếp cận khác nhau, mà nhìn nhanh hơn nhiều so với chi nhánh và bị ràng buộc nhưng không phải tất cả cung cấp các giải pháp hoàn toàn tốt nhất.

Knuth nói trong cuộc thảo luận sau Định lý F rằng anh ta sử dụng tìm kiếm backtrack để chứng minh rằng l (191) = 11, vì vậy tôi nghi ngờ nếu bạn sẽ tìm thấy một câu trả lời ngắn cho việc này. Anh ấy giải thích lời giải thích về tìm kiếm backtrack cho phần 7.2.2, mà tôi nghĩ vẫn chưa được xuất bản, mặc dù có dấu vết của công việc về điều này tại http://www-cs-faculty.stanford.edu/~uno/programs.html.

Answer 2

Metaheuristics các thuật toán sẽ mở rộng tốt hơn nhiều. Chúng bao gồm Tabu tìm kiếm, thuật toán di truyền, Mô phỏng luyện kim ...

Có một vài freebooks và miễn phí software ra khỏi đó.