Nâng cao hiệu năng tính toán cho thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng
Tóm tắt: 286
| 
PDF: 69 
##plugins.themes.academic_pro.article.main##
Author
Từ khóa:
song song
đồ thị
mở rộng
thuật toán
đường đi ngắn nhất
Tóm tắt
Đồ thị 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, công nghệ thông tin, kinh tế,…Thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng đã được công bố trong [2]. Trong bài báo này chúng tôi trình bày chi tiết thuật toán tuần tự tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị mở rộng và chúng tôi xây dựng thuật toán này trên đa bộ xử lý để nâng cao hiệu năng tính toán. Các định lý và mệnh đề trong bài báo được chứng minh, phần thực nghiệm cho kết quả chính xác. Thuật toán song song tìm đường đi giữa hai đỉnh trên đồ thị mở rộng được xây dựng trên m bộ xử lý. Hệ thống thực nghiệm ở đây là mạng LAN và chương trình được xây dựng bằng ngôn ngữ Java.
Tài liệu tham khảo
-
[1] Trần Quốc Chiến, Nguyễn Mậu Tuệ, Trần Ngọc Việt, “Thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng”. Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ VI. FAIR 2013, Huế, 20-21/6/2013.
[2] Nguyễn Đình Lầu, Trần Ngọc việt, Song song hóa thuật toán dijkstra tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh, Tạp chí Khoa học, Đại học Huế, Tập 74B, Số 5, 2012, 81-92.
[3] Nguyễn Đình Lầu, Trần Ngọc việt, Thuật toán song song tìm đường đi ngắn nhất của nhiều cặp đỉnh nguồn đích trên đồ thị, Tạp chí Khoa học & Công nghệ, Đại học Đà nẵng, quyển 1, số 9 2012, 30-34.
[4] Nguyễn Đình Lầu, Trần Quốc Chiến, Lê Mạnh Thạnh, Thuật toán song song phân luồng tuyến tính tối ưu trên mạng giao thông mở rộng, Chuyên san “Các Công trình Nghiên cứu, Phát triển và Ứng dụng Công nghệ Thông tin và Truyền thông Bộ Thông Tin-Truyền Thông, Kỳ 3, Tập V-1, năm 2014.
[5] Trần quốc chiến, Lê Mạnh Thạnh, Nguyễn Đình Lầu, Thuật toán song song tìm luồng cực đai đồng thời chi phí giới hạn, kỷ yếu hội thảo quốc gia @16, Những vấn đề chọn lọc của công nghệ thông tin và truyền thông, Đà Nẵng 14-15/11/2013 (accepted).
[6] Nguyễn Đình Lầu, Trần Ngọc Việt, Song song hóa thuật toán tìm đường đi ngắn nhất của tất cả các đỉnh trên hệ thống cụm máy tính, Kỷ yếu hội thảo khoa học quốc gia @ lần thứ XV, một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, chủ đề tính toán khoa học, nhà xuất bản khoa học và kỹ thuật, quyết định xuất bản số 152/QĐXB-NXBKHKT, 15/8/1013, trang 403-409
[7] Zilong Ye, An Implementation of Parallelizing Dijkstra’s Algorithm, CSE633 Course Project, ID: 3715-8138, 2012
[8] Ned Nedialkov, Parallel Distributed Shortest Paths, SE 3F03, McMaster University Canada, March 2013.
[9] G. Stefano, A. Petricola, C. Zaroliagis, “On the implementation of parallel shortest path algorithms on a supercomputer”, in Proc. of ISPA’06, pp. 406-417, 2006
[10] Y. Tang, Y. Zhang, H. Chen, “A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Y. Tang, Y. Zhang, H. Chen, “A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting”, in Proc. of IEEE HPCC’08, pp. 155-161, 2008.
[11] Seyed H. Roosta, Parallel Processing and parallel Algorithm, Theory ND Computation, Springer, ISBN 0-387-98716-9, 1999.
Xem thêm
##plugins.themes.academic_pro.article.sidebar##
Đã Xuất bản
Jul 31, 2014
Download
Cách trích dẫn
Nguyen Dinh Lau; Tran Quoc Chien; Tran Ngoc Viet. “Nâng Cao hiệu năng tính toán Cho thuật toán tìm đường đi ngắn nhất Trên đồ thị mở rộng”. Tạp Chí Khoa học Và Công nghệ Đại học Đà Nẵng, vol 7, số p.h 80, Tháng Bảy 2014, tr 116-20, https://jst-ud.vn/jst-ud/article/view/303.
