Truy vết

Truy vết là một vấn đề thuờng gặp trong quy hoạch đông. Có nhiều bạn đã thực hành quy hoạch động nhiều rồi, tuy nhiên vẫn không tránh khỏi sự phức tạp của việc truy vết. Ở đây mình trình bày một số phương pháp giúp các bạn cảm thấy dễ dàng hơn trong việc truy vết.

1. Dùng dấu hiệu

Ta xem ví dụ với bài toán sau:

Có một bảng n*n. Một con rô bốt đi từ ô (1,1) đến ô (n,n). Ở ô (i,j), rô bốt có thể đi sang ô (i+1, j) hoặc (i, j+1). Trên mỗi ô vuông có một giá trị. Ta cần tìm một đừong đi của rô bốt sao cho thu được tổng giá trị lớn nhất có thể. (Xem hình vẽ)

Gọi F(i,j) là số điểm lớn nhất có thể ăn được khi vừa được di chuyển đến ô (i,j). Từ ô (i,j), ta có hai lựa chọn là đi sang phải hoặc đi xuống dưới, vì vậy, công thức QHD sẽ là:

F(i,j) = a[i][j] + max(F(i+1,j), F(i,j+1))

với F(i,j) = -oo nếu i>n hoặc j>n. F(n,n) = a[n][n]. Điều ta cần tìm là F(1,1). Kết quả là F[1][1]=36.

Cách giải

• Xét F[i][j],

• Nếu F[i][j]=F[i+1][j]+a[i][j] có nghĩa là ta phải đi xuống dưới.

• Nếu F[i][j]=F[i][j+1]+a[i][j] thì ta phải đi sang phải.

(Nếu F[i+1][j]=F[i][j+1] thì ta có thể đi đến huớng nào cũng được (vẫn đúng))

Ví dụ

Xét ô F[2][2]=24, F[3][2]+a[2][2] = 18+6 = 24

nên nếu ta đi đến ô a[2][2]=24 thì ta phải đi xuống dưới

Từ dấu hiệu này, ta tạo ra hàm Trace có nội dung như sau:

hàm Truy_vết;

biến i, j : số;

[

  i:=1; j:=1;

  hễ (i<n) hoặc (j<n) thì  [

    nếu F[i][j] = F[i+1][j] + a[i][j]

    thì [ i+=1; viết('Đi xuống dưới ô ',i,' - ',j); ]

    ngược_lại [ j+=1; viết('Sang phải đến ô ',i,' - ',j); ];

  ];

];

Ghi nhớ

Dùng dấu hiệu F[i'][j'] = F[i][j] + a[i][j]. Mỗi khi đến ô (i,j), ta tìm ô (i',j') thỏa mãn dấu hiệu trên.

2. Lưu hướng đi

Cách truy vết ở trên chỉ sử dụng được khi ta biết chắc chắn ô (i,j) đi được đến ô (i+1,j) và (i,j+1). Nếu bài toán có nhiều điều kiện hơn thì ta phải viết hàm Truy vết rất phức tạp. Thế nên, ta sẽ dùng mảng T để đánh dấu hướng đi của mình.

Cách giải

Trong hàm F, nếu hướng đi của chúng ta là sang phải, ta sẽ gán T[i][j]=0. Nếu đi xuống dưới, ta gán T[i][j]=1.

(hàm f ở đây mình không lưu vết để cho các bạn dễ hiểu về ý tưởng code)

hàm F(i, j : số) : số;

biến

  qd1 : số = -999999999;

  qd2 : số = -999999999;

[

  nếu (i>n) hoặc (j>n) thì trả_về -999999999; 

  nếu (i=n) và (j=n) thì trả_về a[n][n];

  qd1 := a[i][j] + F(i, j+1);

  qd2 := a[i][j] + F(i+1, j);

  F := max(qd1, qd2);

  nếu F=qd1 thì T[i][j] := 1;

  nếu F=qd2 thì T[i][j] := 0;

];

hàm Truy_vết;

biến i, j : số;

[

  i:=1; j:=1;

  hễ (i<n) hoặc (j<n) thì [

    nếu T[i][j] = 1

    thì [ i+=1; viết('Đi xuống dưới ô ',i,' - ',j); ]

    ngược_lại [ j+=1; viết('Sang phải đến ô ',i,' - ',j); ];

  ];

];

Ghi nhớ

Dùng mảng T để đánh dấu hướng đi.

3. Viết mã truy vết trong hàm quy hoạch động.

Hàm quy hoạch động của chúng ta tính các giá trị của các bài toán con, sau đó tìm ra kết quả. Hàm truy vết của chúng ta cũng phải tìm bài toán con là gì thì mình mới truy vết được. Vậy tại sao chúng ta không thể lồng nội dung hai hàm làm một.

(hàm F ở đây mình chưa có nhớ để cho code đơn giản)

hàm F(i, j : số; dò : boolean = sai) : số;

biến

  qd1 : số = -999999999;

  qd2 : số = -999999999;

[

  nếu (i>n) hoặc (j>n) thì trả_về -999999999;

  nếu (i=n) và (j=n) thì trả_về a[n][n];

  qd1 := a[i][j] + F(i, j+1);

  qd2 := a[i][j] + F(i+1, j);

  F := max(qd1, qd2);

  nếu dò thì

    nếu F = qd1 thì [ viết('Sang phải'); F(i, j+1, đúng); ]

    ngược_lại [ viết('Xuống dưới'); F(i+1, j, đúng); ];

];

Bắt_đầu

  nhập_vào;

  viết(F(1, 1));

  F(1, 1, đúng); // lời gọi lệnh truy vết

Kết_thúc.