Dynamic Programming-Ví dụ giải một số bài toán trong thực tế

Trong bài lần trước – Dynamic Programming – Quy hoạch động trong lập trình mình đã giới thiệu định nghĩa và nêu ra các bước để giải một bài toán bằng Dynamic Programming. Trong bài này mình sẽ trình bày một số ví dụ về việc áp dụng quy hoạch động để giải các bài toán trong thực tế.

Dựa vào ý tưởng của giải thuật quy hoạch động chúng ta có thể thấy ngay một bài toán trong Dynamic Programming có thể cài đặt bằng phương pháp đệ quy (recursion). Tuy nhiên kỹ thuật này có một số hạn chế như mất nhiều thời gian thực hiện, đòi hỏi nhiều chi phí bộ nhớ. Chính vì vậy trong thức tế khi cài đặt quy đặt quy hoạch động thay vì dùng đệ quy chúng ta có thể dùng một mảng hai chiều để lưu trữ kết quả của bài toán con giúp chương trình giảm thiều thời gian tính toán và chi phí bộ nhớ. Thậm chí nếu kết quả bài toán con đang cần tính hiện tại chỉ phụ thuộc vào kết quả của bài toán con trước đó chúng ta chỉ cần dùng hai mảng một chiều là đủ.

Sau đây mình sẽ đi vào chi tiết các bước dùng Dynamic Programming để giải một số bài toán.

Bài toán 1: Dãy con đơn điệu không giảm dài nhất (Longest Increasing Subsequence)

Có lẽ đây là một trong những bài toán điển hình có thể giải bằng quy hoạch động. Đề bài như sau:

Chuỗi A gồm N phần tử là các số nguyên {a1, a2…,an}. Hãy tìm chuỗi con đơn điệu không giảm dài nhất của A. Chuỗi con thoả mãn bài toán là dãy được xây dựng các phần tử của chuỗi A giữ nguyên thứ tự, có thể xoá đi một số phần tử hoặc không và từ trái sang phải các số trước nhỏ hơn hoặc bằng số đứng sau.

Ví dụ:

Input:

Dãy A: 2, 0, 3, 1, 8, 7, 4, 20, 10, 5, 5

Output:

Dãy con đơn điệu dài nhất không giảm của A là : 2, 3, 4, 5, 5

Phân tích:

Dễ dàng thấy =) bài toán hội tụ đầy đủ điều kiện của nguyên lý tối ưu Bellman và dãy con dài nhất thoả mãn bài toán có thể xây dựng được từ các dãy con ngắn hơn. Vì vậy có thể giải quyết bài toán này bằng phương pháp DP (dynamic programming). Chúng ta sẽ áp dụng theo hướng tiếp cận Bottom-Up. Một lần nữa ta dễ dàng tìm được công thức truy hồi sau =)

Gọi L[i] là độ dài dãy con đơn điều dài nhất không giảm tìm được trong chuỗi {A1, A2 … Ai} ta có:

L[i] = Max { L[i], L[j] + 1 Với mọi j < i và A[j]<=A[i]}

Code (Python 3):

def findSubsequence(self, a: List[int]) -> List[int]:
    n = len(a)
    l = [1] * n  # L[i] chứa độ dài của dãy kết quả khi xét đến phần tử thứ i
    trace = [-1] * n  # trace[i] = j A[i] đứng trước A[j] trong dãy kết quả
    for i in range(0, n):
        for j in range(0, i):
            if a[i] >= a[j] and l[i] < l[j] + 1:
                l[i] = l[j] + 1
                trace[i] = j
    result = []
    imax = l.index(max(l))
    i = imax
    while i > -1:
        result.insert(0, a[i])
        i = trace[i]
 
    return result

Độ phức tạp tính toán của giải thuật trên là O(N^2). Longest Increasing Subsequence là một bài toán có rất nhiều phương pháp giải, để đạt được độ phức tạp O(N logN) có thể áp dụng giải thuật tham lam kết hợp tìm kiếm nhị phân Greedy with Binary search tham khảo tài liệu ở đây Princeton.edu. Các bạn có thể xem code của mình ở đây nhé github.com

Bài toán 2:

Một bài toán cổ điển nữa có thể giải bằng phương pháp DP mà mình muốn giới thiệu hôm nay là Biến đổi xâu hay Khoảng cách Levenshtein (Levenshtein Distance). Bài toán được phát biểu như sau:

