TỐI ƯU HÓA QUY HOẠCH ĐỘNG TRÊN CÁC HỆ THỐNG TÍNH TOÁN BIÊN: MỘT KHUNG TIẾP CẬN THỐNG NHẤT SỬ DỤNG HÌNH HỌC TÍNH TOÁN VÀ NHÂN TỬ LAGRANGE
DOI:
https://doi.org/10.59266/houjs.2026.1156Keywords:
quy hoạch động, kỹ thuật bao lồi, tối ưu Lambda, tối ưu hóa biên, độ phức tạp thuật toánAbstract
Trong bối cảnh các thiết bị tính toán biên (Edge Computing) ngày càng đóng vai trò trung tâm trong việc xử lý chuỗi dữ liệu thời gian thực, rào cản lớn nhất nằm ở sự xung đột giữa yêu cầu độ trễ cực tiểu và giới hạn năng lượng tiêu thụ. Các tiếp cận quy hoạch động (DP) kinh điển, vốn mang độ phức tạp, thường trở thành bình cảnh không thể vượt qua khi kích thước dữ liệu chạm ngưỡng. Bài báo này thiết lập một khung triển khai hợp nhất (Unified Implementation Framework), tích hợp sức mạnh của kỹ thuật bao lồi (Convex Hull Trick - CHT) và phương pháp tối ưu hóa Lambda (-Optimization) để hạ bậc độ phức tạp xuống tuyến tính. Những đóng góp khoa học cốt lõi bao gồm: kiến tạo cơ chế tính toán số học an toàn trên miền nguyên 128-bit nhằm triệt tiêu hoàn toàn sai số làm tròn số thực. Sau đó đề xuất chiến lược “phá vỡ thế cân bằng” (tie-breaking strategy) đặc thù cho phương pháp Lagrange để đảm bảo sự hội tụ ổn định; cuối cùng là kiểm chứng thực nghiệm toàn diện trên các tập dữ liệu mô phỏng quy mô lớn. Số liệu cho thấy tại , giải thuật đề xuất chỉ tiêu tốn trung bình 8.5ms, cải thiện hiệu năng tới 99.9% so với mức 20150ms của phương pháp cơ sở, khẳng định tính khả thi khi triển khai trên các thiết bị hạn chế tài nguyên.
References
Aho, V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. Addison-Wesley.
Bellman, R. (1957). Dynamic programming. Princeton University Press.
Bertsekas, D. P. (1999). Nonlinear programming (2nd ed.). Athena Scientific.
Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational geometry: Algorithms and applications (3rd ed.). Springer.
Eppstein, D., Galil, Z., Giancarlo, R., & Italiano, G. F. (1992). Sparse dynamic programming I: Linear cost functions. Journal of the ACM, 39(3), 519-545.
Everett, H. (1963). Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Operations Research, 11(3), 399-417.
Galil, Z., & Giancarlo, R. (1989). Speeding up dynamic programming with applications to molecular biology. Theoretical Computer Science, 64(1), 107-118.
Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4), 132-133.
Hochbaum, D. S. (Ed.). (1997). Approximation algorithms for NP-hard problems. PWS Publishing.
Karp, R. M. (1986). Combinatorics, complexity, and randomness. Communications of the ACM, 29(2), 97-109.
Knuth, D. E. (1971). Optimum binary search trees. Acta Informatica, 1, 14-25.
Knuth, D. E. (1998). The art of computer programming (Vol. 3: Sorting and searching, 2nd ed.). Addison-Wesley.
Kopeliovich, S. (2016). Aliens trick (Lagrange multipliers for DP optimization). Codeforces Blog. https://codeforces. com/blog/entry/49691
Li, Y., & Chao, K. (2011). The Li Chao tree for dynamic programming optimization. Olympiad Informatics Training Material.
Monge, G. (1781). Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences.
Nocedal, J., & Wright, S. J. (2006). Numerical optimization (2nd ed.). Springer.
Overmars, M. H., & van Leeuwen, J. (1981). Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2), 166-204.
Pan, S. J., & Yang, Q. (2010). A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22(10), 1345-1359.
Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. Springer-Verlag.
Rockafellar, R. T. (1970). Convex analysis. Princeton University Press.
Satyanarayanan, M. (2017). The emergence of edge computing. Computer, 50(1), 30-39.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.
Shi, W., Cao, J., Zhang, Q., Li, Y., & Xu, L. (2016). Edge computing: Vision and challenges. IEEE Internet of Things Journal, 3(5), 637-646.
Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.
Skiena, S. S. (2008). The algorithm design manual (2nd ed.). Springer.
Sniedovich, M. (2010). Dynamic programming: Foundations and principles. Taylor & Francis.
Tarjan, R. E. (1983). Data structures and network algorithms. SIAM.
USACO. (2017). Building a tall barn. USACO January Platinum Contest (Problem 2).
Yao, F. F. (1980). Efficient dynamic programming using quadrangle inequalities. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC) (pp. 429-435).
