PHƯƠNG PHÁP QUY HOẠCH ĐỘNG SỬ DỤNG KỸ THUẬT LẬP HỆ THỨC GIẢI MỘT SỐ BÀI TOÁN TIÊU BIỂU TRONG LÝ THUYẾT ĐỒ THỊ | Núi | TNU Journal of Science and Technology

PHƯƠNG PHÁP QUY HOẠCH ĐỘNG SỬ DỤNG KỸ THUẬT LẬP HỆ THỨC GIẢI MỘT SỐ BÀI TOÁN TIÊU BIỂU TRONG LÝ THUYẾT ĐỒ THỊ

Thông tin bài báo

Ngày nhận bài: 18/10/22                Ngày hoàn thiện: 26/12/22                Ngày đăng: 26/12/22

Các tác giả

1. Nguyễn Văn Núi Email to author, Trường Đại học Công nghệ Thông tin và Truyền thông – ĐH Thái Nguyên
2. Nguyễn Thị Hằng, Trường Trung học phổ thông Xuân Giang – Hà Nội

Tóm tắt


Quy hoạch động đã được chứng minh là một phương pháp hiệu quả để giải các lớp bài toán tối ưu trong những năm gần đây. Việc nghiên cứu các kỹ thuật cụ thể của quy hoạch động để giải các bài toán tối ưu là một vấn đề thực sự cần thiết. Trong bài báo này, chúng tôi trình bày phương pháp quy hoạch động sử dụng kỹ thuật lập hệ thức để giải một số bài toán điển hình trong lý thuyết đồ thị. Các bước chi tiết của kỹ thuật lập công thức đã được nghiên cứu và tổng hợp để giải một lớp bài toán điển hình trong lý thuyết đồ thị một cách hiệu quả. Phần phân tích nhằm lựa chọn cấu trúc dữ liệu phù hợp và thiết lập công thức tối ưu để giải bài toán một cách hiệu quả cũng được trình bày. Bên cạnh đó, các thực nghiệm sử dụng ngôn ngữ lập trình python đã được tiến hành để trực quan hóa kết quả phương pháp quy hoạch động với 3 bài toán điển hình trong lý thuyết đồ thị: tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất, tìm luồng cực đại. Kết quả thu được cho thấy phương pháp quy hoạch động sử dụng kỹ thuật lập công thức giúp giải hiệu quả một số bài toán điển hình của lý thuyết đồ thị.

Từ khóa


Tối ưu hóa; Quy hoạch động; Kỹ thuật lập hệ thức; Nghiệm tối ưu; Lý thuyết đồ thị

Toàn văn:

PDF

Tài liệu tham khảo


[1] J. Wengrow, A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Level Up Your Core Programming Skills, Pragmatic Bookshelf, 2020.

[2] M. X. Vu, N. H. Nguyen, and V. T. Nguyen, Fundamental of Algorithms and Programming. University of Education Publishing House, 2014.

[3] E. A. G. Souza, M. S. Nagano, and G. A Rolim, “Dynamic Programming algorithms and their applications in machine scheduling: A review,” Expert Systems with Applications, vol. 190, March 2022, Art. no. 116180.

[4] H. Rahmanian and M. K. Warmuth, “Online Dynamic Programming,” Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, 2017, pp. 2824–2834.

[5] X. H. Nguyen, Creativity in Algorithms and Programming, 5th Edition, Information and Communications Publishing House, 2019.

[6] H. D. Nguyen, Some problems about Algorithms. Education Publishing House, 2005.

[7] X. M. Nguyen, S. D. Ho, D. H. Tran, and S. Q. Le, Some selected problems in Informatics. Education Publishing House, 2002.

[8] D. G. Do, Discrete Math applied in Informatics. Education Publishing House, 2021.

[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. The MIT Press, Cambridge, London, England, 2022.

[10] J. Rue, I. Sau, and D. M. Thilikos, “Dynamic Programming for Graphs on Surfaces,” Proceedings of ICALP’2010, France, 2011, pp. 01-32.

[11] N. Hoch, U. Montanari, and M. Sammartino, “Dynamic Programming on Nominal Graphs,” in Graphs as Models 2015 (GaM’15) - Electronic Proceedings in Theoretical Computer Science EPTCS, Open Publishing Association, 2015, pp. 80–96.

[12] P. Recht, “A Dynamic Programming Approach for the Max-Min Cycle Packing Problem in Even Graphs,” Open Journal of Discrete Mathematics, vol. 6, pp. 340-350, 2016.

[13] R. Rodriguez-Puente and M. S. Lazo-Cortes, Algorithms for shortest path search in Geographic information systems by using reduced graphs. Springer, 2013.

[14] K. R. Saoub, Graph Theory: An introduction to proofs, algorithms, and applications. CRC Press, Taylor & Francis Group, A Chapman & Hall Book, 2021.




DOI: https://doi.org/10.34238/tnu-jst.6715

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

  • Hiện tại không có bài báo tham chiếu
Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên
Phòng 408, 409 - Tòa nhà Điều hành - Đại học Thái Nguyên
Phường Tân Thịnh - Thành phố Thái Nguyên
Điện thoại: 0208 3840 288 - E-mail: jst@tnu.edu.vn
Phát triển trên nền tảng Open Journal Systems
©2018 All Rights Reserved