Thạc Sĩ Song song hoá thuật toán tìm đường đi ngắn nhất trên nguồn dữ liệu lớn dùng MPI

MỤC LỤC
Trang
LỜI CẢM ƠN . iii
MỤC LỤC . iv
Danh mục các thuật ngữ . vii
Danh mục các hình vẽ, bảng biểu . viii
MỞ ĐẦU 1
1. Đặt vấn đề 1
2. Mục đích của luận văn . 1
3. Nội dung của luận văn . 1
4. Phương pháp nghiên cứu . 2

CHƯƠNG 1 - MỘT SỐ KỸ THUẬT TÌM KIẾM ĐƯỜNG ĐI NGẮN NHẤT 3
1.1. Bài toán tìm kiếm đường đi ngắn nhất . 3
1.2. Các thuật toán . 4
1.2.1. Thuật toán Dijkstra . 4
1.2.2. Thuật toán A star 6
1.2.3. Thuật toán di truyền . 9

CHƯƠNG 2 - LẬP TRÌNH SONG SONG VỚI MPI . 16
2.1. Tổng quan về lập trình song song với MPI 16
2.1.1. Giới thiệu 16
2.1.2 Một số đặc điểm của lập trình MPI . 17
2.2. Lập trình song song với MPI 19
2.2.1. Giới thiệu 19
2.2.2. Một số vấn đề về hiệu năng 21
2.2.2.1 Năng lực tính toán . 21
2.2.2.2 Cân bằng tải . 23
2.2.2.3 Sự bế tắc 25

CHƯƠNG 3 - MPI TRONG THUẬT TOÁN DIJKSTRA CHO BÀI TOÁN TÌM
KIẾM ĐƯỜNG ĐI NGẮN NHẤT 27
3.1. Yêu cầu đặt ra cho bài toán tìm kiếm đường đi ngắn nhất theo giải thuật
Dijksta 27
3.2. Xây dựng hàm tìm kiếm đường đi ngắn nhất . 27
3.2.1 Xây dựng thuật toán Dijkstra tuần tự cho bài toán . 27
3.2.2 Thực hiện song song hoá . 28
3.2.3 Thuật toán song song . 29
3.2.4 Lựa chọn hàm MPI cho thuật toán song song . 30
3.2.5 Công thức song song . 35
3.3. Chi phí thời gian . 38

CHƯƠNG 4 - KẾT QUẢ THỬ NGHIỆM 39
4.1. Các kết quả thử nghiệm 39
4.1.1. Kết quả thử nghiệm giải thuật Dijkstra cổ điển . 39
4.1.2. Kết quả thử nghiệm tìm kiếm bằng giải thuật Dijkstra song song . 40
4.2. Đánh giá kết quả . 41
KẾT LUẬN 44


LUẬN VĂN THẠC SĨ
NĂM 2011

MỞ ĐẦU
1. Đặt vấn đề
Tim kiếm đường đi ngắn nhất là một bài toán kinh điển đã được nghiên cứu rất
nhiều và ứng dụng trong những hệ thống chuyên biệt. Rất nhiều nghiên cứu đã
cải tiến những thuật toán và tối ưu thuật toán về không gian tìm kiếm, thời gian
tìm kiếm.
Tuy nhiên, với sự bùng nổ thông tin và sự phát triển của công nghệ thông tin,
những thuật toán tìm kiếm đường đi ngắn nhất kinh điển không thể đáp ứng
được thời gian tìm kiếm tốt nhất trên lượng dữ liệu lớn.
Bài toán đặt ra là làm thế nào để giải quyết vấn đề tìm kiếm đường đi ngắn nhất
với nguồn dữ liệu lớn và phân tán, đáp ứng được mục tiêu rút ngắn thời gian tìm
kiếm.
2. Mục đích của luận văn
Nghiên cứu và song song hoá thuật toán Dijkstra cho bài toán tìm đường đi ngắn
nhất trên nguồn dữ liệu lớn và phân tán; từ đó nâng cao hiệu quả của việc xử lý
dữ liệu.
3. Nội dung của luận văn
Trong luận văn này gồm có 3 nội dung:
- Nội dung 1: Nghiên cứu về bài toán tìm kiếm đường đi ngắn nhất. Đánh giá
ưu điểm, nhược điểm của từng thuật toán.
- Nội dung 2: Cải tiến thuật toán Dijkstra cho bài toán tìm kiếm đường đi
ngắn nhất bằng cách song song hóa thuật toán để tối ưu về thời gian tìm kiếm
trên nguồn dữ liệu lớn.
- Nội dung 3: Tiến hành thử nghiệm, đánh giá thuật toán cải tiến.

4. Phương pháp nghiên cứu
Để thực hiện những nội dung đã nêu ở trên, tác giả đã sử dụng một số phương
pháp cho từng nội dung như sau:
- Nội dung 1: sử dụng phương pháp phân tích, so sánh và đánh giá các thuật
toán tìm kiếm đường đi ngắn nhất.
- Nội dung 2: sử dụng phương pháp phân tích khả năng song song hóa thuật
toán Dijkstra.
- Nội dung 3: sử dụng phương pháp đối sánh để đánh giá kết quả thử nghiệm
của thuật toán đã cải tiến.




TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Đinh Mạnh Tường, Giáo trình trí tuệ nhân tạo, Khoa CNTT – Đại học Quốc
gia Hà Nội
[2] Giáo trình Lý thuyết đồ thị, Khoa CNTT – Đại học Huế
Tiếng Anh
[3] G. Amdahl. Validity of the single processor approach to achieving large scale
computing capabilities. Proc. AFIPS Conf., 30:483{485, Apr. 18-20 1967}.
[4] G.A.Geist, J.A.Kolh, P.M.Papadopoulos, PVM and MPI: a comparison of
features, Applied Mathematical Sciences subprogram of the Office of Energy
Reaseach, US Department of Energy. May 30 1996.