Diễn đàn tin học Văn Lang - Vạn Ninh
Chào mừng bạn đến với Diễn đàn Tin học Văn Lang - Vạn Ninh của chúng tôi !
Hãy đăng nhập hoặc đăng kí tài khoản để trải nghiệm nhiều điều thú vị tại đây !
Thân ái !

Diễn đàn tin học Văn Lang - Vạn Ninh

Nơi trao đổi thông tin, tăng cường hợp tác, giải đáp những vướng mắc khi học lập trình Pascal
 
Trang ChínhCalendarTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập

Share | 
 

 Thuật toán cần học " THUẬT TOÁN QUY HOẠCH ĐỘNG"

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
phong



Posts : 12
Danh tiếng : 2
Join date : 07/12/2014

Bài gửiTiêu đề: Thuật toán cần học " THUẬT TOÁN QUY HOẠCH ĐỘNG"   11/1/2015, 16:10

Thuật toán qui hoạch động
Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán-Tin. Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một số thuật toán chung như chia để trị, tham ăn, quay lui,... Các thuật toán này có thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Trong bài viết này, tôi muốn đề cập với các bạn một thuật toán khác, đó là thuật toán quy hoạch động. Tư tưởng cơ bản của thuật toán là:
Để giải một bài toán ta chia bài toán đó thành các bài toán nhỏ hơn có thể giải một cách dễ dàng. Sau đó kết hợp lời giải các bài toán con, ta có được lời giải bài toán ban đầu. Trong quá trình giải các bài toán con đôi khi ta gặp rất nhiều kết quả trùng lặp của các bài toán con. Để tăng tính hiệu quả, thay vì phải tính lại các kết quả đó, ta lưu chúng vào một bảng. Khi cần lời giải của một bài toán con nào đó ta chỉ cần tìm trong bảng, không cần tính lại.
Tư tưởng của thuật toán quy hoạch động khá đơn giản. Tuy nhiên khi áp dụng thuật toán vào trường hợp cụ thể lại không dễ dàng (điều này cũng tương tự như nguyên tắc Dirichlet trong toán vậy). Khi giải bài toán bằng phương pháp này, chúng ta phải thực hiện hai yêu cầu quan trọng sau:
- Tìm công thức truy hồi xác định nghiệm bài toán qua nghiệm các bài toán con nhỏ hơn. - Với mỗi bài toán cụ thể, ta đề ra phương án lưu trữ nghiệm một cách hợp lý để từ đó có thể truy cập một cách thuận tiện nhất.
Để minh hoạ thuật toán, ta xét một vài ví dụ.
Ví dụ 1: Cho hai dãy số nguyên (a1,a2,...,am), (b1,b2,...,bn). Tìm dãy con chung có độ dài lớn nhất của hai dãy trên (coi dãy không có số nguyên nào là dãy con của mọi dãy và có độ dài bằng 0).
Lời giải
Chúng ta có thể thấy ngay rằng độ phức tạp của bài toán trên phụ thuộc vào hai số m, n. Xét hai trường hợp:
+Trường hợp1: m=0 hoặc n=0.
Đây là trường hợp đặc biệt, có duy nhất một dãy con chung của hai dãy có độ dài  bằng 0. Vì vậy dãy con chung có độ dài lớn nhất của chúng có độ dài bằng 0.
+Trường hợp 2: m# 0 và n # 0.
Trong trường hợp này, ta xét các bài toán nhỏ hơn là tìm dãy con chung có độ dài lớn nhất của hai dãy (a1,a2,...,ai), (b1,b2,...,bj) với 0 <= i <= m, 0 <= j <= n. Gọi l[i,j] là độ dài của dãy con chung lớn nhất của hai dãy (a1,...,ai), (b1,...,bj). ; Như vậy ta phải tính tất cả các l[i,j] trong đó 0<=i<=m, 0<=j<=n.
Chúng ta có thể  thấy ngay rằng  l[0,0]=0. Giả sử ta tính được l[s,t] với 1
       - Nếu ai # bj thì l[i,j]=max{l[i-1,j], l[i,j-1]}.
       - Nếu ai = bj thì l[i,j]= 1+l[i-1,j-1].
Với những nhận xét trên, ta hoàn toàn tính được l[m,n] chính là độ dài dãy con chung dài nhất của (a1,..am), (b1,..bn).
Để tìm phần tử của dãy con, ta xuất phát từ ô l[m,n] tới ô l[0,0]. Giả sử ta đang ở ô l[i,j]. Nếu ai=bj thì ta thêm ai vào dãy con rồi nhảy tới ô l[i-1,j-1]. Nếu aibj thì l[i,j]=l[i-1,j] hoặc l[i,j]=l[i,j-1]. Nếu l[i,j]=l[i-1,j] thì nhảy tới ô l[i-1,j], ngược lại thì nhảy tới ô l[i,j-1].
Sau đây là lời giải của bài toán. Chương trình được viết bằng ngôn ngữ Pascal:
uses crt; 
const fi='b2.inp';
var
 a:array[1..10] of integer;
 b:array[1..10] of integer;
 kq:array[0..10,0..10] of integer;
 i,j,maxa,maxb:integer;
 f:text;
