TAILIEUCHUNG - Thuật toán song song tìm nguồn cực đại

Bài viết tập trung xây dựng thuật toán song song dựa trên thuật toán truyền thống và thuật toán hoán chuyển nguồn đích, các kết quả cơ bản được hệ thống và chứng minh. tưởng thuật toán là sử dụng hai bộ vi xử lý thực hiện công việc song song tìm đường tăng luồng, vi xử lý 1 xuất phát từ đỉnh nguồn, vi xử lý 2 xuất phát từ đỉnh đích. Mời các bạn tham khảo. | THUẬT TOÁN SONG SONG TÌM LUỒNG CỰC ĐẠI USING PARALLEL ALGORITHM TO FIND THE MAXIMAL FLOW TRẦN QUỐC CHIẾN Trường Đại học Sư phạm Đại học Đà Nang HỒ xUâN bình Trường Đại học Dân lập Duy Tân TÓM TẮT Kết quả chính của bài báo là tập trung xây dựng thuật toán song song dựa trên thuật toán truyền thống và thuật toán hoán chuyển nguồn đích 2 Các kết quả cơ bản được hệ thống và chứng tưởng thuật toán là sử dụng hai bộ vi xử lý thực hiện công việc song song tìm đường tăng luồng vi xử lý 1 xuất phát từ đỉnh nguồn vi xử lý 2 xuất phát từ đỉnh đích. Thuật toán song song làm giảm đáng kể thời gian tính toán so với các thuât toán truyền thống. ABSTRACT The main result of this article is putting forward the parallel algorithm based on Ford-Fulkerson and sourse-sink alternative algorithm. The basic results are systematically presented and proved. The aim of the algorithm is using two processing to carry out parallely working finding augmented paths one comes from the source and the other from the sink vertex. The proposed algorithm considerably decreases the computational time in comparison with nonparallel algorithms. Key word graph network flow parallel 1. Đặt vấn đề Bài toán luồng cực đại trên mạng là một trong số những bài toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. Bài toán được đề xuất và giải quyết bởi hai nhà toán học Mỹ Ford và Fulkerson vào đầu những năm 1950 và ngày càng được các nhà khoa học quan tâm nghiên cứu. Hiện nay mô hình xử lý song song đã và đang phát triển mạnh mẽ giải quyết những vấn đề bế tắc mà mô hình xử lý tuần tự gặp phải như vấn đề thời gian thực hiện chương trình tốc độ xử lý khả năng lưu trữ của bộ nhớ xử lý dữ liệu với quy mô lớn. Trong bối cảnh đó thuật toán tìm luồng cực đại cần được phát triển theo hướng song song nhằm phát huy sức mạnh của bài toán. 2. Bài toán tìm luồng cực đại trên mạng Cho mạng G V E C nguồn a đích z. Trong số các luồng trên mạng G hãy .

• Cơ sở dữ liệu
• Ý tưởng thuật toán
• Xây dựng thuật toán song song
• Thuật toán song song
• Bài toán tìm luồng cực đại trên mạng
• Hiệu chỉnh tăng luồng
• Tìm luồng cực đại trên mạng
• Bài thuyết trình
• Thuật toán Karp Rabin
• Tìm hiểu thuật toán Karp Rabin
• Ý tưởng thuật toán Karp Rabin
• Giải thuật thuật toán
• Mã hóa thuật toán
• Tư duy thuật toán
• Tin học
• Thuật toán
• Biểu diễn tư duy
• Mô tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Thuật toán Tham lam
• Ý tưởng tham lam
• Bài toán lập lịch
• Tiếp cận tham lam
• Sự kì diệu của toán học
• Khám phá phá phép thuật toán học
• Ý tưởng toán học
• Quy luật toán học
• Khái niệm toán học
• Ứng dụng toán học
• Thuật toán Lùa bò vào chuồng
• Ý tưởng bài toán Lùa bò vào chuồng
• Mã giả bài toán Lùa bò vào chuồng
• Thuật toán Tin học
• Bài toán Lùa bò vào chuồng
• Đề thi học kỳ
• Chia để trị
• Thiết kế thuật toán
• Phân tích thuật toán
• Lược đồ giản thuật
• Ý tưởng chia để trị
• Bài toán tìm kiếm nhị phân
• Quản trị web
• Thiết kế web
• Phát triển web
• Nguồn thiết kế
• Thủ thuật thiết kế
• Ống khói hình trụ
• Điều khiển chuyển động
• Cơ học đất
• Địa kỹ thuật
• Bài toán nửa ngược
• Công nghệ xây dựng
• Luồng cực đại
• Thuật toán tìm luồng cực đại
• Bài toán luồng cực đại
• Mạng hỗn hợp mở rộng
• Luồng cực đại lát cắt cực tiểu
• Mạng thặng dư
• Phương pháp đẩy luồng trước
• Thuật toán Ford Fulkerson
• Mạng mở rộng
• Thuật toán hoán chuyển nguồn đích
• Luồng trên mạng mở rộng
• Sinh nhãn lùi
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Luồng trên mạng
• Đồ thị tăng luồng
• Luồng đa phương tiện
• Thuật toán tìm đường đi nhanh nhất
• Tìm luồng cực đại
• Mạng giao thông mở rộng
• Hệ quản trị cơ sở dữ liệu MySQL
• Bài giảng Toán rời rạc
• Toán rời rạc
• Lát cắt cực tiểu
• Bài tập Luồng trên mạng
• Tìm ghép cặp cực đại
• Thuật toán đích hướng nguồn
• Hàm khả năng không thành cạnh
• Luồng trên mạng G