Thuật toán quy hoạch tối ưu
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (91.05 KB, 5 trang )
Quy hoạch tối ưu và đề quy hoạch lui
Đào Đức Minh
Có lẽ các bạn đã rất quen thuộc với thuật toán quy hoạch động và kĩ thuật đệ quy-quay lui
đã được giới thiệu qua nhiều bài viết trên tạp chí ISM. Nếu chúng ta kết hợp hai tư tưởng
trên thì sẽ được một lớp bài toán khá thú vị,có nội dung như sau: yêu cầu tìm tất cả các
trường hợp để được kết quả tối ưu.
I. Bài toán 1:
Cho N đồ vật,đồ vật thứ i có một khối lượng là mi. Có 1 ba lô chịu được khối lượng tối đa
là M. Hãy tìm tất cả các cách chọn một số đồ vật nào đó bỏ vào ba lô sao cho tổng khối
lượng các đồ vật được chọn là lớn nhất nhưng không vượt quá M.
Giải thuật:
Ta dễ dàng nhận ra đây là bài toán ba lô quen thuộc, được giải quyết bằng thuật toán quy
hoạch động. Tuy nhiên, ta cần tìm tất cả các cách chọn để được kết quả tối ưu nhất. Vì vậy,
ta cũng sử dụng kĩ thuật đệ quy-quay lui để tìm tất cả các trường hợp.
Như vậy,thuật toán như sau:
+ Bước 1: Ăp dụng thuật toán quy hoạch động tìm giá trị W lớn nhất có thể bỏ vào ba lô từ
các đồ vật đã cho.
+ Bước 2: Ăp dụng kĩ thuật đệ quy-quay lui tìm tất cả các trường hợp chọn đồ vật để có
tổng giá trị là W. Mỗi trường hợp là một cách chọn cần tìm.
II. Bài toán 2:
Cho một ma trận (M x N) có M dòng và N cột ,trong ma trận có thể có một số ô không
được đi vào và đánh dấu '#', những ô được đi vào đánh dấu '*'. Hãy tìm tất cả các đường đi
ngắn nhất để đi từ ô (M1,N1) đến ô (M2,N2).
Bắt đầu từ ô (M1,N1).
Đường đi miêu tả bằng dãy gồm các chữ số:'0' có nghĩa là đến ô bên trái ô đang đứng;'1'-
lên ô phía trên;'2' - đến ô bên phải và '3' - xuống ô phía dưới.
Các bước đi thực hiện từ trái sang phải của dãy số.
Dữ liệu vào:
+ Dòng đầu gồm 2 số M,N (1≤M,N≤100)
+ Dòng thứ 2 và 3 là địa chỉ ô xuất phát và ô cần đến.
+ Tiếp theo là ma trận.
Kết quả:
+ Tất cả đường đi ngắn nhất tìm được.Mỗi đường đi miêu tả bằng dãy các chữ số như trên
và trên một hàng.Các dãy chữ số được sắp xếp theo thứ tự từ điển.
Dữ liệu vào đảm bảo file kết quả không quá 1 Mb.
Ví dụ:
Input example 1:
3 3
1 1
3 2
***
##*
#**
Output example 1:
22330
Input example 2:
2 2
1 1
2 2
**
**
Output example 2:
23
32
Giải thuật:
Cũng giống với bài toán trên,chúng ta thực hiện 2 bước :
+ Bước 1: Sử dụng thuật toán quy hoạch động để tạo bảng (M x N),mỗi ô (i,j)chứa giá trị
là độ dài đường đi ngắn nhất từ ô(M2,N2) đến ô(i,j). Các bạn có thể tham khảo thêm từ bài
viết 'Quy hoạch tối ưu trên một bảng hai chiềú trên ISM (số 10/2003).
Tất nhiên ô(M1,N1) là giá trị độ dài đường đi ngắn nhất từ ô(M2,N2) đến ô(M1,N1).
+ Bước 2: Dùng kĩ thuật đệ quy-quay lui để tìm tất cả đường ngắn nhất từ ô(M1,N1) đến
ô(M2,N2) dựa vào bảng vừa lập trên.
Nắm vững kĩ thuật đệ quy và quy hoạch động ,các bạn sẽ hiểu rõ hơn về ý tưởng trên qua
chương trình cụ thể sau:
PROGRAM SOLVE;
CONST
Step:array[1..4,1..2] of shortint = ((0,-1),(-1,0),(0,1),(1,0));
Dir:string='0123';
VAR
x1,y1,x2,y2,i,j,k,l,m,n:integer;
A:Array[1..100] of string[101];
Min:Array[1..100,1..100] of word;
S:Array[1..10000] of char;
Procedure Inputdata;
Begin
Assign(Input,'land.in');
Reset(Input);
Read(n,m);
Read(x1,y1);
Readln(x2,y2);
For i:=1 to n do
Readln(A[i]);
Assign(Output,'land.out');
Rewrite(Output);
End;
{Bước 1:}
Procedure Queue;
Var
Q:Array[1..10000,1..2] of byte;
Was:array[1..100,1..100] of byte;
r,w,newx,newy:integer;
Begin
r:=0;w:=1;
Fillchar(Was,Sizeof(Was),0);
Min[x2,y2]:=0;
Was[x2,y2]:=1;
Q[1,1]:=x2;Q[1,2]:=y2;
While r
Begin
Inc(r);
For k:=1 to 4 do
Begin
NewX:=Q[r,1]+Step[k,1];
NewY:=Q[r,2]+Step[k,2];
If (NewX>0)and(NewY>0)and(NewX<=n)and(NewY<=m) then
If (A[NewX,NewY]='*')and(Was[NewX,NewY]=0) then
Begin
Inc(w);
Was[NewX,NewY]:=1;
Q[w,1]:=NewX;
Q[w,2]:=NewY;
Min[Newx,Newy]:=Min[Q[r,1],Q[r,2]]+1;
End;
End;
End;
End;
{Bước 2:}
Procedure Go(i,j,Cnt:integer);
Var
newX,newY,v,w:integer;
Begin
If (i=x2)and(j=y2) then
Begin
For w:=1 to Min[x1,y1] do Write(S[w]);
Writeln;
Exit;
End;
For v:=1 to 4 do
Begin
NewX:=i+Step[v,1];
NewY:=j+Step[v,2];
If (NewX>0)and(NewY>0)and(NewX<=n)and(NewY<=m) then
If (A[NewX,NewY]='*')and((Min[NewX,NewY]+Cnt+1)=Min[X1,Y1]) then
Begin
S[Cnt+1]:=Dir[v];
Go(NewX,NewY,Cnt+1);
S[Cnt+1]:=' ';
End;
End;
End;
Procedure ProcessData;
Begin
Queue;
Go(x1,y1,0);
End;
Procedure OutputData;
Begin
Close(Output);
End;
BEGIN
InputData;
ProcessData;
OutputData;
END.
Hiểu thấu đáo thuật giải trên, các bạn thử giải bài toán tổng quát:
'Cho N thành phố ,giữa hai thành phố i,j có thể được nối bởi 1 con đường có độ dài là
S[i,j].Hãy tìm tất cả các cách đi ngắn nhất từ thành phố A đến thành phố B'.
Nhận xét: Thực ra,đây là dạng bài toán tìm đường đi ngắn nhất rất quen thuộc.Mình đề cập
đến bài toán này vì đôi khi đề bài yêu cầu tìm đường đi ngắn nhất nhưng phải thoả một số
điều kiện nào đó. Trong trường hợp điều kiện quá phức tạp thì chúng ta có thể dùng cách
này để duyệt tất cả các đường đi ngắn nhất và chọn con đường thích hợp.
Các bạn thử giải quyết bài toán sau:
III. Bài toán 3:
Cho tập hợp A gồm K số nguyên dương ai (1<=i<=K) và số S.
Hãy phân tích S thành tổng thoả điều kiện:
1. Tất cả số hạng của tổng phải thuộc tập hợp A.
2. Khi xếp các số hạng theo thứ tự giảm dần thì tổng độ chênh lệch giữa 2 số liền nhau là
nhỏ nhất.
Ví dụ: 12=1+4+2+5.
Xếp số hạng theo thứ tự giảm dần: 5 , 4 , 2 , 1
Tổng độ lệch là (5-4)+(4-2)+(2-1) = 4.
Nhìn chung, tư tưởng trên thường được áp dụng đối với những bài toán tối ưu kèm điều
kiện quá phức tạp.Nếu điều kiện bài toán đơn giản, không cần thiết duyệt tất cả các trường
hợp thì các bạn nên xử lí cách khác vì duyệt đệ quy-quay lui thường bất lợi về thời gian.
