BIẾN ĐỔI XÂU_QUY HOẠCH ĐỘNG

BIẾN ĐỔI XÂU_QUY HOẠCH ĐỘNG

Dựa theo Giải thuật và lập trình của Lê Minh Hoàng                                                          

Cho xâu ký tự X, xét 3 phép biến đổi:

a)      Insert(i,C): i là số, C là ký tự: Phép Insert chèn ký tự C vào sau vị trí i của xâu X

b)      Replace(i,C): i là số, C là ký tự: Phép Replace thay ký tự tại vị trí i của xâu X bởi ký tự C.

c)      Delete(i): i là số, phép Delete xóa ký tự tại vị trí i của xâu.

Yêu cầu: Cho trước xâu Y, hãy tìm một số ít nhất các phép biến đổi trên để biến xâu X thành xâu Y.

Input: file văn bản STR.INP

+Dòng 1: Chứa xâu X ( độ dài <= 100)

+Dòng 2: Chứa xâu Y ( độ dài <= 100)

Output: file văn bản STR.OUT ghi các phép biến đổi cần thực hiện và xâu X tại mỗi phép biến đổi.

STR.INP	STR.OUT
PBBCEFAATZ QABCDABEFA	7 PBBCEFATZ -> Delete(9) -> PBBCEFAT PBBCEFAT ->Delete(8) -> PBBCEFA PBBCEFA -> Insert( 4, B ) -> PBBCBEFA PBBCEFA -> Insert( 4, A) -> PBBCABEFA PBBCABEFA ->Insert(4,D) ->PBBCDABEFA PBBCDABEFA -> Replace( 2, A) -> PABCDABEFA PABCDABEFA -> Replace(1, Q) -> QABCDABEFA

Cách giải:

Đối với xâu ký tự thì việc xóa, chèn sẽ làm cho các phần tử phía sau bị biến đổi bị đánh lại chỉ số, gây khó khăn cho việc quản lý vị trí. Để khắc phục điều này, ta sẽ tìm một thứ tự biến đổi thỏa mãn: Phép biến đổi tại vị trí i bắt buộc phải được thực hiện sau các phép biến đổi tại vị trí i+1, i+2,….

Ví dụ: X = ‘ABCD’;

Insert(0,E) sau đó Delete(4) cho ra X = ‘EABD’. Cách này không tuân thủ nguyên tắc.

Delete(3) sau đó Insert(0,E) cho ra X =’EABD’. Cách này tuân thủ nguyên tắc đề ra.

Nói tóm lại ta sẽ tìm một dãy biến đổi có vị trí thực hiện giảm dần.

3.1.Công thức truy hồi:

Giả sử m là độ dài xâu X và n là độ dài xâu Y. Gọi F[i,j] là sô phép biến đổi tối thiểu để biến xâu gồm i ký tự đầu của xâu X: X[1…i] thành xâu gồm j ký tự đầu của xâu Y: Y[1…i].

+Nếu X[m] = Y[n] thì ta chỉ cần biến đoạn X[1…m-1] thành Y[1…n-1]. Tức là trong trường hợp này : F[m,n] = F[m-1,n-1].

+Nếu X[m] khác Y[n] thì tại vị trí X[m] ta có thể sử dụng 1 trong 3 phép biến đổi: Hoặc chèn sau vị trí của X, một ký tự đúng bằng Yn

Thì khi đó F[m,n] sẽ bằng 1 phép chèn vừa rồi cộng với số phép biến đổi biến dãy X[1…m] thành dãy Y[1…n-1]: F[m,n] = 1+ F[m,n-1]

Hoặc thay vị trí m của X bằng một ký tự đúng bằng Y[n]:

Khi đó F[m,n] sẽ bằng 1 phép thay thế vừa rồi cộng với số phép biến đổi biến dãy X[1…m-1] thành dãy Y[1..n-1]: F[m,n] = 1 + F[m-1,n-1].

Hoặc xóa vị trí thứ m của X:

Thì khi đó F[m,n] sẽ bằng 1 phép xóa vừa rồi cộng với số phép biến đổi biến dãy X[1….m-1] thành dãy Y[1…n]:  F[m,n] = 1 + F[m-1,n].

Vì F[m,n] phải là nhỏ nhất có thể, nên trong trường hợp X[m] khác Y[n] thì:

F[m,n] = min(F[m,n-1],F[m-1,n-1],F[m-1,n]) + 1, if Xm khác Yn

3.2.Cơ sở quy hoạch động:

+F[0,j] là số phép biến đổi xâu rỗng thành xâu gồm j ký tự đầu của F. Nó cần tối thiểu j phép chèn:

 F[0,j] = j.

+F[i,0] là số phép biến đổi xâu gồm i ký tự đầu của S thành xâu rỗng, nó cần tối thiểu i phép xóa:

F[i,0] = i;

Vậy đầu tiên của bảng phương án F ( cỡ [0….m,0…n]) được khởi tạo hàng 0 và cột 0 là cơ sở quy hoạch động. từ đó dùng công thức truy hồi tính ra tất cả các phần tử bảng B.

Sau khi tính xong thì F[m,n] cho ta biết số phép biến đổi tối thiểu.