procedure init;  
begin
  assign(f,fi);
 reset(f);
 i:=0;
  while not(eoln(f)) do
  begin
    inc(i);
    read(f,a[i]);
  end;
 maxa:=i;
  readln(f);
 i:=0;
  while not(eoln(f)) do
  begin
    inc(i);
    read(f,b[i]);
  end;
 maxb:=i;
  close(f);
 
end;
   
function max(a,b:integer):integer;  
begin
  if a>b then max:=a
  else max:=b;
 
end;
   
begin
  init;
  kq[0,0]:=0;
  for i:=1 to maxa do
    for j:=1 to maxb do
      if a[i]<>b[j] then kq[i,j]:=max(kq[i-1,j],kq[i,j-1])
      else kq[i,j]:=kq[i-1,j-1]+1;
  writeln('Do dai day con chung lon nhat:',kq[maxa,maxb]);
  i:=maxa;
 j:=maxb;
  while (i>0)or(j>0) do
    if a[i]=b[j] then
    begin
      write(a[i]);
      dec(i);
      dec(j);
    end
    else
      if kq[i-1,j]=kq[i,j] then dec(i)
      else dec(j);
 
end.
Với nội dung file ‘b2.inp’ chứa 2 dãy (a1,a2,..am) ,(b1,b2,..bn) sau:
1 2 3 2 3 4 6
6 9 8 7
Xét bài toán kinh điển về tối ưu tổ hợp:
Ví dụ 2: Cho cái túi chứa được trọng lượng tối đa là w. Có n đồ vật, đồ vật thứ i có khối lượng a[i] và giá trị c[i],  1<= i <=n. Tìm cách xếp đồ vật vào túi sao cho đạt giá trị lớn nhất.
Lời giải
Gọi f(k,v) là giá trị lớn nhất của túi đựng trọng lượng v và chỉ chứa các đồ vật từ 1 đến k.
Nếu k=1 thì f(k,v)=(v div a[1])*c[1]. Giả sử tính được f(s,t) với 1<S< ti?nh Ca^`n 1<t
Đặt: tg=v div a[k], f(k,v)=max{f(k-1,u)+x*c[k]}  (*) ,với x=0,1,2,...,tg, u=v-x*a[k]
Giá trị lớn nhất là f(n,w). Ta dùng mảng bản ghi a[1..n,1..w] chứa kết quả trung gian. Mỗi bản ghi a[k,v] chứa giá trị f(k,v) và giá trị x thoả mãn công thức (*).
Để xác định số lượng x[i] đồ vật i thoả mãn điều kiện tối ưu, ta xuất phát từ a[n,w] xác định được x[n]. Nhảy tới a[n-1,w-x[n]*a[n]] xác định được x[n-1]. Cứ như vậy tới x[1].
uses crt;
 
const
 n=5;
 w=17;
 fi='b3.inp';
 
type
 kq=record
   num,val:integer;
 end;
 
var
 a:array[1..10] of integer; {khoi luong}
 c:array[1..10] of integer; {Gia tri}
 i,j,tg,k,max,save:integer;
 f:text;
 b:array[1..n,1..w] of kq;
   
procedure init;  
begin
  assign(f,fi);
 reset(f);
  for i:=1 to n do
  begin
    read(f,a[i],c[i]);
  end;
  close(f);
 
end;
   
begin
  init;
  for j:=1 to w do
    for i:=1 to n do
    begin
      tg:=j div a[i];
      max:=0;
      for k:=0 to tg do
        if (b[i-1,j-k*a[i]].val+k*c[i])>max then
        begin
          max:=b[i-1,j-k*a[i]].val+k*c[i];
          save:=k;
        end;
      b[i,j].val:=max;
      b[i,j].num:=save;
    end;
  for i:=1 to n do
  begin
     for j:=1 to w do write(b[i,j].val:3);
    writeln;
  end;
  writeln('Max:',b[n,w].val);
  i:=n;
 j:=w;
  while i>=1 do
  begin
    if b[i,j].num>0 then writeln('Co ',b[i,j].num,' do vat ',i);
    j:=j-a[i]*b[i,j].num;
    dec(i);
  end;
  readln;
 
end.
Với nội dung file ‘b3.inp’ :hàng i chứa khối lượng a[i], giá trị c[i]:
3 4
4 5
7 10
8 11
9 13
Qua hai ví dụ trên chắc các bạn đã nắm được tư tưởng của thuật toán qui hoạch động cũng như cách cài đặt cho nó. Như các bạn thấy, cách phát biểu thuật toán rất đơn giản. Nếu biết cách vận dụng thuật toán một cách hợp lý, ta có thể giải được một lớp khá rộng các bài toán trong thực tế. Hi vọng thuật toán sẽ là công cụ tốt của các bạn trong quá trình học tập môn tin học.
Về Đầu Trang Go down
Xem lý lịch thành viên
 
Thuật toán cần học " THUẬT TOÁN QUY HOẠCH ĐỘNG"
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Văn Lang - Vạn Ninh :: Thảo luận-
Chuyển đến