Hậu viết blog: Bài 3: GIẢI THUẬT CHIA ĐỂ TRỊ

Chia để trị trong chiến tranh

Thuật ngữ chia để trị áp dụng trong chiến tranh có ý nghĩa là đánh bại một vài nhóm đối thủ nhỏ hơn thì dễ hơn là đánh bại một nhóm lớn. Tương tự các thuật toán chia để trị tận dụng lợi thế của việc chia nhỏ vấn đề thành một hoặc nhiều bài toán con để giải chúng độc lập.

Các bước thực hiện giải thuật chia để trị.

Bước 1: Chia bài toán thành các bài toán con không trùng lặp
Bước 2: Giải bài toán con bằng đệ quy
Bước 3: Kết hợp các kết quả

Ví dụ 1: Tìm kiếm tuyến tính

Tìm kiếm tuyến tính là một ví dụ tầm thường cho việc sử dụng giải thuật chia để trị để giải quyết bài toán này.

Ví dụ 2: Tìm kiếm nhị phân

Input: Một danh sách $A[low,...,high]$ đã được sắp xếp và một từ khóa $k$ .

Output: Nếu $A[i]=k$ thì kết quả là $i$ , nếu $A[i]<k$ thì kết quả là chỉ số $i$ lớn nhất để $A[i]<k$ , nếu

$k<A[low]$ thì kết quả là $low-1.$

Code sử dụng đệ quy trong python:

def BinarySearch(A,low,high,key):
    if high<low:
        return low-1
    mid=(low+high)//2
    if A[mid]==key:
        return mid
    elif key<A[mid]:
        return(BinarySearch(A,low,mid-1,key))
    elif key>A[mid]:
        return(BinarySearch(A,mid+1,high,key))

Code sử dụng vòng lặp trong python.

def BinarySearch(A,low,high,key):
    while low<=high:
        mid=(low+high)//2
        if A[mid]==key:
            return mid
        elif key<A[mid]:
            high=mid-1
        else:
            low=mid+1
    return low-1

Thời gian chạy của thuật toán $T(n)=T \left(\left \lfloor \frac{n}{2} \right \rfloor \right) +C=T \left(\left \lfloor \frac{n}{2^2} \right \rfloor \right) +2C=T \left(\left \lfloor \frac{n}{2^k} \right \rfloor \right) +kC \leq T \left(\frac{n}{2^k} \right)+kC=T(1)+log_2(n).C$ $=T(0)+C+log_2(n).C=C+C+log_2(n).C=(log_2(n)+2).C \leq log_2(n).K$

Vậy $T(n)=O(log_2(n))$

Ví dụ 3: Bài toán phép nhân đa thức (thuật toán karatsuba)

Input: Cho 2 đa thức $A$ và $B$ có bậc là $n-1:$

$A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_1x+a_0$

