Tìm hiểu thuật toán quy hoạch động

Bài viết sau được sưu tầm từ csharpviet.freevnn.com.

Mình cảm thấy bài viết rất hay nên sưu tầm tại đây để tiện tra cứu phục vụ học tập

Xin gửi lời cảm ơn chân thành tới tác giả vì bài viết rất hữu ích.

Nếu bạn là một lập trình viên, hoặc là một người đam mê tin học, chắc chắn bạn phải biết đến thuật toán quy hoạch động (QHĐ). Đây là một thuật toán mà theo quan niệm của tôi là rất hay. Nó được dùng để giải hầu hết các bài toán tối  ưu. Trong bài viết này, tôi sẽ giới thiệu với các bạn thuật toán này và 1 ví dụ bằng C# (ps: Trong bài viết này mình đã chuyển ví dụ qua ngôn ngữ C++)

1) Quy hoạch động là gì?

QHĐ thực chất là một phương pháp cải tiến hơn của phương pháp giải quyết vấn đề theo hướng phân rã. Cả 2 đều dựa trên nguyên lý "chia để trị". Nghĩa là ta chia bài toán ban đầu thành các bài toán nhỏ hơn và cứ như vậy cho đến khi các bài toán đủ nhỏ để có thể tìm ra nghiệm.

2) Ưu điểm:

Điểm khác biệt cơ bản giữa QHĐ và pp phân rã:

Phương pháp phân rã: 

    Giải quyết bài toán theo hướng top-down, nghĩa là để giải bài toán ban đầu, ta phải giải tất cả các bài toán con của nó. Đây là một phương pháp hay tuy nhiên pp này sẽ gặp hạn chế về mặt thời gian, tốc độ do phải tính đi tính lại nhiều lần một số bài toán con giống nhau nào đó.

Phương pháp quy hoạch động (QHĐ):

    Sử dụng nguyên lý bottom-up, nghĩa là  "đi từ dưới lên trên". Đầu tiên, ta sẽ phải giải các bài toán con đơn giản nhất, có thể tìm ngay ra nghiệm. Sau đó kết hợp các bài toán con này để tìm lời giải cho bài toán lớn hơn và cứ như thế  cho đến khi giải được bài toán được yêu cầu. Với pp này, mỗi bài toán con sau khi giải được đều được lưu trữ lại và đem ra sử dụng nếu cần. Do đó tiết kiệm bộ nhớ, cải thiện được tốc độ.

3) Hạn chế:

   Không phải lúc nào việc kết hợp các bài toán con lại với nhau cũng cho ta kết quả của bài toán lơn hơn. Hay nói cách khác, việc tìm kiếm "công thức truy hồi" rất khó khăn.

  Số lượng các bài toán con cần lưu trữ có thể rất lớn, không chấp nhận được vì dữ liệu và bộ nhớ máy tính không cho phép.

4) Kết luận:

  Quy hoạch động là 1 pp hay và hiệu quả. 

  Nó có thể giải được hầu hết các bài toán tôi ưu. Tuy nhiên, khi giải các bài toán theo hướng QHĐ, ta cần phải tìm công thức truy hồi thật chính xác và chứng mình tính tin cậy của nó.

5) Ví dụ minh họa:

Chuỗi A được gọi là con của chuỗi B nếu ta thu được chuỗi A bằng cách xóa 1 hay 1 số ký tự trong chuỗi B.

Yêu cầu:

    Cho 2 chuỗi A và B. Tìm chuỗi C là chuỗi con chung dài nhất của A và B. Nếu nhiều hơn 1 kq thì lấy kq bất kỳ.

Ví dụ:

  A = CEACEEC

  B = AECEAC

Kết quả:

  C = ECEC hoặc AEEC

Giả sử:
   Chuỗi A có độ dài n, chuỗi B có độ dài m.
+Gọi L[i,j] là độ dài lớn nhất của chuỗi con chung của 2 chuỗi:
     I: a[1],a[2],...,a[i] với i<= n 
     J: b[1], b[2],...,b[j] với j<=m


*Ta sẽ đi tìm công thức truy hồi tính L[i,j]


