Nội dung

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG -------o0o------- ĐỒ ÁN TỐT NGHIỆP NGÀNH CÔNG NGHỆ THÔNG TIN HẢI PHÒNG 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG -------o0o------- TÌM HIỂU PHƢƠNG PHÁP QUY HOẠCH ĐỘNG CHO TÍNH KHOẢNG CÁCH ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin HẢI PHÒNG - 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG -------o0o------- TÌM HIỂU PHƢƠNG PHÁP QUY HOẠCH ĐỘNG CHO TÍNH KHOẢNG CÁCH ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Sinh viên thực hiện: Vũ Hữu Trường Giáo viên hướng dẫn: PGS.TS Ngô Quốc Tạo Mã số sinh viên: 1351010055 HẢI PHÒNG - 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG CỘNG HÒA XA HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc -------o0o------- NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinh viên: Vũ Hữu Trường Mã SV: 1351010055 Lớp: CT1301 Ngành: Công nghệ Thông tin Tên đề tài: Tìm hiểu thuật toán quy hoạch động cho tính khoảng cách NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung ● Tổng quan về thuật toán quy hoạch động ● Một số kinh nghiệm xây dựng thuật toán quy hoạch động ● Thử nghiệm trên ngôn ngữ b. Các yêu cầu cần giải quyết ● Hiểu nội dung của quy hoạch động ● Viết xong đồ án ● Cài đặt thử nghiệm chương trình đặc trưng CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Ngô Quốc Tạo Học hàm, học vị: Phó Giáo Sư - Tiến Sĩ Cơ quan công tác: Trưởng phòng Nhận dạng và Công nghệ tri thức , Viện Công nghệ thong tin , Viện Hàn Lâm Khoa học và Công nghệ Việt Nam Nội dung hướng dẫn: ...................................................................................... ………………………………………………………………………………… ………………………………………………………………………………… Ngƣời hƣớng dẫn thứ hai: Họ và tên: ………………………………………………………………… Học hàm, học vị: …………………………………………………………… Cơ quan công tác: …………………………………………………………… Nội dung hướng dẫn: ………………………………………………………….. ………………………………………………………………………………… ………………………………………………………………………………… Đề tài tốt nghiệp được giao ngày tháng năm 2013 Yêu cầu phải hoàn thành trước ngày tháng năm 2013 Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hướng dẫn Đ.T.T.N PGS.TS. Ngô Quốc Tạo Hải Phòng, ngày ............tháng.........năm 2013 HIỆU TRƯỞNG GS.TS.NGƯT Trần Hữu Nghị PHẦN NHẬN XÉT TÓM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................................. ........................................................................................................... 2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) ........................................................................................................................ ........................................................................................................................ ........................................................................................................................ ........................................................................................................................ ........................................................................................................................ ........................................................................................................................ ........................................................................................................................ ............................ 3. Cho điểm của cán bộ hƣớng dẫn: ( Điểm ghi bằng số và chữ ) ........................................................................................................................ ........................................................................................................................ Ngày.......tháng.........năm 2013 Cán bộ hướng dẫn chính ( Ký, ghi rõ họ tên ) PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế, ...) ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................................. ........................................................................................................... ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................ ............................................................................................................................................. ........................................................................................................ 2. Cho điểm của cán bộ phản biện ( Điểm ghi bằng số và chữ ) ........................................................................................................................ ........................................................................................................................ . Ngày.......tháng.........năm 2013 Cán bộ chấm phản biện ( Ký, ghi rõ họ tên ) Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng LỜI CẢM ƠN Tôi xin được bày tỏ lòng biết ơn chân thành đến Ban Giám Hiệu, các thầy giáo, cô giáo trường đại học Dân Lập Hải Phòng, đã giảng dạy và tạo mọi điều kiện cho tôi học tập, nghiên cứu và hoàn thành Đồ án này. Đặc biệt, tôi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc đến PGS.TS. Ngô Quốc Tạo - người đã tận tình hướng dẫn và giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu và hoàn thành Đồ án. Cảm ơn gia đình, bạn bè đã hết lòng giúp đỡ, khích lệ, động viên tôi để tôi hoàn thành Đồ án. Xin chia sẻ niềm vui này với bạn bè và những người thân yêu. Vũ Hữu Trường - CT1301 Page 1 Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng MỤC LỤC LỜI CẢM ƠN .................................................................................................. 3 DANH MỤC CÁC BẢNG .............................................................................. 4 DANH MỤC CÁC HÌNH ............................................................................... 5 MỞ ĐẦU .......................................................................................................... 6 Chƣơng 1: TỔNG QUAN VỀ PHƢƠNG PHÁP QUY HOẠCH ĐỘNG .. 6 1.1. Giới thiệu chung ...............................................................................................6 1.2. Thuật toán chia để trị ......................................................................................11 1.3. Nguyên lý tối ưu của Bellman .........................................................................12 1.4. Đặc điểm chung của phương pháp quy hoạch động .......................................12 1.5. Ý tưởng và nội dung của thuật toán quy hoạch động .....................................14 1.5.1. Các khái niệm ...........................................................................................14 1.5.2. Ý tưởng .....................................................................................................14 1.5.3. Nội dung ...................................................................................................14 1.6. Các bước thực hiện .........................................................................................14 Chƣơng 2 MỘT SỐ KỸ THUẬT GIẢI BÀI TOÁN QUY HOẠCH ĐỘNG ............................................................................................................. 17 2.1. Lập hệ thức .....................................................................................................17 2.1.1. Tạo một công thức truy hồi từ một công thức đã có ................................17 2.1.2. Dựa theo thứ tự xây dựng .........................................................................19 2.1.2.1. Xây dựng dựa theo thứ tự đầu ...........................................................19 2.1.2.2. Xây dựng theo thứ tự cuối ..................................................................21 2.1.3. Phụ thuộc vào số biến của hàm ................................................................24 2.1.3.1. Công thức truy hồi có một biến..........................................................24 2.1.3.2. Công thức truy hồi có hai biến ..........................................................27 2.1.3.3. Công thức truy hồi có ba biến............................................................28 2.2. Tổ chức dữ liệu ...............................................................................................30 Chƣơng 3 THUẬT TOÁN QUY HOẠCH ĐỘNG VÀ LÝ THUYẾT TRÒ CHƠI............................................................................................................... 35 3.1. Bài toán trò chơi .............................................................................................35 3.2. Lý thuyết trò chơi ...........................................................................................36 3.2.1. Trò chơi trên đồ thị...................................................................................37 3.2.1.1. Trường hợp đồ thị không có chu trình ...............................................38 3.2.1.2. Trường hợp đồ thị có chu trình ..........................................................38 3.2.1.3. Giải thuật xây dựng W và L độ phức tạp O(E) ..................................39 3.2.2. Tổng trực tiếp. Hàm Sprague - Grundy ...................................................39 3.2.3. Trò chơi trên ma trận ...............................................................................43 3.3.1. Tính trực tiếp hàm Sprague - Grundy ......................................................44 Vũ Hữu Trường - CT1301 Page 2