Lý thuyết và bài tập loại quy hoạch động
Cho mảng A(N) . Cần xoá ít nhất một số phần tử của dãy này sao cho các phần tử còn lại tạo thành dãy tăng nghiêm ngặt . Ta xây dựng mảng T(N) và mảng D(N) với ý nghĩa : + T[i] là chỉ số j ( trong mảng A ) của phần tử đứng trước phần tử có chỉ số i (trong mảng A ) khi xét dãy kết quả . + D[i] là độ dài của dãy kết quả khi bài toán trên mảng A(N) mới được xét từ phần tử 1 đến phần tử i ( Nghiã là ta tạm giải bài toán với kích thước đến i - đó là kích thước không vượt quá kích thước bài toán đã cho ) . Công thức qui hoạch động của bài toán này là :
Bạn đang xem nội dung tài liệu Lý thuyết và bài tập loại quy hoạch động, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Quy hoạch động Qui hoạch động là một trong những phương pháp tối ưu hiện đại. Đối tượng của qui hoạch động là các quá trình tối ưu nhiều bước nói chung và các quá trình phát triển theo thời gian nói riêng. Sự xuất hiện của qui hoạch động gắn liền với tên tuổi của nhà toán học Mỹ R.Bellman mà trong những năm 50 của thế kỉ này đã áp dụng cho một loạt các bài toán thực tế, một công cụ mà sau này gọi là nguyên tắc tối ưu. Chính nhờ tính đơn giản và tính tường minh của nguyên tắc này mà phương pháp qui hoạch động tỏ ra đặc biệt hấp dẫn. Bên cạnh nguyên tắc tối ưu, nguyên tắc quan trọng thứ hai là nguyên tắc lồng bài toán tối ưu đang xét vào một họ các bài toán tương tự. Việc áp dụng nguyên tắc tối ưu và nguyên tắc lồng dẫn đến các phương trình hàm truy toán đối với giá trị tối ưu. Những phương trình thu được cho phép lần lượt viết ra các điều khiển tối ưu cho bài toán xuất phát. Cái hay ở đây là bài toán tính toán điều khiển của cả quá trình chia ra thành một dãy các bài toán tính toán điều khiển đơn giản cho các giai đoạn của quá trình. Lĩnh vực áp dụng của qui hoạch động rất rộng: Các quá trình kỹ thuật công nghiệp, tổ chức sản xuất, kế hoạch hóa kinh tế, trong các vấn đề khác nhau của vật lý, sinh vật, và quân sự.
$1. PHƯƠNG PHÁP PHƯƠNG TRÌNH TRUY TOÁN VÀ CÁC NGUYÊN TẮC CƠ BẢN CỦA QUI HOẠCH ĐỘNG
1.1 Bài toán phân phối một chiều và phương pháp phương trình truy toán. 1. Bài toán phân phối Trong thực tế có nhiều tài nguyên khác nhau: Nhân công, tiền máy, nhiên liệu
Mõi tài nguyên có thể sử dụng theo nhiều cách và cho nhiều hiệu quả khác nhau. Vấn đề đặt ra là cần phân phối các tài nguyên đó như thế nào để hiệu quả sử dụng tổng cộng là lớn nhất. Ta xét quá trình phân phối một tài nguyên với trữ lượng là a. Có n cách sử dụng. Nếu sử dụng đơn vị theo cách thứ i (i=1
N) thì sẽ đạt hiệu quả đo bằng hàm . Hãy qui định số đơn vị cần dùng theo mỗi cách i để tổng hiệu quả là lớn nhất. Mô hình của bài toán có dạng (1.1) (1.1) (1.2) và thường được biểu thị bởi những đơn vị đo khác nhau: Chẳng hạn là nhiêu liệu thì là tốc độ, là tiền thì là máy, độ tin cậy
Độ lớn của hiệu quả phụ thuộc vào số lượng tài nguyên sử dụng (a) và vào quá trình được chọn lựa (N). 2. Phương pháp phương trình truy toán Để nghiên cứu bài toán trên, ta lồng nó vào một họ các quá trình phân phối nào đó. Thay cho một bài toán với số lượng tài nguyên a cho trước và số các cách sử dụng N cố định, ta xét một họ các bài toán như vậy, trong đó a và N thay đổi, tức là ta chuyển quá trình tĩnh thành quá trình động. Vì cực đại của hàm chỉ phụ thuộc vào a và N, ta gọi giá trị tối ưu là thì trong đó thỏa mãn (1.2) và (1.3). Khi N thay đổi, ta hãy tìm mối liên hệ giữa các hàm
., Vì ở đây ta biết ngay
. nên có thể nói rõ hơn là : Biết
. với a thay đổi, hãy tìm mối liên hệ giữa
.
? Giả sử
là lượng tài nguyên quyết định đối với quá trình thứ N. Khi đó bất kì
như thế nào, số lượng còn lại
sẽ được sử dụng sao để cho nhận được thu nhập cực đại của N-1 quá trình còn lại. Vì thu nhập tối ưu của N -1 quá trình theo định nghĩa là
. nên sự quyết định
cho quá trình thứ N đi đến thu nhập tổng cộng đối với N quá trình :
.. Phương trình truy toán là
. Như vậy ta đã đưa bài toán cực trị của N biến về N bài toán cực trị một biến và phương tình (1.4) gọi là phương trình truy toán của qui hoạch động. Đó là ý cơ bản của phương pháp qui hoạch động giải bài toán cực trị bằng phương pháp phương trình truy toán. Biết
.. dựa vào phương trình truy toán (1.4) ta tìm được
., sau đó lại thay
. vào (1.4) ta tìm được
..v.v
. Cứ như vậy cho tới khi tìm được
. Cơ sở của việc làm này là nguyên lý tối ưu tổng quát mà ta sé xét trong mục dưới đây 1.2 Các nguyên tắc cơ bản của qui hoạch động Qui hoạch động là việc qui hoạch từng giai đoạn của quá trình nhiều giai đoạn mà trong đó mỗi giai đoạn ta chỉ tối ưu hóa một bước. Tuy nhiên khi qui hoạch một quá trình nhiều giai đoạn, ở mỗi bước ta phải lựa chọn điều khiển trên cơ sở không phải xuất phát từ lợi ích nhỏ hẹp của chính bước đó mà từ lợi ích chung của toàn bộ quá trình. 1. Nguyên tắc đánh số các giai đoạn từ dưới lên. Đối với giai đoạn cuối có thể làm cho nó tốt nhất và không lo hậu quả. Khi đó giai đoạn này trở nên ổn định và ta có thể xét giai đoạn ở trước đó và cứ tiếp tục cho tới lúc ta đi được tới giai đoạn đầu của quá trình. 2. Nguyên tắc thông số hóa bài toán Ở giai đoạn sát giai đoạn cuối cùng, ta chưa biết kết quả nên ta phải đặt giả thiêt cho giai đoạn này rồi ứng với giả thiết đó ta tìm điều khiển tối ưu cho giai đoạn cuối cùng. Ở các bước khác tình hình cũng xảy ra như vậy. Do đó quá trình điều khiển tối ưu sẽ phụ thuộc vào các thông số đặc trưng cho kết quả ở bước trước. 3. Nguyên tắc lồng Lồng bài toán ban đầu vào một bài toán rộng hơn hay một họ các bài toán và do đó bài toán ban đầu là một trường hợp riêng của họ bài toán này. Họ bài toán này nhờ có các thông số nên ta giải được. Ta sẽ thử kết quả của bài toán với các thông số khác nhau cho tới một lúc được thông số của bài toán ban đầu thì dừng lại. 4. Nguyên tắc tối ưu (Bellman) Dáng điệu tối ưu có tính chất là: dù trạng thái ban đầu và điều khiển ban đầu có dạng như thế nào thì điều khiển tiếp theo cũng là tối ưu đối với trạng thái thu được trong kết quả tác động những điều khiển ban đầu. Bài toán ứng dụng cho quy hoạch động - bài toán knapsack 0-1 hay bài toán cái túi xách:
Qui hoạch động
A - Phần đề bài
Bài 1 :
Cho N số nguyên dương (0<104 +1) và một dãy A1, A2 , ... , An các số nguyên
Tìm trong dãy đã cho một dãy con Ai1, Ai2, .... , Aik thoả mãn các điều kiện :
a) Ai j £ Ai j+1
b) ij £ i j+1
c) k lớn nhất
Dữ liệu vào : File BL1.INP có cấu trúc như sau :
Dòng thứ nhất ghi số N
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , An mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số Ai1, Ai2, .... , Aik mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
12
6 12 8 11 3 4 1 7 5 9 10 2
File Output
3 4 7 9 10
Bài 2 :
Cho 2 số nguyên dương M,N (0£100) và 2 dãy số nguyên : A1, A2 , ... , AN và B1, B2 , ... , B M . Hãy loại đi một số phần tử của 2 dãy sao cho các số còn lại của 2 dãy ( giữ nguyên thứ tự cũ ) tạo thành 2 dãy như nhau và độ dài k là lớn nhất .
Dữ liệu vào : File BL1.INP có cấu trúc như sau :
Dòng thứ nhất ghi số N ,M
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , AN và B1, B2 , ... , B M mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số còn lại của 1 dãy nào đó , mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
8 12
0 0 9 2 3 7 3 1
4 4 0 5 0 9 0 3 10 4 8 3
File Output
5
0 0 9 3 3
Bài 3 : ( Di chuyển từ Tây sang Đông )
Cho hình chữ nhật MxN ô vuông ,mỗi ô chứa một số nguyên
Bài : ( Bài Mã vạch )
Cho bộ 3 số (N,M,K) nguyên không âm (N<=100,M,K<=33) . Người ta định nghĩa mỗi bộ 3 số trên ứng với 1 mã là một xâu kí tự dạng nhị phân thoả mãn :
+ Chứa đúng N chữ số
+ Các chữ số 0 liền nhau hoặc các chữ số 1 liền nhau gọi là 1 vạch , phải có đúng M vạch
+ Số chữ số trong 1 vạch gọi là độ rộng của vạch . Độ rộng tối đa của vạch là K
+ Vạch đầu tiên của mã phải là vạch gồm các chữ số 1.
Lập trình thực hiện các yêu cầu sau :
1) Lấy dữ liệu từ File ‘MV.INP’ tổ chức như sau :
- Dòng đầu là 3 số N,M,K
- Dòng thứ 2 là số p
- P dòng tiếp theo : mỗi dòng là một mã M i (0< i <P+1) của bộ mã (M,N,K)
2) Thông tin ra gửi vào File ‘MV.OUT’ :
- Dòng đầu là số nêu tổng số mã của bộ mã (N,M,K)
- Tiếp theo gồm p dòng , mỗi dòng ghi 1 số là vị trí của mã M i trong tự điển xếp tăng các mã của bộ mã (N,M,K) .
Thí dụ
File ‘MV.INP’
7 4 3
6
1110100
1101100
1001000
1000100
1101110
1110110
File ‘MV.OUT’
16 15
12
3
1
13
16
Bài 1 : Tìm dãy con tăng dài nhất :
Cho mảng A(N) . Cần xoá ít nhất một số phần tử của dãy này sao cho các phần tử còn lại tạo thành dãy tăng nghiêm ngặt . Ta xây dựng mảng T(N) và mảng D(N) với ý nghĩa :
+ T[i] là chỉ số j ( trong mảng A ) của phần tử đứng trước phần tử có chỉ số i (trong mảng A ) khi xét dãy kết quả .
+ D[i] là độ dài của dãy kết quả khi bài toán trên mảng A(N) mới được xét từ phần tử 1 đến phần tử i ( Nghiã là ta tạm giải bài toán với kích thước đến i - đó là kích thước không vượt quá kích thước bài toán đã cho ) . Công thức qui hoạch động của bài toán này là :
D[i] = Max { D[j] + 1 / " j : j <i mà A[j] < A[i] }
Chú ý
1- Khởi trị bài toán : T[1] = 0 , D[1] = 1
2- Xử dụng công thức trên với i>1 , mỗi lần tìm được j thoả mãn cần ghi lưu T[i]=j
3- Khi xong i=N , tìm lại kết quả nhờ duyệt mảng D . Trước hết tìm j có D[j] lớn nhất , sau đó truy hồi dần tìm j bằng cách thay j bởi T[j] cho đến khi T[j]=0
Các vị trí j tìm được chính là các vị trí trong mảng A cần giữ lại nhưng theo thứ tự ngược .
Thí dụ
Chỉ số
1
2
3
4
5
6
7
8
9
10
11
12
A
6
12
8
11
3
4
1
7
5
9
10
2
T
0
1
1
3
0
5
0
6
6
8
10
7
D
1
2
2
3
-1
-2
1
-3
3
-4
-5
2
Dãy kết quả là :
Chỉ số
5
6
8
10
11
A
3
4
7
9
10
Bài 2 : Xoá ít nhất một số phần tử của 2 dãy sao cho sau khi xoá 2 dãy như nhau
Gợi ý : Cần xây dựng mảng C(N,M) với ý nghĩa : C[i,j] là độ dài của dãy còn lại nếu dãy A chỉ xét tới chỉ số i và dãy B chỉ xét tới chỉ số j . Đương nhiên C[1,j] = 0 nếu A[1] không có trong dãy B(j) ,ngược lại thì C[1,j] = 1 ; tương tự C[i,1] = 0 nếu B[1] không có trong dãy A(i) ,ngược lại thì C[i,1] = 1 . Những trường hợp còn lại C[i,j] được tính theo công thức truy hồi sau :
C[i,j] = Max{C[i,j-1],C[i-1,j],C[i-1,j-1]+x}
( Vì : nếu A[i]=B[j] thì C[i,j]= C[i-1,j-1]+1
nếu A[i] không có trong B(j) thì C[i,j]= C[i-1,j]
nếu B[j] không có trong A(i) thì C[i,j]= C[i,j-1] )
A - Lời giải
Bài 1 :
{Cho N nguyen duong N<=10000 so , tim day tang dai nhat }
Uses Crt;
Const Max = 10000;
Fi = 'BL14.inp';
Fo = 'BL1.out';
Type Mang = Array[1..Max] of Integer;
Var A,D,T : Mang;
N,dem : LongInt;
F : Text;
Procedure TaoF;
Var F : Text;
i : LongInt;
Begin
Assign(F,Fi);
ReWrite(F);
Write('Nhap N = ');
Repeat
{$I-} Readln(N);{$I+}
Until (IoResult=0) and (N>0) and (N<=Max);
Writeln(F,N);
For i:=1 to N do
Begin
Write(F,10000-i+1:7);
{Write(F,Random(100):3);}
If i mod 10 =0 then Writeln(F);
End;
Close(F);
End;
Procedure Nhap;
Var i : LongInt;
Begin
FillChar(A,Sizeof(A),0);
Assign(F,Fi);
Reset(F);
Readln(F,N);
For i:=1 to N do Read(F,A[i]);
Close(F);
End;
Procedure KhoitriT_D;
Begin
FillChar(T,Sizeof(T),0);
T[1] := 0;
D[1] := 1;
End;
Function Vitritruoc(i : LongInt) : LongInt;
Var j,Ld,Lj : LongInt;
Begin
Ld := 0;
Lj := 0;
Vitritruoc := 0;
For j:=i-1 downto 1 do
If A[j]<=A[i] then
If D[j]>Ld then
Begin
Ld := D[j];
Lj := j;
End;
Vitritruoc := Lj;
End;
Procedure TaoT_D;
Var i : LongInt;
Begin
KhoitriT_Dl;
For i:=2 to N do
Begin
T[i] := Vitritruoc(i);
If T[i]=0 then D[i] := 1
Else D[i] := D[T[i]]+1;
End;
End;
Function MaxD : Longint;
Var i,p,Li : LongInt;
Begin
p := -MaxInt;
Li := 0;
For i:=1 to N do
If D[i]>p then
Begin
p := D[i];
Li := i;
End;
MaxD := Li;
End;
Procedure Timketqua;
Var i : LongInt;
Begin
i := MaxD;
D[i] := -D[i];
dem := 1;
Repeat
i := T[i];
If i0 then
Begin
D[i] := -D[i];
Inc(dem)
End;
Until i=0;
End;
Procedure Ghi;
Var F : Text;
i : LongInt;
Begin
Assign(F,Fo);
ReWrite(F);
Writeln(F,dem);
dem := 0;
For i := 1 to N do
If D[i]<0 then
Begin
Write(F,A[i]:7);
Inc(dem);
If dem mod 10 = 0 then Writeln(F);
End;
Close(F);
End;
BEGIN
Clrscr;
{TaoF;}
Nhap;
TaoT_D;
Timketqua;
Ghi;
Writeln('Da xong ');
Readln;
END.
Bài 2 :
Uses Crt;
Const Max = 100;
Fi = 'qhdong2.inp';
Fo = 'qhdong2.out';
Type M1 = Array[1..Max] of Byte;
M2 = Array[1..Max,1..Max] of Byte;
Var A,B : M1;
C : M2;
F,F2 : Text;
M,N : Byte;
Procedure TaoF;
Var i : Byte;
F : Text;
Begin
Write('Nhap do dai 2 mang : M,N = ');
Readln(M,N);
Assign(F,Fi);
ReWrite(F);
Writeln(F,M,' ',N);
For i:=1 to M do Write(F,Random(100+1),' ');
Writeln(F);
For i:=1 to N do Write(F,Random(100+1),' ');
Close(f);
End;
Procedure DocF;
Var i : Byte;
Begin
Assign(F,Fi);
Reset(F);
Readln(F,M,N);
For i:=1 to M do Read(F,A[i]);
Readln(F);
For i:=1 to N do Read(F,B[i]);
Close(F);
End;
Function Max3(x,y,z : Byte) : Byte;
Var phu : Byte;
Begin
If x>y then phu := x Else phu := y;
If z>phu then phu := z;
Max3 := Phu;
End;
Function Co(x,L : Integer;D : M1) : Boolean;
Var
Các file đính kèm theo tài liệu này:
Lý htuyết và bài tập loại quy hoạch động.doc
