[block id=”bo-sung-1″]

Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả
giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Những bài toán này
thường có nhiều nghiệm chấp nhận được và mỗi nghiệm có một giá trị đánh giá.
Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá lớn nhất hoặc
nhỏ nhất (tối ưu). Ví dụ tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị, tìm chuỗi
con chung dài nhất của hai chuỗi, tìm chuỗi con tăng dài nhất, Số lượng bài toán
được giải bằng lập trình động cũng rất lớn. Ví dụ riêng kì thi Olympic quốc tế về
Tin học 2004 có tới ba bài trong sáu bài có thể giải bằng quy hoạch động.
Quy hoạch động giải các bài toán bằng cách kết hợp các lời giải của các bài
toán con của bài toán đang xét. Phương pháp này khả dụng khi các bài toán con
không độc lập đối với nhau, tức là khi các bài toán con có dùng chung những bài
toán “cháu”. Quy hoạch động giải các bài toán “cháu” dùng chung này một lần và
lưu lời giải của chúng trong một bảng và sau đó khỏi phải tính lại k hi gặp lại bài
toán cháu đó. Quy hoạch động được áp dụng cho những bài toán tối ưu hóa
(optimization problem). Bốn bước của qui hoạch động : Đặc trưng hóa cấu trúc
của lời giải tối ưu. + Định nghĩa giá trị của lời giải tối ưu một cách đệ quy. + Tính
trị của lời giải tối ưu theo kiểu từ dưới lên. + Cấu tạo lời giải tối ưu từ những thông
tin đã được tính toán. Các thành phần của quy hoạch động : + Tiểu cấu trúc tối ưu -Một bài toán có tính chất tiểu cấu trúc tối ưu nếu lời giải tối ưu chứa trong nó
những lời giải tối ưu của những bài toán con. + Những bài toán con trùng lắp – Khi
một giải thuật đệ quy gặp lại cùng một bài toán con nhiều lần, ta bảo rằng bài toán
tối ưu hóa có những bài toá n con trùng lặp.

de_tai_tim_hieu_phuong_phap_quy_hoach_dong_cho_tinh_khoang

 

pdf78 trang | Chia sẻ: thuychi21 | Ngày: 12/12/2015 | Lượt xem: 1404 | Lượt tải: 4download