$B(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0$

Output: Tích hai đa thức $A.B$

$C(x)=c_{2n-2}x^{2n-2}+c_{2n-3}x^{2n-3}+...+c_1x+c_0$

Trong đó:

$c_{2n-2}=a_{n-1}.b{n-1}$

$c_{2n-3}=a_{n-1}.b_{n-2}+a_{n-2}.b_{n-1}$

$...$

$c_2=a_2.b_0+a_1.b_1+a_0.b_2$

$c_1=a_1.b_0+a_0.b_1$

$c_0=a_0.b_0$

Code Python:

def MultPoly(A,B,n):# n là độ lớn của danh sách A hoặc B
    C=[0]*(2*n-1)
    for i in range(len(A)):
        for j in range(len(B)):
            C[i+j]=C[i+j]+A[i]*B[j]
    return C

Thời gian chạy của thuật toán là $O(n^2)$

Phân tích chia để trị(Karatsuba).

$A(x)=D_1(x)x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0(x)$ trong đó

$D_1(x)=a_{n-1}x^{n-1-\left \lfloor \frac{n}{2} \right \rfloor}+a_{n-2}x^{n-2-\left \lfloor \frac{n}{2} \right \rfloor}+...+a_{\left \lfloor \frac{n}{2} \right \rfloor}$

$D_0(x)=a_{\left \lfloor \frac{n}{2} \right \rfloor -1}x^{\left \lfloor \frac{n}{2} \right \rfloor -1}+a_{\left \lfloor \frac{n}{2} \right \rfloor -2}x^{\left \lfloor \frac{n}{2} \right \rfloor -2}+...+a_0$

$B(x)=E_1(x)x^{\left \lfloor \frac{n}{2} \right \rfloor}+E_0(x)$

$AB=(D_1x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0)(E_1x^{\left \lfloor \frac{n}{2} \right \rfloor}+E_0)=D_1E_1x^{2\left \lfloor \frac{n}{2} \right \rfloor}+(D_1E_0+D_0E_1)x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0E_0$

$=D_1E_1x^{2\left \lfloor \frac{n}{2} \right \rfloor}+\left [(D_1+D_0)(E_1+E_0)-D_1E_1-D_0E_0\right ]x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0E_0$

Tính $D_1E_1,(D_1+D_0)(E_1+E_0),D_0E_0$ .

Thời gian chạy của thuật toán là $T(n)=3T(\frac{n}{2})+kn=3^2T(\frac{n}{2^2})+(1+\frac{3}{2})kn=...=3^iT(\frac{n}{2^i})+\sum_{i=0}^{i-1} \left (\frac{3}{2} \right )^i kn$

( $kn$ là thời gian cộng hai dãy $D_1+D_0$ và $E_1+E_0$ )

Ta có $\sum_{i=0}^{i-1} \left ( \frac{3}{2} \right )^i =2n^{\log_{2}{3}-1}-2$ và $a^{\log_bc}=\left (b^{\log_ba} \right )^{\log_bc}=\left (b^{\log_bc} \right )^{\log_ba}=c^{log_ba}$

Quá trình kết thúc khi $2^i=n \Rightarrow i=log_2(n).$ Khi đó $T(n)=n^{log_23}T(1)+2kn^{\log_23}-2kn$

Vậy độ phức tạp của thuật toán là $T(n)=O(n^{log_2(3)})=O(n^{1.58})$

Code python

import numpy as np
def MultPoly(A, B):
  n, m = len(A), len(B)
  if n == 1:
    return B*A[0]
  if m == 1:
    return A*B[0]
  mid_n, mid_m = n//2, m//2
  mid = min(mid_n, mid_m)
  D1, D0, E1, E0 = A[:mid_n], A[mid_n:], B[:mid_m], B[mid_m:]
  D1D0 = np.append(D1 + D0[:len(D1)], D0[len(D1):])
  E1E0 = np.append(E1 + E0[:len(E1)], E0[len(E1):])
  D1xE1 = MultPoly(D1, E1)
  D0xE0 = MultPoly(D0, E0)
  D1D0xE1E0 = MultPoly(D1D0, E1E0)
  D1D0xE1E0 = np.append(D1D0xE1E0[:len(D1xE1)] - D1xE1, D1D0xE1E0[len(D1xE1):])
  D1D0xE1E0 = np.append(D1D0xE1E0[:len(D0xE0)] - D0xE0, D1D0xE1E0[len(D0xE0):])
  AxB = np.zeros(n + m - 1)
  AxB[ : mid_n + mid_m -1] += D1xE1
  AxB[mid_n + mid_m : n + m - 1] += D0xE0
  AxB[mid : mid + len(D1D0xE1E0)] += D1D0xE1E0
  return AxB
A = np.array([1,2,3,4])
B = np.array([4,3,2,1])
MultPoly(A,B)

Chú ý : Nếu độ lớn của A và B không bằng nhau thì mình có ý tưởng không hay lắm như sau là chèn phần tử không vào phía trước mảng bé hơn sau khi được kết quả ta xóa đi phần tử không ở phía trước kết quả

Định lý Master.

Chúng ta thấy sử dụng giải thuật chia để trị để giải một bài toán thì phải sử dụng đệ quy. Như vậy khi đánh giá độ phức tạp của thuật toán chúng ta phải giải được hệ thức truy hồi mà đệ quy tạo ra. Việc này rất mất thời gian cho nên định lý Master ra đời.

Phát biểu định lý Master

Nếu $T(n)=aT \left (\left \lceil \frac{n}{b} \right \rceil \right)+O(n^d)(a >0,b>1,d \geq 0),$ thì:

$T(n)=\begin{cases} O(n^d)& \text{nếu } d> \log_{b}a \\ O(n^d \log_bn)& \text{nếu } d = \log_{b}a\\ O(n^{\log_ba})& \text{nếu } d < \log_{b}a \end{cases}$

Chứng minh định lý Master.

Để tính tổng trên ta cần tới công thức chuỗi hình học (geometric series)

Cho $r \neq 0, \text{ và tổng }S=a+ar+ar^2+ \cdots+ar^{n-1}$

Ta có $(1-r)S=a-ar+ar-ar^2+ar^2-ar^3+ \cdots-ar^{n-1}+ar^{n-1}-ar^n=a-ar^n$

Suy ra $S=\frac{a-ar^n}{1-r}=a\frac{1-r^n}{1-r}$

Tổng $\sum_{i=0}^{\log_bn}\left(\frac{a}{b^d}\right)^i=\frac{1-\left(\frac{a}{b^d}\right)^{\log_bn}}{1-\frac{a}{b^d}}=\frac{1-\frac{n^{\log_ba}}{n^d}}{1-\frac{a}{b^d}}(\frac{a}{b^d}\neq 0)$

Trường hợp 1: Nếu $d>\log_ba$ suy ra $\frac{a}{b^d}<1$ thì

$\sum_{i=0}^{\log_bn}\left(\frac{a}{b^d}\right)^iO(n^d)=O(n^d)$

Trườn hợp 2: Nếu $d=\log_ba$ suy ra $\frac{a}{b^d}=1$ thì

$\sum_{i=0}^{\log_bn}\left(\frac{a}{b^d}\right)^iO(n^d)=\sum_{i=0}^{\log_bn}O(n^d)=(1+\log_bn)O(n^d)=O(n^d\log_bn)$

Trường hợp 3: Nếu $d<\log_ba$ suy ra $\frac{a}{b^d}>1$ thì

$\sum_{i=0}^{\log_bn}\left(\frac{a}{b^d}\right)^iO(n^d)=\frac{\frac{n^{\log_ba}}{n^d}-1}{\frac{a}{b^d}-1}O(n^d)=O(n^{\log_ba})$

Tổng quát định lý Master ta có phương pháp 'bom tấn'. Giả sử $T(n)=\sum_{i=1}^{k}a_iT(\frac{n}{b_i})+f(n)(\forall i \text{ } a_i>0,b_i>1,f(n)=O(n^d)$

Năm 1998, Mohamad Akra và Louay Bazzi chứng mình tổng trên có dạng như sau:

$T(n)=\Theta\left(n^p \left(1+\int_{1}^{n}\frac{f(u)}{u^{\rho+1}}du \right)\right)$

Trong đó $\rho$ thỏa mãn phương trình: $\sum_{i=1}^k \frac{a_i}{b_i^\rho}=1$

Bài viết đã đủ dài mình xin dừng lại ở đây. bài sau mình viết về một số ứng dụng của giải thuật chia để trị cho bài toán sắp xếp.

Hậu viết blog

Bài 3: GIẢI THUẬT CHIA ĐỂ TRỊ

Không có nhận xét nào:

Đăng nhận xét

Bài 6: NGĂN XẾP VÀ HÀNG ĐỢI