Bài 4: GIẢI THUẬT QUY HOẠCH ĐỘNG

 Quy hoạch động (dynamic programming) giống với chia để trị, chia bài toán thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Tuy nhiên khác với chia để trị, thay vì sử dụng đệ quy, quy hoạch động lưu trữ lời giải của các bài toán con đã giải. Do vậy, nếu sau này ta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả đã được tính toán.

1. Bài toán đổi tiền

Tìm số lượng đồng xu tối thiểu cần thiết để đổi giá trị input (một số nguyên) thành tiền xu với mệnh giá coin_1,..., coin_d

a. Sử dụng đệ quy 

def RecursiveChange(money, coins):
    if money == 0:
        return 0
    MinNumCoins = float('inf')
    for i in range(len(coins)):
        if money >= coins[i]:
            NumCoins = RecursiveChange(money - coins[i], coins)
            if NumCoins + 1 < MinNumCoins:
                MinNumCoins = NumCoins + 1
    return MinNumCoins
print(RecursiveChange(9, [6, 5, 1]))

Mô tả cây đệ quy mathcha.io

b. Sử dụng quy hoạch động bottom-up

def DPChange(money, coins):
    MinNumCoins = [None]*(money + 1)
    MinNumCoins[0] = 0
    for m in range(1, money + 1):
        MinNumCoins[m] = float('inf')
        for i in range(len(coins)):
            if m >= coins[i]:
                NumCoins = MinNumCoins[m - coins[i]] + 1
                if NumCoins < MinNumCoins[m]:
                    MinNumCoins[m] = NumCoins
    return MinNumCoins[money]
print(DPChange(9, [6, 5, 1]))

2. Khoảng cách chỉnh sửa

Cho hai chuỗi ký tự, tìm số lượng tối thiểu các thao tác (chèn, xóa và thay thế các ký hiệu) để biến đổi chuỗi này thành chuỗi kia.

a, Tính toán khoảng cách chỉnh sửa

Cho hai chuỗi ký tự $A[1...n]$ và $B[1...m]$. Ta có các thao tác cơ bản như sau.

Chèn ảnh

Gọi $D(i,j)$ là khoảng cách chỉnh sửa của hai chuỗi ký tự $A[1...i], B[1...j]$, khi đó

$D(i,j)=min\begin{cases} D(i,j-1)+1\\ D(i-1,j)+1\\ D(i-1,j-1)+1 &\text{ if } A[i]\neq B[j]\\ D(i-1,j-1)&\text{ if } A[i]= B[j] \end{cases}$

Trường hợp cơ sở của bài toán là $D(0,j)=j$ hoặc $D(i,0)=i$

Ví dụ $A[1...n]=DIS$ và $B[1...m]=EDI$

Code python 

def edit_distance(str_1, str_2, n, m):
    if n == 0:
        return m
    if m == 0:
        return n
    if str_1[n-1] == str_2[m-1]:
        return edit_distance(str_1, str_2, n-1, m-1)
    return 1 + min(edit_distance(str_1, str_2, n, m-1),\
                   edit_distance(str_1, str_2, n-1, m),\
                   edit_distance(str_1, str_2, n-1, m-1))
str_1 = 'dis'
str_2 = 'edi'
print(edit_distance(str_1, str_2, len(str_1), len(str_2)))

Độ phức tạp về thời gian  của thuật toán là 

$\begin{aligned}T(n)&=\begin{cases} 1& \text{nếu } n=0 \\ 3T(n-1)+C &   \text{còn lại} \end{cases}\\ & = 3^n+nc=O(3^n) \end{aligned}$

Ta để ý thấy sau khi đệ quy sẽ sẽ có những bài toán đã lặp lại cho nên ta tạo ra một bộ nhớ phụ để lưu lại kết quả đã tính toán trước đó, nếu gặp bài toán tương tự chỉ việc lấy đáp án ra sử dụng. 

Code python 

