TAILIEUCHUNG - 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

Bài viết 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 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. | 116 Nguyễn Đình Lầu Trần Quốc Chiến Trần Ngọc Việt 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 IMPROVING COMPUTING PERFORMANCE FOR ALGORITHM IN FINDING THE SHORTEST PATH IN EXTENDED GRAPH Nguyễn Đình Lầu1 Trần Quốc Chiến2 Trần Ngọc Việt1 1 Trường Cao đẳng Giao thông Vận tải II Email trviet01@ launhi@ 2 Trường Đại học Sư phạm Đại học Đà Nẵng Email tqchien@ Tóm tắt - Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều Abstract - The graph is a powerful mathematical tool applied in lĩnh vực như giao thông công nghệ thông tin kinh tế Thuật toán many fields such as transportation communication information tìm đường đi ngắn nhất trên đồ thị mở rộng đã được công bố trong technology economy Algorithm finding the shortest path in 1 . Trong bài báo này chúng tôi trình bày chi tiết thuật toán tuần extended graph was proposed in 1 . In this paper we present and tự tìm đường đi ngắn nhất giữa hai đỉnh trên đồ thị mở rộng và demonstrate in details the sequential algorithm to find the shortest chúng tôi xây dựng thuật toán này trên đa bộ xử lý để nâng cao path between two vertices on the extended graph and build this hiệu năng tính toán. Các định lý và mệnh đề trong bài báo được algorithm on multiple processors to improve computing chứng minh phần thực nghiệm cho kết quả chính xác. Thuật toán performance. The properties and theorems of this paper are song song tìm đường đi giữa hai đỉnh trên đồ thị mở rộng được carefully proven and the experiment shows correct results. Parallel xây dựng trên k bộ xử lý. Hệ thống thực nghiệm ở đây là mạng algorithm finding the shortest path between the two vertices in the LAN và chương trình được xây dựng bằng ngôn ngữ Java. extended graph is built on k processors. The experimental system used is LAN network and the program written is in Java. Từ khóa - song song đồ thị mở rộng thuật toán đường đi ngắn nhất. Key words - parallel graph extended algorithm the shortest path.

• Kỹ thuật lập trình
• Thuật toán tìm đường đi ngắn nhất
• Nâng cao hiệu năng tính toán
• Đồ thị mở rộng
• Ngôn ngữ Java
• Hệ quản trị cơ sở dữ liệu MySQL
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Cài đặt thuật toán
• Thuật toán Dijkstra
• Song song hóa thuật toán Dijkstra
• Thuật toán Dijkstra tìm đường đi ngắn nhất
• Bài toán tìm đường đi ngắn nhất
• Thuật toán tuần tự Dijkstra
• Bài giảng Toán rời rạc 2
• Toán rời rạc 2
• Toán rời rạc
• Thuật toán Bellman Ford
• Bài toán đường đi ngắn nhất
• Thuật toán tìm bao đóng bắt cầu
• Lý thuyết đồ thị
• Bài giảng lý thuyết đồ thị
• Bài toán lý thuyết đồ thị
• thuật toán song song meta heuristic
• tìm đường đi ngắn nhất
• luận văn
• hệ thống điện
• kỹ thuật điện
• tóm tắt luận văn
• Luận văn Thạc sĩ Toán học
• Kỹ thuật phễu
• Kỹ thuật cây phễu
• Toán ứng dụng
• Luận văn thạc sỹ
• luận văn ký thuật
• học viện kỹ thuật quâm sự
• thuật toán
• đường đi ngắn nhất
• dữ liệu mở dạng khoảng
• hệ thống thông tin
• Google Maps
• Giải thuật di truyền
• Đa nguồn đi đa đích đến
• Bài toán đa nguồn đi
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Biểu diễn đường đi ngắn nhất
• Chu trình trọng số âm
• Kỹ thuật nới lỏng
• Luận văn Thạc sĩ
• Công nghệ thông tin
• Tìm đường đi ngắn nhất trong đồ thị
• Hệ thống định vị toàn cầu
• Thuật toán duyệt đồ thị theo chiều sâu
• Luận án Tiến sĩ
• Luận án Tiến sĩ Toán học
• Tóm tắt Luận án Tiến sĩ Toán học
• Cơ sở toán học cho Tin học
• Bài toán tìm cây khung
• Bài toán cây khung phân cụm đường đi
• đồ án cơ sở
• Cài đặt thuật toán vuson
• tk
• Phân tích thiết kế giải thuật
• Qui hoạch động
• Thuật toán Floyd
• Bài toán tìm xâu con chung dài nhất
• Bài toán cây nhị phân tìm kiếm
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• định tuyến Dijkstra
• thuật toán định tuyến
• thuật giải một thuật toán
• thuật toán kinh điển
• Phân luồng tuyến tính tối ưu
• Mạng giao thông mở rộng
• Thuật toán tuần tự
• Thuật toán song song tương ứng
• Bài giảng Toán rời rạc
• Đồ thị
• Giải thuật Dijsktra
• Bài toán TSP
• Đồ thị có trọng số
• Đồ thị Euler
• Đồ thị Hamilton
• nguyên lý tối ưu
• luận văn mẫu
• báo cáo tốt nghiệp
• thuật toán Widest Shortest Path
• giải thuật định tuyến
• THUẬT TOÁN SONG SONG
• tuyển tập báo cáo
• nghiên cứu khoa học
• đề tài nghiên cứu
• chuyên ngành khoa học
• công nghệ môi trường
• kỹ thuật khao học
• Đề thi học kì 2
• Đề thi HK2 Kỹ thuật ra quyết định kỹ sư
• Đề thi môn Kỹ thuật ra quyết định kỹ sư
• Kỹ thuật ra quyết định kỹ sư
• Phương án tối ưu lựa chọn xây nhà