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 .