def edit_distance(str1, str2, n, m):
    dp = [[-1 for j in range(m+1)] for i in range(n+1)]
    if n == 0:return m
    if m == 0:return n
    if dp[n][m] != -1:return dp[n][m]
    if str1[n-1] == str2[m-1]:
        if dp[n-1][m-1] == -1:
            dp[n][m] = edit_distance(str1, str2, n-1, m-1)
            return dp[n][m]
        else:
            dp[n][m] = dp[n-1][m-1]
            return dp[n][m]
    else:
        if dp[n][m-1] != -1:m1 = dp[n][m-1]
        else:m1 = edit_distance(str1, str2, n, m-1)
        if dp[n-1][m] != -1:m2 = dp[n-1][m]
        else:m2 = edit_distance(str1, str2, n-1, m)
        if dp[n-1][m-1] != -1:m3 = dp[n-1][m-1]
        else:m3 = edit_distance(str1, str2, n-1, m-1)
        dp[n][m] = 1 + min(m1, m2, m3)
        return dp[n][m]
str1, str2 = "dis", "edi"
n, m = len(str1), len(str2)
print(edit_distance(str1, str2, n, m))

Độ phức tạp trên là quá lớn cho nên ta xem xét hướng tiếp cận bottom-up (Từ dưới lên) như sau

Code python

def edit_string(str_1, str_2, n, m):
    dp = [[0 for j in range(m+1)] for i in range(n+1)]
    for i in range(n+1):
        for j in range(m+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str_1[i-1] == str_2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
    return dp[n][m]
str_2 = 'dis'
str_1 = 'edi'
print(edit_string(str_1, str_2, len(str_1), len(str_2)))

Độ phức tạp về không gian và thời gian là $O(n \times m)$, chúng ta có thể giảm độ phức tạp về không gia xuống còn $O(min{n,m})$. tham khảo giaithuatlaptrinh.com

Code python

def edit_distance(str1, str2, n, m):
    ED = [1*j for j in range(m+1)]
    for i in range(1,n+1):
        left,dag = i, i-1
        for j in range(1,m+1):
            if str1[i-1] == str2[j-1]:
                curr = min(ED[j]+1, left+1, dag)
            else: curr = min(ED[j]+1, left+1, dag+1)
            left, dag, ED[j] = curr, ED[j], curr
    return ED[m]
str1 = "dis"
str2 = "edi"
print(edit_distance(str1, str2, len(str1), len(str2)))

3. Bài toán cái túi

a, Bài toán cái túi với điều kiện lặp

Giả sử bạn có một chiếc ba lô có thể đựng được $W(kg)$  và $n$ vật phẩm nặng $w_1,w_2,...,w_n$ với giá trị lần lượt là $v_1,v_2,...,v_n$. Bạn hãy chọn vật phẩm bỏ vào ba lô để mang đi sao cho giá trị là cao nhất. Chú ý mỗi vật phẩm có thể lấy vô số lần.

Phân tích

Gọi $value(w)$ là giá trị lớn nhất của knapsack có tổng trọng lượng tối đa là $W$, khi đó $value(w) = max\left \{ value(w-w_i)+v_i \right \}$

Code python

def kanapsack(W, w_i, v_i):
    value = [None]*(W+1)
    value[0] = 0
    for w in range(1,W+1):
        value[w] = 0
        for i in range(len(w_i)):
            if w_i[i] <= w:
                val = value[w - w_i[i]] + v_i[i]
                if val > value[w]:
                    value[w] = val
    return value[W]
print(kanapsack(10,[6,3,4,2],[30,14,16,9]))

Độ phức tạp về thời gian là $O(n*W)$

b, Bài toán cái túi với điều kiện không lặp

Gọi $0 \leq w \leq W$ và $0 \leq i \leq n$, $value(w,i)$ là giá trị lớn nhất của knapsack, khi đó $value(w,i)=max\left \{value(w-w_i,i-1)+v_i,value(w,i-1)  \right \}$

Code python

def knapsack(W,w_i,v_i):
    value = [[None for j in range(W+1)] for i in range(len(w_i)+1)]
    for j in range(W+1):
        value[0][j] = 0
    for i in range(1,len(w_i)+1):
        value[i][0] = 0
    for i in range(1,len(w_i)+1):
        for w in range(1,W+1):
            value[i][w] = value[i-1][w]
            if w_i[i-1] <= w:
                val = value[i-1][w-w_i[i-1]] + v_i[i-1]
                if val > value[i][w]:
                    value[i][w] = val
    return value[len(w_i)][W]
print(knapsack(10,[6,3,4,2],[30,14,16,9]))

Độ phức tạp về thời gian là $O(n*W)$