Chưa phân loại

Phân tích thuật toán Quy hoạch động

s1, s2 = input().split()
t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
for i, x1 in enumerate(s1, 1):
for j, x2 in enumerate(s2, 1):
if x1 == x2:
t[i][j] = t[i – 1][j – 1] + 1
else:
t[i][j] = max(t[i][j – 1], t[i – 1][j])

print(t[-1][-1])

# Kết quả khi giải các bài toán con như bảng sau:
#

Quy hoạch động vs Memoization

Có một kỹ thuật khác gọi là “memoization” cũng có cách tiếp cận tương tự với quy hoạch động. Cả quy hoạch động và memoization đều dùng để tối ưu các vòng lặp mà có tính toán tượng tự nhau, trong đó kết quả của phép tính lớn hơn sẽ cần được tính toán dựa vào kết quả của phép tính nhỏ hơn. Memoization thường được sử dụng trong các phép tính đệ quy khi mà một tính toán bị lặp đi lặp lại nhiều lần. Nó sẽ lưu một bảng các giá trị tính được, mỗi khi có tính toán cần thực hiện, chúng ta sẽ tra bảng đó trước. Nếu bảng đã có kết quả rồi, chúng ta chỉ cần lấy ra là xong, nếu chưa, chúng ta sẽ tính toán như thường và tiếp tục lưu vào bảng.

Memoization không phải là một thuật toán theo đúng nghĩa, nó là một kỹ thuật được sử dụng trong lập trình thì đúng hơn. Để hiểu rõ hơn về kỹ thuật này, mình xin lấy ví dụ ngay với bài toán Fibonacci. Chúng ta sẽ sử dụng memoization như sau:

look_up = {0: 1, 1: 1}
def fib(n):
    if look_up.get(n) is None:
        look_up[n] = fib(n - 1) + fib(n - 2)
    return look_up[n]

Sự khác biệt chủ yếu là quy hoạch động sẽ thực hiện việc tính toán theo một thứ tự định trước, trong khi memoization duyệt theo chiều sâu. Quy hoạch động không bao giờ tính toán một bài toán con hai lần, tương đối giống với các phép tính đệ quy với memoization. Tuy nhiên memoization thì không bao giờ tính toán những phép tính thừa trong khi quy hoạch động sẽ cần tất cả mọi bài toán con. Đây là một phương pháp khá hay, nó chỉ tính toán những gì cần thiết và lưu kết quả này lại để sau này dùng lại khi nào được gọi mà không cần tính toán nữa.

Ưu điểm

  • Dễ code hơn
  • Không yêu cầu thứ tự thực hiện tính toán
  • Chỉ tính toán những gì cần thiết

Nhược điểm

  • Chỉ có một kiểu duyệt duy nhất
  • Thường chậm hơn quy hoạch động.

Các dạng toán quy hoạch động

Bài toán tối ưu

Bài toán tối ưu yêu cầu chúng ta phải tìm đáp án tốt nhất từ mục tiêu của bài toán. Cả hai ví dụ mình đưa ra ở trên đều thuộc loại bài toán này (một bài tìm số đồng xu ít nhất, một bài tìm xâu con dài nhất). Mối liên hệ của các bài toán con thuộc dạng này có công thức chúng là dp[s] = min(F1(dp[i], dp[j], ..., dp[k]), F2(dp[u], dp[v], ..., dp[w]), ..., Fl(dp[q], dp[p], ..., dp[z])), trong đó dp mảng lưu kết quả của các bài toán con đó.

Mỗi bài toán được giải dựa trên bài toán đã được giải trước đó. Đây chính là tính chất cấu trúc con tối ưu của mỗi bài toán. Với bài toán đồng xu, mỗi bài toán mới đều được giải bằng cách thêm đúng 1 đồng xu vào kết quả từ trước đó. Kết quả cuối cùng là kết quả tốt nhất thu được từ nhiều cách thêm đồng xu với khối lượng khác nhau.

