TAILIEUCHUNG - Một cách tiếp cận mới cho bài toán tìm đường đi ngắn nhất trên đồ thị phân tán

Bài viết đề xuất một cách tiếp cận mới dựa trên kỹ thuật ước lượng từng phần để giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh trên một đồ thị phân tán. | ISSN 2354-0575 MỘT CÁCH TIẾP CẬN MỚI CHO BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ PHÂN TÁN Nguyễn Thị Huyền Phạm Đăng Hải Trường Đại học Bách khoa Hà Nội Ngày nhận 17 2 2016 Ngày xét duyệt 15 3 2016 Tóm tắt Gần đây hiệu quả của việc truy vấn thông tin trên các đồ thị lớn trở thành một chủ đề quan trọng trong khoa học máy tính. Một câu truy vấn được sử dụng rộng rãi đó là tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị một bài toán mà có thể được giải bằng một vài thuật toán nổi tiếng như Dijkstra Johnson hay Floyd-Warshall tuy nhiên nó là không đơn giản để trả lời câu truy vấn này trên một đồ thị mà dữ liệu phân tán ở nhiều vị trí khác nhau. Trong bài báo này chúng tôi đề xuất một cách tiếp cận mới dựa trên kỹ thuật ước lượng từng phần để giải quyết bài toán tìm đường đi ngắn nhất giữa hai đỉnh trên một đồ thị phân tán. Chúng tôi chỉ ra rằng thuật toán đề xuất có thể được cài đặt dưới hình thức song song trên nền tảng MapReduce. Bằng việc sử dụng một tập dữ liệu trong thực tế cho thực nghiệm chúng tôi tiến hành thực nghiệm và chỉ ra được thuật toán của chúng tôi có khả năng mở rộng cho các đồ thị lớn trên các hệ thống phân tán. Từ khóa Truy vấn đồ thị MapReduce Đường đi ngắn nhất Đồ thị phân tán Ước lượng từng phần. 1. Đặt vấn đề Giải thuật tìm kiếm A giải bài toán Trong các ứng dụng thực tế bài toán tìm nguồn đơn sử dụng heuristics để tăng tốc độ tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị kiếm. liên thông có một ý nghĩa to lớn. Ví dụ như bài toán Thuật toán Floyd-Warshall giải bài toán chọn một hành trình tiết kiệm nhất theo tiêu chuẩn đường đi ngắn nhất cho mọi cặp đỉnh. hoặc khoảng cách hoặc thời gian hoặc chi phí trên Thuật toán Johnson giải bài toán đường một mạng giao thông đường bộ đường thủy hoặc đi ngắn nhất cho mọi cặp đỉnh có thể nhanh hơn đường không bài toán chọn một phương pháp tiết thuật toán Floyd-Warshall trên các đồ thị thưa. kiệm nhất để đưa ra một hệ thống động lực từ trạng Các thuật toán trên được xây dựng để giải thái xuất phát .

• Toán học
• Bài toán tìm đường đi
• Đồ thị phân tán
• Truy vấn đồ thị
• Bài toán tìm đường đi ngắn nhất
• Phân tích mạng xã hội
• Phân tích mạng giao thông
• Tóm tắt luận văn Thạc sĩ Khoa học
• Luận văn Thạc sĩ Khoa học
• Tóm tắt luận văn Thạc sĩ
• Ứng dụng bài toán tìm đường đi
• khôi phục đường đi
• bài toán đường đi có trọng số bé nhất
• tìm đường đi ngắn nhất
• đường đi trên đồ thị phi chu trình
• đường đi ngắn nhất giữa các cặp đỉnh
• 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
• 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
• Đường đi ngắn nhất
• Google Maps
• Giải thuật di truyền
• Đa nguồn đi đa đích đến
• Bài toán đa nguồn đi
• Đề tài nghiên cứu khoa học
• Báo cáo nghiên cứu khoa học
• Báo khoa học
• Tiếp cận bài toán quy hoạch tuyến tính
• Bài toán quy hoạch tuyến tính
• 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ị
• 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
• Bài giảng Các hệ thống thông minh nhân tạo
• Hệ thống thông minh nhân tạo
• Bài toán tìm kiếm 1
• Cây tìm kiếm
• Thuật toán tìm kiếm mù
• tìm cách giải
• bài toán vật lý
• tìm quãng đường đi được
• dao động điều hòa
• nghiên cứu tự nhiên
• chuyển động tròn đều
• hệ thống GPS
• điện thoại di động
• Hệ thống điện thoại
• Vệ tinh GPS
• Mô hình kết hợp
• thuật toán song song meta heuristic
• 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ĩ
• Luận văn Thạc sĩ Công nghệ thông tin
• Đồ thị Euler
• Đồ thị lập phương
• Bài giảng Toán tổ hợp
• Toán tổ hợp
• Bài toán về đường đi
• Đồ thị Hamilton
• Bài giảng Toán học tổ hợp
• Toán học tổ hợp
• Cấu trúc rời rạc
• AKT tìm đường đi tối ưu
• cấu trúc cây
• trí tuệ nhân tạo
• bài tập lập trình
• Cấu trúc dữ liệu
• cách biểu diễn trạng thái
• phân tích bài toán
• Bài giảng Toán rời rạc
• Đường đi trên đồ thị
• Tìm kiếm theo chiều rộng
• Cài đặt hàng đợi ưu tiên
• Toán ứng dụng
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• Thuật toán Floyd
• Địa hình lưới tam giác
• Dãy mặt các tam giác kề nhau
• Đường căn chỉnh
• Hình học tính toán
• Luận văn Thạc sĩ Toán học
• Kỹ thuật phễu
• Kỹ thuật cây phễu
• 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
• dữ liệu mở dạng khoảng
• hệ thống thông tin