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ị

Abstract

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ị.