Trước khi tính toán, mảng chứa kết quả có thể được điền đầy một giá trị trung tính nào đó. Giá trị trung tính có nghĩa là giá trị đó sẽ không bao giờ là đáp án cho bất kỳ bài toán con nào. Ví dụ khi cần tìm ra số đồng xu nhỏ nhất, chúng ta có thể điền mảng này bằng số dương lớn nhất, mọi tính toán tiếp theo sẽ cho ra một kết quả nhỏ hơn nhiều. Nếu không ra kết quả nào khác, chúng ta có thể coi như là không có một đáp án nào cho bài toán con đó.

Bài toán tổ hợp

Bài toán tổ hợp thường yêu cầu chúng ta tìm ra số cách khác nhau để thực hiện một việc gì đó. Nhiều bài thi code thường có kết quả rất lớn và họ yêu cầu chúng ta đưa đáp án dạng modulo của 10000007. Trong dạng bài toán này, công thức khi xây dựng các bài toán con sẽ là R[s] = F1(R[i], R[j], ..., R[k]) + F2(R[u], R[v], ..., R[w]) + ... + Fl(R[q], R[p], ..., R[z]). Sự khác biệt cơ bản của dạng bài toán này với dạng bài toán tối ưu là ở chỗ chúng ta cần tính tổng thay vì tìm số lớn nhất hoặc nhỏ nhất.

Trong mọi bài toán quy hoạch động, tính chất cấu trúc con tối ưu luôn là quan trọng nhất và cũng là tính chất khó đảm bảo nhất. Nếu cấu trúc con không được tối ưu, chúng ta sẽ tính toán theo một phương thức sai lầm và đương nhiên, kết quả thu được cũng không chính xác.

Với phần lớn các bài toán quy hoạch động, việc chia các bài toán con gối nhau khá dễ dàng trong khi đảm bảo cấu trúc con tối ưu thì khó hơn nhiều.

Mình sẽ đưa ra hai ví dụ tương tự nhau cho các bạn hiểu rõ hơn về những khó khăn để đảm bảo tính chất này.

Vẫn với bài toán đồng xu, chúng ta sẽ thay đổi một chút để có bài toán tổ hợp như sau:

Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S.

Các bài toán con sẽ tương tự như trước: dp(P) = k là số cách khác nhau để chọn ra các đồng xu có tổng khối lượng là P. Công thức đệ quy trong trường hợp này sẽ biến đổi theo bài toán như sau:

# Công thức đệ quy cho bài toán quy hoạch động
#   {dp[0] = 1;
#   {dp[P] = sum(dp[P-Wi]);   (for Wi <= P)
#
# Với đầu vào như sau: n = 3, S = 11, W = [1, 3, 5]
# Mảng kết quả quy hoạch động sẽ là

Bài toán tổ hợp cũng có thể có một giá trị trung tính. Bởi vì bài toán tổ hợp thường tính tổng, giá trị trung tính sẽ là 0. Bài toán tổ hợp yêu cầu tìm số cách khác nhau để làm gì đó, do đó giá trị 0 sẽ không ảnh hưởng gì đến đáp án. Một điểm đặc biệt quan trọng trong bài toán tổ hợp này là mỗi cách chúng ta chỉ tính đúng một lần. Nói thì dễ nhưng nhiều khi trong thực hành chúng ta hay gặp sai sót ở chỗ cực kỳ quan trọng này.


Tiếp tục thay đổi thêm một chút, chúng ta sẽ có bài toán tổ hợp như sau:




Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S. Với điều kiện, các cách lấy đồng xu là hoán vị của nhau không được coi là khác nhau.




Bài toán này khó hơn bài toán trước một chút. Nếu chúng vẫn chia các bài toán con như cũ thì không thể có được cấu trúc con tối ưu. Ví dụ, với các đồng xu 1, 3, 5 thì (1, 3) và (3, 1) đều cho kết quả là 4 nhưng chỉ được coi là 1 cách.


Với bài toán này, chúng ta sẽ chia bài toán lớn thành các bài toán con theo một cách tương đối khác. Chúng ta thấy rằng, kết quả (số cách chọn đồng xu) sẽ là tổng hợp của hai kết quả:


    

  • Số cách lấy đồng xu từ n - 1 đồng xu đầu tiên, tức là chúng ta coi như không có đồng xu nặng nhất
    • 

  • Số cách lấy đồng xu có chứa đồng xu nặng nhất.
    • 