Khoảng cách Levenshtein giữa hai chuỗi kỹ tự S1 và S2 là số thao tác ít nhất cần thực hiện để biến S1 thành S2. Các thao tác bao gồm: chèn, thay thế và xoá một ký tự. Ví dụ

Khoảng cách Levenshtein giữa hai chuỗi “kitten” và “sitting” là 3:

  • 1. kitten -> sitten (thay thế k bằng s)
  • 2. sitten -> sittin (thay thế e bằng i)
  • 3. sittin -> sitting (chèn thêm g vào cuối)

Input:

Cho hai xâu X có độ dài là N và xâu Y có độ dài là M. Dùng các phép biến đổi chèn, thay thế và xoá một ký tự để biến đổi X thành Y.

Output:

Số phép biến đổi ít nhất cần thực hiện để biến X thành Y.

Phần tích:

Một lần nữa chúng ta lại dễ dang thấy được bài toán này có thể chia ra thành các bài toán con. Để tính số lần thực hiện phép biến đổi của X thành Y ta có thể dựa vào số thao tác cần thực hiện để biến đổi các xâu con của X thành các xâu con của Y. Cấu trúc các bài toán con này thoả mãn nguyên lý Bellman vì vậy có thể áp dụng DP để giải bài toán này theo hướng tiếp cận Bottom-Up. Ta dễ dàng tìm được công thức truy hồi như sau:

Gọi L[i,j] là số phép biến đổi ít nhất cần thực hiện để biến đổi xâu con x1,x2,..,xi thành xâu con y1,y2,…,yj

Nếu x_{i} = y_{j} thì L[i,j] = L[i-1,j-1]

Nếu x_{i} <> y_{j} ta xét 3 trường hợp như sau:

  • Xoá xi và biến đổi x_{1}, x_{2},...,x{i-1} thành y_{1}, y_{2},...,y{j} ta có L[i,j] = L[i-1, j] +1
  • Biến đổi x_{1}, x_{2},...,x_{i} thành y_{1}, y_{2},...,y_{j-1} sau đó chèn y_{j} vào trước x_{i}. Ta có L[i,j] = L[i,j-1]+1
  • Biến đổi x_{1}, x_{2},...,x_{i-1} thành y_{1}, y_{2},...,y_{j-1} sau đó thay thế x_{i} bằng y_{j}. Ta có L[i,j]= L[i-1,j-1] + 1

Từ 3 trường hợp trên ta có nếu x_{i} <> y_{j} L[i,j] = min(L[i-1,j], L[i,j-1], L[i-1,j-1]) + 1

Kết quả cần tìm của bài toán chính là L[N,M]

Code: (python 3)

class Solution:
    def computeLevenshteinDistance(self, X: str, Y: str) -> int:
        n = len(X)
        m = len(Y)
        # khởi tạo ma trận levenshtein
        l = [[0 for j in range(m + 1)] for i in range(n + 1)]
        ## nếu Y là xâu rỗng để biến đổi Xi thành Y ta phải xoá đi i ký tự
        for i in range(0, n + 1):
            l[i][0] = i
        ## nếu X là xâu rỗng để biến đổi X thành Yj ta cần xoá đi j ký tự
        for j in range(0, m + 1):
            l[0][j] = j
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if X[i - 1] == Y[j - 1]:
                    l[i][j] = l[i - 1][j - 1]
                else:
                    l[i][j] = min(l[i - 1][j], l[i][j - 1], l[i - 1][j - 1]) + 1
 
        return l[n][m]

Độ phức tạp của giải thuật trên là O(N*M). Trong lời giải trên mình dùng một mảng 2 chiều để ghi nhớ các kết quả của các bài toán con nhưng vì bài toán con hiện tại chỉ phụ thuộc vào kết quả của bài toán con ở ngay mức trước nên thực tế ta chỉ cần 2 mảng 1 chiều đề giải bài toán này.

Vậy là trong bài này mình đã đưa ra 2 ví dụ điển hình của bài toán có thể giải bằng phương pháp Dynamic Programming và thực tế là DP chỉ là một phương pháp để tìm ra kết quả của bài toán chứ không phải lúc nào cũng là phương pháp tối ưu. Hy vọng qua bài này giúp các bạn hiểu hơn về cách áp dụng DP để giải quyết một vấn để trong thực tế. Gook luck and Having fun =)

Tags: 
Thuật toán Java
Fivestar: 
No votes yet
File: 
PDF icon longestincreasingsubsequence.pdf