Thuật toán quy hoạch động

Quang Tùng




Thuật toán quy hoạch động là một trong những phương pháp giải bài toán tối ưu nhanh và hiệu quả lại rất dễ làm. Sau đây xin giới thiệu lời giải một bài toán quy hoạch động khá cơ bản. Đó là bài PalinDrone trong đề thi IOI2000.
Nội dung : Cho một xâu ký tự có độ dài không quá 5000 ký tự. Hãy tìm cách thêm vào chuỗi tại bất kỳ vị trí nào trong chuỗi sao cho chuỗi mới tạo thành là một chuỗi đối xứng (Khi đảo ngược chuỗi này ta vẫn được chuỗi đó).
Yêu cầu: Số ký tự thêm là ít nhất và thời gian chạy không quá 2 giây. Lời giải được sử dụng các dẫn hướng {$r-},{$c-},{$s-}.
Input: file text có tên palin.inp gồm:
-         Dòng 1 số nguyên n: độ dài của chuỗi. (1<=n<=5000)
-         Dòng 2 là chuỗi ký tự. Không có dấu cách.
Ví dụ : 5
Abcdba
Output: file text có tên là palin.out gồm: Một số nguyên chỉ số ký tự cần thêm.
VD: 1 (Vì cần thêm ký tự d vào chuỗi để có abdcdba).
Thuật giải.
Nếu xét kỹ bài toán thì thêm vào một số ký tự để đạt được tính đối xứng thì những ký tự này phải giống những ký tự chưa đối xứng ở trong chuỗi. Như vậy những ký tự mà không cần thêm để đối xứng thì nó đã đối xứng rồi. Vì vậy chúng ta chỉ cần tìm chuỗi con đối xứng dài nhất (CCD) rồi chỉ cần thêm số ký tự để tạo tính đối xứng cho những ký tự ngoài chuỗi con này là xong. Điều này đảm bảo tính đối xứng của chuối và số ký tự cần thêm là ít nhất.
Nếu ta gọi F[i,j] là độ dài CCD của chuỗi nằm từ vị trí i đến vị trí j. Vậy độ dài CCD của cả chuỗi là F[1,n]. Đơn giản ta nhận thấy:
Nếu S[i]=S[j] thì F[i,j]:=F[i+1,j-1]+2;(1) (S: là mảng lưu chuỗi)
Nếu S[i]<>S[j] thì F[i,j]:=max(f[i,j-1],f[i+1,j]);(2)
Nhưng nếu sử dụng mảng f[i,j] thì cần 5000*5000*2 byte.(quá lớn)
Ta hãy chú ý vào công thức, F[i,j] chỉ phụ thuộc vào f[i+1,j-1] hoặc f[i,j-1] hoặc f[i+1,j-1]. Vậy ta sẽ sử dụng mảng:
D,d1,db:array[1..5000] of integer;
Trong đó tại lần lặp thứ i, d[j] chứa độ dài CCD của chuỗi đó có vị trí là j và i + j. d1[j] chứa độ dài CCD của chuỗi có vị trí là j và i+j-2. db là mảng phụ để gán giữa d và d1;
Như vậy ta có sơ đồ thuật toán sau:
Khởi tạo: Gán mảng d giá trị 1 và d1 giá trị 0.
Xử lý: {độ dài CCD của cả chuỗi sẽ là d[1] tại lần lặp thứ n-1}
For i:=1 to n-1 do
Begin
  Db:=d;{Lưu lại mảng d ở lần lặp i-1}
  For j:=1 to n-i do
    If s[j]=s[i+j] then d[j]:=d1[i+1]+2 {Tương tự như (1)}
     Else
        d[j]:=max(d[j],d[j+1]);
        {Tương tự như (2)}
    d1:=db; {lưu lại d1 băng lần lặp thứ i-2 của d}
end;
Writeln(‘Số ký tự cần thêm:’,n-d[1]);