Kết quả sẽ là tổng của hai kết quả trên. Các bạn thấy đó, với cách xây dựng bài toán con như thế này, chúng ta đã xây dựng các bài toán con gối nhau mà vẫn đảm bảo cấu trúc con tối ưu (kết quả bằng tổng của các bài toán con).


Nhân tiện, với cách chia bài toán như vậy, chúng ta có thể thu được lời giải bằng cách đệ quy đơn giản như sau:


n, S = map(int, input().split())
w = list(map(int, input().split()))


def count(arr, x):
    # Có 1 cách (lấy ra 0 đồng xu) cho tổng khối lượng bằng 0
    if x == 0:
        return 1
    # Không thể lấy được các đồng xu cho khối lượng âm
    if x < 0:
        return 0
    # Không thể lấy nếu không có đồng xu nào
        return 0
    # Kết quả là tổ hợp các bài toán con
    return count(arr[:-1], x) + count(arr, x - arr[-1])


print(count(w, S))


Tuy nhiên, như mình đã nói ở phần trước, nếu bạn đang thi code, cách làm này sẽ không mang lại bất cứ hy vọng đạt giải nào, do nó cực kỳ mất thời gian và bộ nhớ. Tuy nhiên, chúng ta có thể áp dụng quy hoạch động cho bài toán này rất dễ dàng sau khi có được cấu trúc con tối ưu với các bài toán con gối nhau:


n, S = map(int, input().split())
w = list(map(int, input().split()))

dp = [[0 for _ in range(n)] for _ in range(S + 1)]
for i in range(n):
    dp[0][i] = 1

for i in range(1, S + 1):
    for j in range(n):
        dp[i][j] = x + y


print(dp[-][n - 1])
# Kết quả tính toán với n = 3, w = [1, 3, 5] như sau:

Các bạn thấy đó, xây dựng các bài toán con gối nhau sao cho cấu trúc con vẫn tối ưu nhiều khi không đơn giản chút nào. Và mỗi bài toán quy hoạch động lại có những biến hóa khác nhau mà không theo một khuôn mẫu khô cứng nào. Ngay cả khi bạn có thể giải được rất nhiều bài toán quy hoạch động rồi, không gì có thể đảm bảo bạn có thể giải được các bài khác nữa. Đó cũng là một lý do khiến cho dạng bài này luôn “hot” trong các cuộc thi.


Tuyển dụng IT tại HCM, Hà Nội, Đà Nẵng


Quy hoạch động xuôi và ngược


Tất cả những ví dụ mình đã trình bày ở trên đều sử dụng quy hoạch động kiểu “ngược”. Ngược ở đây không phải là chúng ta duyệt các bài toán con từ lớn ngược về nhỏ. Mà quy trình sẽ như thế này: Duyệt qua tất cả các bài toán con (từ nhỏ đến lớn), với mỗi bài toán đó, chúng ta tính toán kết quả dựa vào bài toán con trước đó. Tất nhiên, bài toán con phía trước đã được giải theo quy trình duyệt, và với mỗi bài toán, chúng ta phải “nhìn ngược lại” bài toán trước đó, nên cách làm này gọi là quy hoạch động kiểu “ngược”.


Phương pháp quy hoạch động ngược này được sử dụng rộng rãi, vì nó khá tương ứng với suy nghĩ tự nhiên của chúng ta. Chúng ta đọc đề bài, suy nghĩ cách giải cho nó. Cách giải đó yêu cầu phải giải những bài toán nhỏ hơn, như kiểu làm toán ngày phải chứng minh các bổ đề vậy. Chúng ta tiếp tục suy nghĩ cho những bài toán con này, rồi tổng hợp để tìm ra lời giải cho bài toán lớn. Quá trình cứ tiếp tục như vậy, và quy hoạch động kiểu “ngược” này đang được xây dựng đúng như vậy.


Ngoài ra, về mặt lập trình, kiểu quy hoạch động này có mối quan hệ tương đối gần gũi với đệ quy. Một bài toán lớn được giải dựa vào các bài toán con tương tự nhau (và tương tự bài toán lớn) thì việc áp dụng đệ quy có thể là một phương pháp dễ dàng để code. Vì vậy, nhiều trường hợp, có thể coi quy hoạch động là một cách để tối ưu phương pháp đệ quy để giải một bài toán.