+TH1: Đơn giản nhất: i =0, j =0 =>L[i,j] = 0
+TH2: i>0 và j>0 và a[i]<> b[j], nghĩa là 2 chuỗi khác rỗng và ký tự cuối cùng của chúng khác nhau thì ta sẽ chọn phép tìm với chuỗi cho chuỗi con chung dài hơn để thực hiện bước tiếp theo. Như vậy ta sẽ lựa chọn 1 trong 2 chuỗi sau để so sánh:


a[1],a[2],...,a[i-1]
hoặc:
b[1],b[2],...,b[j-1];


+TH3: Nếu i>0 và j>0 và a[i] = b[j], khi đó ta sẽ so sánh tiếp ký tự phía trước ký tự i trong chuỗi I và ký tự j trong chuỗi J, nghĩa là L[i,j] = 1 + L[i-1,j-1].


Vậy là chúng ta đã tìm xong CT truy hồi cho bài toán. Ta sẽ  tạo một bảng 2 chiều để lưu kết quả. Bảng này gồm n+1 dòng và m+1 cột vì ta sẽ thêm cột 0 và dòng 0 vào để tính các nghiệm ban đầu.

Phần truy vết:


Ta sẽ bắt đầu truy vết để tìm chuỗi kết quả:


Đầu tiên, xuất phát từ ô L[n,m], ta sẽ hướng về ô L[0,0].
Quá trình truy vết dừng lại khi chạm tới cột 0 hoặc dòng 0.


+Nếu a[i] == b[j] thì ta chèn ký tự a[i] vào đầu chuỗi c ( c là chuỗi kết quả).
+Nếu a[i]<>b[j]: Ta tiến về ô L[i-1,j] nếu L[i-1,j]>L[i,j-1], và ngược lại, vì yêu cầu đặt ra là tìm chuỗi lớn nhất có thể nên ta ưu tiên giá trị L lớn hơn.


theo đó: Bộ test ban đầu ta sẽ được chuỗi C = AEEC
Như vậy ra đã giải quyết xong bài toán nhờ QHĐ


Chú ý: Trong chương trình sau, bảng phương án bắt đầu từ 0, hơi khác một chút với bản code gốc

/*:
 Chuong trinh sau lay y tuong tu nguon code tren csharpviet.freevnn.com
 Minh chi code lai theo ngon ngu C++
*/

#include<iostream>
#include<cstring>
#include<stdlib.h>
#define MAX 100

using namespace std;

char a[MAX],b[MAX],c[MAX];
int L[MAX][MAX];
/*:
 n,m lan luot la do dai cua xau a,b
 l[][] = bang phuong an luu do dai cua xau con chung tai moi vi tri i,j*/
 
int Max(int x, int y)
{
 return (x>y)?x:y;
}
 
//Nhap xau
void Init()
{
 cin>>a>>b;
}


void Optimize()
{
 int i,j;
 int _a = strlen(a), _b = strlen(b);

 //Tim bang phuong an dua vao cong thuc truy hoi
 
 //Khoi tao co cot và hang dau tien cua bang phuong an
 for(i=0;i<_a;++i)
 {
  if(a[i]==b[0])L[i][0] = 1;
  else L[i][0] = 0;
  
  if(b[i] == a[0])L[0][i] =1;
  else L[0][i] = 0;
 }
 
 for(i=1;i<_a;++i)
 {
  for(j=1;j<_b;++j)
  {
   if(a[i] == b[i])
   {
    L[i][j] = L[i-1][j-1] + 1;
   }
   else
   {
    L[i][j] = Max(L[i][j-1],L[i-1][j]);
   }
  }
 }
 

 //Truy vet(Trace)
 // Ket thuc vong for tren i = _a va j = _b
 int t = 0;
 --i;
 --j;
 while(i>= 0 && j>=0)
 {
  if(a[i] == b[j])
  {
   c[t] = a[i];
   ++t;
   --i;
   --j;
  }
  else
  {
   if(L[i-1][j]>L[i][j-1])
   {
    --i;
   }
   else
      --j;
  }
 }
 while(t>=0)
 {
        --t;
  cout<<c[t];
 
 
 }
}

int main()
{
 Init();
 Optimize();
 cout<<endl;
 system("pause");
 return 0;

}

****************