Ứng dụng mô hình xử lý phân tán Mapreduce để giải quyết bài toán TSP

Abstract

Mô hình xử lý phân tán MapReduce là mô hình dùng để xử lý dữ liệu lớn trên nhiều cụm máy tính. Trong luận văn này, tôi đã trình bày cơ sở lý thuyết tổng quan về mô hình xử lý phân tán MapReduce, tổng quan về dữ liệu lớn, sự khác biệt giữa dữ liệu lớn và dữ liệu truyền thống, bài toán TSP(người bán hàng). Tiếp đến, tôi đã tìm hiểu chi tiết hệ thống phân tán MapReduce, qui trình xử lý một bài toán trên mô hình MapReduce, tìm hiểu hàm Map, hàm Reduce, quá trình xử lí bài toán TSP (người bán hàng) trên mô hình MapReduce. Cuối cùng, tôi đã xây dựng thành công chương trình giải bài toán TSP trên mô hình MapReduce và đã cho thử nghiệm chương trình trên mô hình tuần tự và mô hình xử lý phân tán MapReduce bằng nhiều hình thức khác nhau như: Số lượng đỉnh của bài toán, số lượng máy tính, cụm máy tính tham gia tính toán. Qua kết quả thử nghiệm cho thấy thời gian thực hiện chương trình nhanh hơn nhiều so với chương trình viết bằng thuật toán xử lý tuần tự với cùng số đỉnh. Điều này thêm một lần nữa khẳng định rằng việc ứng dụng cơ chế xử lý phân tán MapReduce để giải quyết các bài toán có dữ liệu lớn( bài toán TSP) là có hiệu quả và đúng đắn.