Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    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

    Nhu Ely Nhu Ely Đang Ngoại tuyến (1771 tài liệu)
    .:: Bronze Member ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. 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.

    Xem Thêm: 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
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu 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 sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu
Tài liệu mới

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status