tailieunhanh - Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng

Bài viết Ứng dụng thuật toán tìm đường đi nhanh nhất tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng phân tích, chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 10 71 .2013 ỨNG DỤNG THUẬT TOÁN TÌM ĐƯỜNG ĐI NHANH NHẤT TÌM LUỒNG CỰC ĐẠI ĐA PHƯƠNG TIỆN TUYẾN TÍNH ĐỒNG THỜI CHI PHÍ CỰC TIỂU TRÊN MẠNG GIAO THÔNG MỞ RỘNG APPLICATION OF THE FASTEST PATH ALGORITHM TO FINDING MAXIMUM CONCURENT MULTICOMMODITY LINEAR FLOW WITH MINIMAL COST ON EXTENDED TRAFFIC NETWORK Trần Quốc Chiến Trường Đại học Sư phạm Đại học Đà Nẵng Email tqchien@ TÓM TẮT Đồ thị và mạng mở rộng là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông truyền thông công nghệ thông tin kinh tế . 7 . Kết quả chính của bài báo là nghiên cứu thuật toán tìm luồng cực đại đa phương tiện tuyến tính đồng thời chi phí cực tiểu trên mạng giao thông mở rộng sử dụng thuật toán tìm đường đi nhanh nhất trên mạng giao thông mở rộng 6 . Trên sơ sở bài toán đối ngẫu trong 7 tác giả xây dựng thuật toán đưa tỉ lệ hàm mục tiêu hai bài toán đối ngẫu này tiến đến 1 và từ đó suy ra luồng cực đại đồng thời chi phí cực tiểu. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là 1 với dương nhỏ tùy ý. Bài báo phân tích chứng minh các kết quả và đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác. Từ khóa đồ thị mạng luồng đa phương tiện tối ưu xấp xỉ ABSTRACT Extended graph and network is a powerful mathematical tool applied in many fields such as transportation communication informatics economy 7 . The main result of this paper is to design a Maximum Concurent Multicommodity Flow with Minimal Cost algorithm on extended traffic networks using the algorithm to find shortest paths on extended networks 6 . On the basis of the dual linear programming problem studied in 7 the author designs the algorithm to reduce the ratio of objective values of the dual and the primal problems down to 1. Then it follows the concurent maximal flow with minimal cost of the origin problem. This .