Bài giảng Kỹ thuật lập trình - Chương 4: Phương pháp quy hoạch động - Trần Minh Thái

Chương 4Phương pháp quy hoạch độngTRẦN MINH THÁI – minhthai@huflit.edu.vn - www.minhthai.edu.vn PHẠM ĐỨC THÀNH – phamducthanh@huflit.edu.vn - www.phamthao.com 12/3/20201Trần Minh Thái - Phạm Đức Thành4.1. Ý tưởng và nguyên lý4.2. Công thức truy hồi4.3. Một số bài toán quy hoạch động4.4. Tóm tắt chương4.5. Bài tập12/3/20202Trần Minh Thái - Phạm Đức ThànhNội dungMột ví dụ giới thiệu về bài toán quy hoạch:12/3/20203yOxR=1“Trong mặt phẳng xOy, tìm điểm có tọa độ (x, y) sao cho x2+y2v thì chỉ có loại 1, ngược lại (m0.12/3/202028Trần Minh Thái - Phạm Đức Thành[4.2] Công thức truy hồistatic int soCachPhanTichSo(int n){ int[,] F = new int[101, 101]; int m, v; for (m = 0; m =0; i--) { int jmax = n - 1; for (int j = i + 1; j A[i] && L[j] > L[jmax]) jmax = j; L[i] = L[jmax] + 1; T[i] = jmax; }}12/3/202040Trần Minh Thái - Phạm Đức Thànhi01234567891011A[i]-52349105678+L[i]958763254321T[i]28347611891011static bool truyVet (int[] A, int[] L, int[] T, string fileName){ StreamWriter sw = new StreamWriter(fileName); if(sw==null) {Console.WriteLine("Khong ghi duoc file");return false; } sw.WriteLine("{0}", L[0] - 2); int i = T[0]; while(i= w[i - 1] && F[i, j] 0) { if (F[n, W] != F[n - 1, W]) { sw.Write("{0,4}", n); W = W - w[n-1]; } n--; } sw.Close(); return true;}12/3/202057Trần Minh Thái - Phạm Đức Thànhstatic void Main(string[] args){ int[] w=null, v=null; int n=0, W=0; int[,] F; if (docFile(ref w,ref v,ref n,ref W,"..//..//BALO.INP") ==true) { bangPhuongAn(w, v, n, W, out F); if (truyVet (w,v,n,W,F,"..//..//BALO.OUT") == true) Console.WriteLine("Luu file thanh cong"); } Console.ReadLine();}12/3/202058Trần Minh Thái - Phạm Đức ThànhPhương pháp quy hoạch động do nhà toán học Richard Bellman phát minh vào năm 1953. Ý tưởng của nguyên lý tối ưu Bellman là:“Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái A xem như trạng thái bắt đầu cũng là tối ưu”.12/3/202059Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngPhương pháp quy hoạch động thường được dùng để giải các bài toán tối ưu có bản chất là đệ quy:Việc tìm phương án tối ưu có thể đưa về tìm tối ưu cho các bài toán con hữu hạn.Thuật toán đệ quy đã tìm hiểu ở chương 3 đa số là dùng nguyên lý “chia để trị” và trong quy hoạch động cũng áp dụng nguyên lý này.12/3/202060Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngCó 2 loại quy hoạch động:Phép phân giải đệ quy theo hướng “từ trên xuống” (top-down).Phép phân giải đệ quy theo hướng “từ dưới lên” (bottom-up).12/3/202061Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngTa có một số khái niệm sau:Bài toán quy hoạch động: giải theo phương pháp quy hoạch động.Công thức truy hồi của quy hoạch động: là công thức phối hợp nghiệm của các bài toán con để có nghiệm cho bài toán lớn.Bảng phương án của quy hoạch động: là không gian lưu trữ lời giải của các bài toán con để tìm cách phối hợp chúng.12/3/202062Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngMuốn giải bằng phương pháp quy hoạch động, bài toán cần thỏa mãn các yêu cầu sau:Phải phân rã được bài toán lớn thành các bài toán con và sự phối hợp lời giải đó cho ta lời giải cuối cùng của bài toán lớn.Phải có đủ không gian bộ nhớ vật lý.Quá trình phối hợp lời giải bài toán con đến bài toán ban đầu, phải có một số bước hữu hạn (tính dừng của chương trình).12/3/202063Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngCác bước cài đặt:Bước 1: Phân tích bài toán, lập công thức truy hồi.Bước 2: Giải tất cả các bài toán con và lưu vào bảng phương án (dùng mảng một chiều hoặc hai chiều).Bước 3: Dùng công thức truy hồi để phối hợp các lời giải của những bài toán con, lặp cho đến khi tìm được lời giải ban đầu.Bước 4: Dựa vào bảng phương án, truy vết tìm lời giải tối ưu.12/3/202064Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngCũng gần giống như phần đệ quy ở chương 3: khi phân tích bài toán và tìm ra công thức truy hồi, ta sẽ phải tìm ra hai thành phần sau:Phần cơ sở quy hoạch động (giống như phần cố định – neo trong chương 3 về đệ quy).Phần truy hồi (công thức truy hồi – giống như phần đệ quy của chương 3).12/3/202065Trần Minh Thái - Phạm Đức Thành[4.4] Tóm tắt chươngBài 1: Bài toán bố trí phòng họpCó n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm si và kết thúc fi. Do chỉ có một phòng hội thảo nên hai cuộc họp bất kỳ sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của các cuộc họp này chỉ giao nhau tại các đầu mút. Hãy bố trí lịch họp sao cho phục vụ được nhiều cuộc họp nhất.12/3/202066Trần Minh Thái - Phạm Đức Thành[4.5] Bài tậpBài 2: Bài toán điền dấu biểu thứcCho n số tự nhiên a1, a2, .., an. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu chấm hỏi (?) như sau: a1 ? a2 ? .. ? , an. Cho trước số nguyên S, có cách nào thay các dấu chấm hỏi bằng dấu công (+) hoặc trừ (-) để được một biểu thức số học cho giá trị là S không?Ví dụ: dãy ban đầu 1 ? 2? 3 ? 4 với K=0, thì cho kết quả 1-2-3+4 = 0.12/3/202067Trần Minh Thái - Phạm Đức Thành[4.5] Bài tậpBài 3: Bài toán xâu con chung dài nhất.Xâu ký tự S gọi là xâu con của xâu M nếu có thể xóa bớt một số ký tự trong xâu M để được xâu S. Nhập vào hai xâu ký tự X, Y và tìm xâu Z có độ dài lớn là xâu con của cả X và Y.Ví dụ: nhập X= “abcdefghi123” và Y= “abc1def2ghi3” thì Z là “abcdefghi3”.12/3/202068Trần Minh Thái - Phạm Đức Thành[4.5] Bài tập