Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Tài liệu HOT
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
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
TAILIEUCHUNG - 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
Nội dung chính của bài báo tập trung xây dựng thuật toán song song tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh của đồ thị liên thông dựa trên thuật toán tuần tự Dijkstra. Ý tưởng của thuật toán là sử dụng m bộ xử lý tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh trên đồ thị. Trong m bộ xử lý chọn một bộ xử lý đóng vai trò trung tâm thực hiện việc quản lý dữ liệu, chia n đỉnh và ma trận trọng số của đồ thị cho m bộ xử lý để tìm đường đi ngắn nhất. | TẠP CHÍ KHOA HỌC, Đại học Huế, Tập 74B, Số 5, (2012), 81-92 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 Nguyễn Đình Lầu, Trần Ngọc Việt Trường Cao đẳng Giao thông Vận tải II Tóm tắt. Nội dung chính của bài báo tập trung xây dựng thuật toán song song tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh của đồ thị liên thông dựa trên thuật toán tuần tự Dijkstra. Ý tưởng của thuật toán là sử dụng m bộ xử lý tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh trên đồ thị. Trong m bộ xử lý chọn một bộ xử lý đóng vai trò trung tâm thực hiện việc quản lý dữ liệu, chia n đỉnh và ma trận trọng số của đồ thị cho m bộ xử lý để tìm đường đi ngắn nhất. 1. Giới thiệu Bài toán tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh là một trong số những bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thực tế cũng như các ứng dụng thú vị trong ngành toán học rời rạc. Bài toán được đề xuất và giải quyết bởi nhà khoa học máy tính người Hà Lan Edsger Dijkstra và được gọi là thuật toán Dijkstra. Thuật toán có độ phức tạp là O(n2), với độ phức tạp tính toán cao của thuật toán này cũng như đòi hỏi về mặt thời gian, việc giải bài toán này với tính chất tuần tự của giải thuật sẽ gặp phải những vấn đề về 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, kích thước của bài toán tăng lên và không gian tìm kiếm càng lớn, yêu cầu phải song song hóa giải thuật để tăng tốc độ và hiệu quả của giải thuật [1], [2]. Thuật toán đã giải quyết trên đồ thị với thời gian chạy khá lâu trên đồ thị có số đỉnh lớn và dễ dàng tìm thấy nhiều ứng dụng trong các lĩnh vực khoa học kỹ thuật, y tế, sinh vật và đặc biệt trong mạng giao thông vận tải. Tuy nhiên, có rất nhiều ứng dụng cần xử lý nhanh trên đồ thị có số đỉnh lớn thì thuật toán tuần tự không đáp ứng được. Vì vậy ta phải tìm cách giải quyết bài toán với số đỉnh lên đến hàng chục ngàn đỉnh mà thời gian chạy phải được rút gọn. Điều này .
Kim Lan
258
12
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
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
12
224
7
Tìm đường đi ngắn nhất với định tuyến Dijkstra
3
97
0
Bài giảng Cấu trúc dữ liệu và giải thuật: Thuật toán 2 ngăn xếp của Dijkstra - TS. Đào Nam Anh
43
108
2
Luận văn Thạc sĩ Khoa học Máy tính: Thuật toán Dijkstra Fibonacci heap, thuật toán ACO tìm đường đi tối ưu và ứng dụng
74
48
1
Advanced Algorithms Analysis and Design - Lecture 35: Dijkstra’s algorithm
32
35
1
Bài giảng Toán rời rạc: Chương 5 - Nguyễn Đức Nghĩa
78
171
2
Đồ án cơ sở : Thuật toán tìm đường đi ngắn nhất trong lý thuyết đồ thị Vuson.tk
25
100
0
Bài giảng Thuật toán ứng dụng: Graphs
141
11
1
Bài giảng Toán rời rạc 2 - Bài toán tìm đường đi ngắn nhất
28
156
4
Chương 3 - CÁC BÀI TOÁN ĐƯỜNG ĐI
74
74
0
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461868
55
Giới thiệu :Lập trình mã nguồn mở
14
22645
59
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10893
529
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10067
446
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9522
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8283
1125
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8240
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7864
2220
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6687
253
Vật lý hạt cơ bản (1)
29
5771
85
TỪ KHÓA LIÊN QUAN
Toán học
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
đị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
Bài giảng Cấu trúc dữ liệu
Cấu trúc dữ liệu và giải thuật
Cấu trúc dữ liệu
Thuật toán 2 ngăn xếp của Dijkstra
Thuật toán 2 ngăn xếp
Giá trị ngăn xếp
Luận văn Thạc sĩ
Luận văn Thạc sĩ Khoa học Máy tính
Thuật toán Dijkstra Fibonacci heap
Tìm đường đi tối ưu trên đồ thị
Lý thuyết đồ thị
Advanced Algorithms Analysis and Design
Lecture Advanced Algorithms Analysis and Design
Bài giảng Phân tích và thiết kế thuật toán nâng cao
Dijkstra’s algorithm
Mathematical statement of problem
Edge relaxation
Bài giảng Toán rời rạc
Toán rời rạc
Bài toán đường đi ngắn nhất
Thuật toán Bellman Ford
Thuật toán Floyd Warshal
Đồ thị không có chu trình
đồ án cơ sở
Thuật toán tìm đường
Xây dựng thuật toán
Cài đặt thuật toán vuson
tk
Bài giảng Thuật toán ứng dụng
Thuật toán ứng dụng
Chu trình Euler
Thuật toán Kruskal
Disjoint set structure
Bài giảng Toán rời rạc 2
Toán rời rạc 2
Nguyên lý Bellman
Thuật toán Floyd
Thuật toán Ford Bellman
Đồ thị Euler
Đồ thị Hamilton
Đồ án tốt nghiệp mạng máy tính
Đề tài thiết kế mạng
Nghiên cứu giải thuật chọn đường trên mạng
Kỹ thuật chọn đường thích nghi
Thuật toán chọn đường
Minh họa thuật toán
giao diện GUI
Đường đi Euler
Đường đi Hamilton
Chu trình Hamilton
Đường đi trên đồ thị
Tìm kiếm theo chiều rộng
Cài đặt hàng đợi ưu tiên
đồ thị vô hướng
đồ thị phi chu trình
giải thuật
tài liệu giải thuật
lý thuyết giải thuật
chuyên ngành công nghệ thông tin
đồ thị
trọng âm số
khởi tạo đồ thị
kiễm tra chu trình âm
phương pháp quy nạp
Lecture Algorithms
Bài giảng Thuật toán
Shortest Paths
Shortest paths properties
Dijkstra's algorithm
Edge weighted DAGs
Lecture Design and Analysis of Algorithms
Bài giảng Thiết kế và phân tích thuật toán
Analysis of Algorithms
Design of Algorithms
Bài giảng Lý thuyết đồ thị
Tính chất của đường đi ngắn nhất
giáo trình toán rời rạc
toán tối ưu đồ thị
đồ thị có trọng số
TÀI LIỆU MỚI ĐĂNG
Đánh giá hao mòn và độ tin cậy của chi tiết và kết cấu trên đầu máy diezel part 3
12
314
0
27-04-2024
Động cơ đốt trong và máy kéo công nghiêp tập 1 part 7
23
258
0
27-04-2024
BeginningMac OS X Tiger Dashboard Widget Development 2006 phần 2
34
212
0
27-04-2024
beginning Ubuntu Linux phần 1
34
212
1
27-04-2024
MySQL Basics for Visual Learners PHẦN 9
15
184
0
27-04-2024
B2B Content Marketing: 2012 Benchmarks, Budgets & Trends
17
139
0
27-04-2024
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1
5
126
0
27-04-2024
báo cáo hóa học:" Endoscopic decompression for intraforaminal and extraforaminal nerve root compression"
7
107
0
27-04-2024
QUẢN LÝ CHẤT LƯỢNG KHÔNG KHÍ
75
137
0
27-04-2024
Diseases of the Liver and Biliary System - part 1
33
125
0
27-04-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7864
2220
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
5738
1368
Ebook Chào con ba mẹ đã sẵn sàng
112
3767
1231
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5321
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8283
1125
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3500
643
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10893
529
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3685
525
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4052
516
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4129
480
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.