Bạn đang xem trước 20 trang tài liệu Đề tài Tìm hiểu phương pháp quy hoạch động cho tính khoảng cách, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

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
Sinh viên
Đã nhận nhiệm vụ: Đ.T.T.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
Vũ Hữu Trường – CT1301 Page 1
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.
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 2
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
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 3
3.3.2. Kỹ thuật bảng phương án (Decide Table) ………………………………………… 47
Chƣơng 4 THUẬT TOÁN QUY HOẠCH ĐỘNG CHO TÍNH KHOẢNG
CÁCH ………………………………………………………………………………………………. 52
4.1: Khoảng cách Levenshtein ……………………………………………………………………. 52
4.1.1:Thuật toán …………………………………………………………………………………….. 52
4.1.2 : Độ phức tạp ………………………………………………………………………………… 55
4.1.3: Biến thể ……………………………………………………………………………………….. 55
4.2 : Dãy con chung dài nhất ……………………………………………………………………… 56
4.3 : Các thuật toán khác ……………………………………………………………………………. 56
4.4 : Ứng dụng …………………………………………………………………………………………. 56
4.5: Tính Khoảng cách: Quy hoạch động, Lập trình thuật toán ………………………. 59
4.6 :Phân tích của DP Tính Khoảng cách …………………………………………………….. 65
4.7. Xây dựng chương trình tính khoảng cách bằng thuật toán quy hoạch động .. 66
KẾT LUẬN ……………………………………………………………………………………… 71
TÀI LIỆU THAM KHẢO …………………………………………………………………. 72
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 4
DANH MỤC CÁC BẢNG
Bảng 2.1. Bảng số lần gọi hàm f(n) với n = 5 ……………………………………… 17
Bảng 2.2. Các phương án chia kẹo với m = 7, n = 4 …………………………….. 21
Bảng 2.3. Số lần gọi hàm cục bộ khi gọi C(7, 4) …………………………………. 31
Bảng 3.1. Bảng phương án cho bài toán lật xúc xắc …………………………….. 50
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 5
DANH MỤC CÁC HÌNH
Hình 2.1. Cây biểu diễn lời gọi hàm f của bài toán tính hàm f(5) ………………………. 18
Hình 2.2. Cây biểu diễn số lần gọi hàm cục bộ khi gọi hàm C(7, 4) …………………… 32
Hình 3.1. Không gian trạng thái và không gian điều khiển của bài toán lật xúc xắc
………………………………………………………………………………………………………………….. 37
Hình 3.2. Biểu diễn các nước đi của trò chơi dưới dạng một đồ thị có hướng ……………. 37
Hình 3.3. Biểu diễn tính số Sprague – Grundy …………………………………………………. 40
Hình 3.4. Sơ đồ thuật giải trò chơi NIM …………………………………………………………. 46
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 6
Chƣơng 1: TỔNG QUAN VỀ PHƢƠNG PHÁP QUY HOẠCH ĐỘNG
1.1. Giới thiệu chung
Quy hoạch động (Dynamic Programming) là một phương pháp rất hiệu quả
giải nhiều bài toán tin học, đặc biệt là những bài toán tối ưu. Những bài toán này
thường có nhiều nghiệm chấp nhận được và mỗi nghiệm có một giá trị đánh giá.
Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá lớn nhất hoặc
nhỏ nhất (tối ưu). Ví dụ tìm đường đi ngắn nhất giữa hai đỉnh của đồ thị, tìm chuỗi
con chung dài nhất của hai chuỗi, tìm chuỗi con tăng dài nhất, Số lượng bài toán
được giải bằng lập trình động cũng rất lớn. Ví dụ riêng kì thi Olympic quốc tế về
Tin học 2004 có tới ba bài trong sáu bài có thể giải bằng quy hoạch động.
Quy hoạch động giải các bài toán bằng cách kết hợp các lời giải của các bài
toán con của bài toán đang xét. Phương pháp này khả dụng khi các bài toán con
không độc lập đối với nhau, tức là khi các bài toán con có dùng chung những bài
toán “cháu”. Quy hoạch động giải các bài toán “cháu” dùng chung này một lần và
lưu lời giải của chúng trong một bảng và sau đó khỏi phải tính lại khi gặp lại bài
toán cháu đó. Quy hoạch động được áp dụng cho những bài toán tối ưu hóa
(optimization problem). Bốn bước của qui hoạch động : Đặc trưng hóa cấu trúc
của lời giải tối ưu. + Định nghĩa giá trị của lời giải tối ưu một cách đệ quy. + Tính
trị của lời giải tối ưu theo kiểu từ dưới lên. + Cấu tạo lời giải tối ưu từ những thông
tin đã được tính toán. Các thành phần của quy hoạch động : + Tiểu cấu trúc tối ưu –
Một bài toán có tính chất tiểu cấu trúc tối ưu nếu lời giải tối ưu chứa trong nó
những lời giải tối ưu của những bài toán con. + Những bài toán con trùng lắp – Khi
một giải thuật đệ quy gặp lại cùng một bài toán con nhiều lần, ta bảo rằng bài toán
tối ưu hóa có những bài toán con trùng lặp.
Chuỗi con chung dài nhất LCS : O(m+n)
Bài toán cái túi (Knapsack) : Bài toán cái túi có thể dễ dàng giải được nếu M
không lớn, nhưng khi M lớn thì thời gian chạy trở nên không thể chấp nhận được.
Phương pháp này không thể làm việc được khi M và trọng lượng/kích thước là
những số thực thay vì số nguyên. Giải thuật qui hoạch động để giải bài toán cái túi
có thời gian chạy tỉ lệ với NM.
Giải thuật Warshall [O(V3)- Giải thuật Floyd [O(V3)] : thể hiện sự áp dụng
chiến lược quy hoạch động vì sự tính toán căn cứ vào một hệ thức truy hồi nhưng
lại không xây dựng thành giải thuật đệ quy. Thay vào đó là một giải thuật lặp với
sự hỗ trợ của một ma trận để lưu trữ các kết quả trung gian.
Giải thuật tham lam
Các giải thuật tối ưu hóa thường đi qua một số bước với một tập các khả năng lựa
chọn tại mỗi bước. Một giải thuật tham lam thường chọn một khả năng mà xem
như tốt nhất tại lúc đó. Tức là, giải thuật chọn một khả năng tối ưu cục bộ với hy
vọng sẽ dẫn đến một lời giải tối ưu toàn cục. VD : +Bài toán xếp lịch cho các hoạt
động + Bài toán cái túi dạng phân số + Bài toán mã Huffman+ Giải thuật Prim để
tính cây bao trùm tối thiểu.
Đồ án tốt nghiệp Trường đại học dân lập Hải Phòng
Vũ Hữu Trường – CT1301 Page 7
Hai thành phần chính của giải thuật tham lam :
+ Tính chất lựa chọn tham lam : Lựa chọn được thực hiện bởi giải thuật tham
lam tùy thuộc vào những lựa chọn đã làm cho đến bây giờ, nhưng nó không tùy
thuộc vào bất kỳ lựa chọn trong tương lai hay những lời giải của những bài toán
con.
Như vậy, một giải thuật tham lam tiến hành theo kiểu từ trên xuống, thực hiện
mỗi lúc một lựa chọn tham lam.
+ Tiểu cấu trúc tối ưu: Một bài tóan có tính chất tiểu cấu trúc tối ưu nếu một
lời giải tối ưu chứa trong nó những lời giải tối ưu cho những bài toán con.
Dùng giải thuật tham lam cho bài toán cái túi dạng phân số và qui hoạch động
cho bài toán cái túi dạng 0-1.
Giải thuật tham lam cho bài toán xếp lịch các hoạt động:
Hoạt động được chọn bởi thủ tục GREEDY-ACTIVITY-SELECTER thường
là hoạt động với thời điểm kết thúc sớm nhất mà có thể được xếp lịch một cách hợp
lệ. Hoạt động được chọn theo cách “tham lam” theo nghĩa nó sẽ để lại cơ hội để
xếp lịch cho được nhiều hoạt độngkhác. Giải thuật tham lam không nhất thiết đem
lại lời giải tối ưu. Tuy nhiên thủ tục GREEDY-ACTIVITY-SELECTOR thường
tìm được một lời giải tối ưu cho một thể hiện của bài toán xếp lịch các hoạt động.
Bài toán cái túi dạng phân số (knapsack) : O(n) + Giải thuật HUFFMAN
(dùng phổ biến và rất hữu hiệu cho việc nén dữ liệu) trên tập n ký tự sẽ là :
O(nlgn) + Bài toán tô màu đồ thị : Đầu tiên ta cố tô cho được nhiều đỉnh với màu
đầu tiên, và rồi dùng một màu mới tô các đỉnh chưa tô sao cho tô được càng nhiều
đỉnh càng tốt. Và quá trình này được lặp lại với những màu khác cho đến khi mọi
đỉnh đều được tô màu. Độ phức tạp của thủ tục SAME_COLOR: O(n). Nếu m là số
màu được dùng để tô đồ thị thì thủ tục SAME_COLOR được gọi tất cả m lần.
Do đó, độ phức tạp của toàn giải thuật: m* O(n). Vì m thường là một số
nhỏ=>độ phức tạp tuyến tính . Ứng dụng : xếp lịch thi học kỳ , gán tần số trong
lĩnh vực vô tuyến ,điện thoại di động.
Giải thuật quay lui : “bước hướng về lời giải đầy đủ và ghi lại thông tin về
bước này mà sau đó nó có thể bị tháo gỡ và xóa đi khi phát hiện rằng bước này đã
không dẫn đến lời giải đầy đủ, tức là một bước đi dẫn đến “tình thế bế tắc”(dead-
end). (Hành vi này được gọi là quay lui – backtracking.) VD : bài toán tám con hậu
,bài toán con mã đi tuần
Một phương pháp tổng quát để giải quyết vấn đề: thiết kế giải thuật tìm lời
giải cho bài tóan không phải là bám theo một tập qui luật tính toán được xác định
mà là bằng c

[block id=”bo-sung”]

Từ khóa: Đề tài Tìm hiểu phương pháp quy hoạch động cho tính khoảng cách

Leave a Reply

Your email address will not be published. Required fields are marked *