PHƯƠNG PHÁP QUY HOẠCH ĐỘNG SỬ DỤNG KỸ THUẬT LẬP HỆ THỨC GIẢI MỘT SỐ BÀI TOÁN TIÊU BIỂU TRONG LÝ THUYẾT ĐỒ THỊ

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Thị Hằng Nguyễn, Văn Núi Nguyễn

Ngôn ngữ: vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên, 2023

Mô tả vật lý: tr.70 - 77

Bộ sưu tập: Báo, Tạp chí

ID: 337018

Thêm vào giỏ Liên kết toàn văn

Dynamic programming has been proven to be an effective method to solve class of optimization problems in the recent years. The study of specific techniques of dynamic programming to solve optimization 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 technique have been studied and synthesized to effectively solve a class of typical problems in graph theory. The analysis in oder to select suitable data structure and establish the optimal formula to effectively solve the problem is also presented. Besides, the experiments using python programming language has been conducted for visualizing the results of dynamic programing method with three typical problems in 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.Quy hoạch động đã được chứng minh là một phương pháp hiệu quả để giải các lớp bài toán tối ưu trong những năm gần đây. Việc nghiên cứu các kỹ thuật cụ thể của quy hoạch động để giải các bài toán tối ưu là một vấn đề thực sự cần thiết. Trong bài báo này, chúng tôi trình bày phương pháp quy hoạch động sử dụng kỹ thuật lập hệ thức để giải một số bài toán điển hình trong lý thuyết đồ thị. Các bước chi tiết của kỹ thuật lập công thức đã được nghiên cứu và tổng hợp để giải một lớp bài toán điển hình trong lý thuyết đồ thị một cách hiệu quả. Phần phân tích nhằm lựa chọn cấu trúc dữ liệu phù hợp và thiết lập công thức tối ưu để giải bài toán một cách hiệu quả cũng được trình bày. Bên cạnh đó, các thực nghiệm sử dụng ngôn ngữ lập trình python đã được tiến hành để trực quan hóa kết quả phương pháp quy hoạch động với 3 bài toán điển hình trong lý thuyết đồ thị: tìm đường đi ngắn nhất, tìm cây khung nhỏ nhất, tìm luồng cực đại. Kết quả thu được cho thấy phương pháp quy hoạch động sử dụng kỹ thuật lập công thức giúp giải hiệu quả một số bài toán điển hình của lý thuyết đồ thị.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR