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

Bài viết 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ả. | TNU Journal of Science and Technology 228 02 70 - 77 DYNAMIC PROGRAMMING METHOD USING FORMULATING TECHNIQUE TO SOLVE SOME TYPICAL PROBLEM IN GRAPH THEORY Nguyen Van Nui1 Nguyen Thi Hang2 1 TNU - University of Information and Communication Technology 2Xuan Giang High School Ha Noi ARTICLE INFO ABSTRACT Received 18 10 2022 Dynamic programming has been proven to be an effective method to solve class of optimization problems in the recent years. The study of Revised 26 12 2022 specific techniques of dynamic programming to solve optimization Published 26 12 2022 problems is a really necessary issue. In this paper we present a dynamic programming method using formulating technique to solve some typical problems in graph theory. Detailed steps of formulating KEYWORDS technique have been studied and synthesized to effectively solve a class Optimization of typical problems in graph theory. The analysis in oder to select suitable data structure and establish the optimal formula to effectively Dynamic programming solve the problem is also presented. Besides the experiments using Formulating technique python programming language has been conducted for visualizing the Optimal solution results of dynamic programing method with three typical problems in Graph theory graph theory shortest path finding minimum spanning tree finding maximum network flow finding. The obtained results show that the dynamic programming method using the formulating technique helps to solve some typical problems of graph theory effectively. 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Ị Nguyễn Văn Núi1 Nguyễn Thị Hằng2 1 Trường Đại học Công nghệ Thông tin và Truyền thông ĐH Thái Nguyên 2 Trường Trung học phổ thông Xuân Giang Hà Nội THÔNG TIN BÀI BÁO TÓM TẮT Ngày nhận bài 18 10 2022 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 Ngày hoàn thiện 26 12 2022