Truy vết:

Nếu X[m] = Y[n] thì ta chỉ việc xét tiếp F[m-1,n-1].

Nếu không, xét 3 trường hợp:

+Nếu F[m,n] = F[m,n-1] + 1 thì phép biến đổi đầu tiên là Insert(m,Y[n])

+Nếu F[m,n] = F[m-1,n-1] + 1 thì phép biến đổi đầu tiên được sử dụng là: Replace(m,Y[n]).

+Nếu F[m,n] = F[m-1,n]+1 thì phép biến đổi đầu tiên được sử dụng là: Delete(m);

Đưa về bài toán với m,n nhỏ hơn truy vết cho tới khi về F[0,0]

Ví dụ: X=’ABCD’; Y = ‘EABD’ bảng phương án là:

F	0    1  2  3  4
0 1 2 3 4	0          1  2  3  4                         1           1  1  2  3                        2            2  2  1  2                        3            3  3  2  2                       4            4  4  3  2

 Lưu ý: khi truy vết đê tránh truy nhập ra ngoài bảng, nên tạo viền cho bảng.

function Min3(x,y,z: Integer) :Integer; 
{ Cho gia tri nho nhat trong 3 gia tri x,y,z }
var
  t: Integer;
begin
  if x<y then t := x else t := y;
  if z<t then t:= z;
  Min3 := t;
  
end;

procedure Optinmize;
var
  i,j: Integer;
begin
   { Khoi tao vien cho bang phuong an }
   for i:= 0 to m do F[i,-1] := max + 1;
   for j:= 0 to n do F[-1,j] := max + 1;
   { Luu co so quy hoach dong }
   for j := 0 to n do F[0,j] := j;
   for i := 1 to m do F[i,0] := i;
   { Dung cong thuc truy hoi tinh toan bang phuong an }
   
   for i := 1 to m do
     for j := 1 to n do
       if X[i] = Y[j] then F[i,j] := F[i-1,j-1]
       else F[i,j] := Min3(F[i,j-1],F[i-1,j-1],F[i-1,j]) +1;

end;

procedure Trace; { Truy vet }
var
  fo:Text;
begin
  Assign(fo, OutputFile); Rewrite(fo);
  WriteLn(fo, F[m,n]);
  { F[m,n] chinh la so it nhat cac phep bien doi can thuc hien }
  
  while( m<>0) or(n<>0) do {Vong lap ket thuc khi m = n =0}
    if X[m] = Y[n] then { Hai ky tu cuoi cua 2 xau giong nhau}
      begin
        Dec(m); Dec(n);
        { Chi viec truy cheo tren bang phuong an }
      end
    else {Tai day can mot phep bien doi}
      begin
        Write(fo, X,'->');{In ra xau X truoc khi bien doi}
        if F[m,n] = F[m,n-1] +1 then {Neu day la phep chen}
         begin
           Write(fo,'Insert'(',m',',',Y[n],')');
           Insert(Y[n],X,m+1);
           Dec(n);{Truy sang phai }
         end
        else
          if F[m,n] = F[m-1,n-1] + 1 then { Neu day la phep thay }
            begin
              Write(fo,'Replace(',m,',',Y[n],')');
              X[m] := Y[n];
              Dec(m);Dec(n); {Truy cheo len tren }
            end;
          else {Neu day la phep xoa }
            begin
              Write(fo, 'Delete(',m,')');
              Delete(X,m,1);
              Dec(m); {Truy len tren}
            end;
            WriteLn(fo,'->',X); { In ra xau X sau phep bien doi }
      end;
    Close(fo);
end;
          
            
   

// Code Implementation:
        //BIEN DOI XAU
#include<iostream>
#include<fstream.h>
#define max 100

char X[max<<1+1], Y[max<<1+1];
int F[max+2][max+2];
int m,n;

void Enter()
{
     fstream f;
     f.open("BIEN_DOI_XAU.txt");
     f>>X;
     f>>Y;
     m = strlen(X) -1;
     n = strlen(Y) -1;
     f.close();
}

int Min3( int x, int y, int z)
{
    int t;
    if( x<y) t = x;
    else t = y;
    if(z<t) t =z;
    return t;
}

void Optimize()
{
     int i,j;
     //Khoi tao bang phuong an
     for( i =0;i<=m;++i)
       F[i][-1] = max+1;
     for( i =0;i<=n;++i)
       F[-1][j] = max+1;
     //Luu co so quy hoach dong
     for( i =0;i<=n;++i)
       F[0][i] = i;
     for( i=1;i<=n;++i)
       F[i][0] = i;
     //Dung cong thuc truy hoi tinh toan bang phuong an
     for( i=1;i<=n;++i)
      for( j =1;j<=m;++j)
      {
           if(X[i] == Y[j])F[i][j] = F[i-1][j-1];
           else F[i][j] = Min3(F[i][j-1],F[i-1][j-1],F[i-1][j])+1;
      }
}

void Trace() //Truy vet
{
     std::cout<<" The best result is: "<<F[n][m];
}
main()
{
      Enter();
      Optimize();
      Trace();
      system("pause");
      return 0;
}