Ngoài kiểu quy hoạch động ngược này, có một kiểu quy hoạch động “xuôi”. Tuy không phổ biến, kiểu quy hoạch động xuôi cũng khá khó áp dụng, nhưng quy hoạch động “xuôi” mang đến cho chúng ta nhiều tiện lợi. Kiểu xuôi này cũng cần duyệt qua các bài toán con từ nhỏ đến lớn, nhưng với mỗi bài toán con, chúng ta tính toán kết quả và từ đó tìm cách thực hiện một số phép tính để giải bài toán lớn hơn. Nghĩa là, với mỗi bài toán con, chúng ta sẽ nhìn về phía trước để xem phải giải bài toán tiếp theo như thế này từ bài toán hiện tại.


Phương pháp này khó áp dụng hơn phương pháp ngược kia, và cũng không phải bài toán nào cũng áp dụng được. Với mỗi bài toán, việc xác định bước tiếp theo tương đối khó khăn, thậm chí việc kiểm tra tính đúng sai của phương pháp cũng không hề dễ dàng.


Như chúng ta đã thấy ở những phần trước, thông thường, mỗi bài toán cần phải giải bằng cách tổng hợp kết quả từ một vài bài toán con trước đó. Vì vậy, cách quy hoạch động xuôi này chỉ sử dụng một bài toán con để tính toán trước bài toán tiếp theo sẽ chỉ cho ra một phần của kết quả chứ không phải kết quả cuối cùng. Vì vậy, để thực hiện quy hoạch động xuôi, việc điền sẵn một mảng các giá trị trung tính là điều bắt buộc (sau đó chúng ta sẽ cộng dồn kết quả vào mỗi khi giải được một bài toán con mới).


Mình lấy vị với bài toán xâu con chung dài nhất. Với bài toán này, chúng ta có thể chọn giá trị trung tính là một số âm. Chúng ta sẽ tìm cách quy hoạch động xuôi như sau:


    

  • dp(0,0) = 0 là bài toán với hai xâu rỗng
    • 

  • Với mỗi bài toán dp(i, j) chúng ta sẽ tìm cách tính toán kết quả cho các bài toán lớn hơn. Lúc này, có 3 hướng phát triển tiếp:

      

    

    • 



n1, n2 = map(int, input().split())
s1, s2 = input().split()
s1 += 'x00'
s2 += 'x00'

# Điền sẵn giá trị trung tính
dp = [[-1] * (n1 + 2) for _ in range(n2 + 2)]
dp[0][0] = 0

for i in range(n1 + 1):
    for j in range(n2 + 1):
        tres = dp[i][j]
        # Phát triển theo hướng thứ nhất
        if dp[i + 1][j] < tres:
            dp[i + 1][j] = tres
        # Phát triển theo hướng thứ hai
        if dp[i][j + 1] < tres:
            dp[i][j + 1] = tres
        # Phát triển theo hướng thứ ba
        if s1[i] == s2[j] and dp[i + 1][j + 1] < tres + 1:
            dp[i + 1][j + 1] = tres + 1

print(dp[n1][n2])



Kết luận


Hy vọng qua bài viết này, mình đã trình bày được phần nào về thuật toán quy hoạch động. Về cơ bản, với mọi bài toán quy hoạch động, chúng ta có thể xây dựng các bài toán con gối nhau với cấu trúc con tối ưu là 90% công việc đã hoàn thành.


Tuy nhiên, cũng cần hiểu rằng, mặc dù thuật toán quy hoạch động là một thuật toán thần thánh, nó có thể giải được rất nhiều bài toán, nhưng nó không phải là chìa khóa vạn năng. Có một điều rất hiển nhiên: phương pháp tốt nhất để giải quyết mọi bài toán trong tin học là biết sử dụng và phối hợp uyển chuyển nhiều thuật toán, chúng ta không nên phát cuồng một thuật toán và cũng không nên coi thường bất cứ một thuật toán nào.


Tác giả: Trần Ngọc Anh – manhhomienbienthuy.bitbucket.io