1. Định nghĩa (vietjack.com)
Bài toán con là một bài toán tương tự và có kích thước nhỏ hơn bài toán ban đầu.
Các thành phần chính của giải thuật tham lam.
+ Rút gọn thành các bài toán con
- Thực hiện một số bước ban đầu
- Rút gọn thành bài toán tương tự nhưng ở dạng nhỏ hơn
- Ta gọi là bài toán con
- Một nước đi gọi là an toàn nếu nó phù hợp với một số giải pháp tối ưu
- Không phải tất cả các bước đi đầu tiên đều là an toàn
- Thường thì lựa chọn tham lam không an toàn
Một lựa chọn tham lam được gọi là nước đi an toàn nếu có một giải pháp tối ưu phù hợp với lựa chọn này.
- Ban đầu lựa chọn một tham lam
- Chứng minh nó là một nước đi an toàn
- Rút gọn thành một bài toán con
- Giải bài toán con
- Lặp lại cho đến khi giải được bài toán
- Dễ triển khai giải thuật tham lam cho một bài toán nào đó
- Dễ phân tích Big-O hơn các giải thuật khác
- Khó chọn nước đi tham lam
- Khó chứng minh nước đi tham lam là đúng
- Hầu như giải thuật tham lam đều không chính xác
2. Ví dụ
Một chiếc ôtô khi đổ đầy bình xăng có thể đi được xa nhất là $L(km).$ Hãy tìm số lần đổ xăng ít nhất để đi từ điểm $A$ đến điểm $B$ biết rằng có $n$ trạm xăng $x_1\leq x_2\leq ...\leq x_n$ dọc theo đường đi từ $A$ đến $B$. Lưu ý không tính số lần đổ xăng ở điểm xuất phát.
Phân tích một số lựa chọn tham lam như sau:
- Đổ xăng tại trạm xăng gần nhất
- Đổ xăng tại trạm xăng xa nhất có thể đến được
- Đi cho tới khi hết xăng và hy vọng có cây xăng để đổ
Theo đề bài yêu cầu tìm số lần đổ xăng ít nhất nên lựa chọn tham lam đổ xăng tại trạm xăng xa nhất có thể đến được là tối ưu.
- Bắt đầu tại A
- Đổ xăng tại trạm xăng xa nhất có thể đến được G
- Biến G thành A mới
- Đi từ A mới tới B với số lần đổ xăng ít nhất
$\text{numReffil } \leftarrow 0, \text{ currentReffil } \leftarrow 0$
$\text{while currentReffil } \leq n:$
$\text{lastReffil } \leftarrow \text{ currenReffil }$
$\text{while currenReffil } \leq n \text{ and } x[currenReffil+1]-x[lastReffil] \leq L:$
$\text{currenReffil } \leftarrow \text{ currenReffil }+1$
$\text{if currentReffil }== \text{ lastReffil}:$
$\text{return IMPOSSIBLE}$
$\text{if currentReffil } \leq n:$
$\text{numReffil } \leftarrow \text{ numReffil }+1$
$\text{return numReffil}$
def MinRefills(x,n,L):
numRefills,currentRefill=0,0
while currentRefill<=n:
lastRefill=currentRefill
while currentRefill<=n and x[currentRefill+1]-x[lastRefill]<=L:
currentRefill+=1
if lastRefill==currentRefill:
return IMPOSSIBLE
if currentRefill<=n:
numRefills+=1
return numRefills
x,L=[0,200,375,550,750,950],400
n=len(x)-2
print(MinRefills(x,n,L))Thời gian chạy của thuật toán trên là O(n). Vì biến currentRefill chạy từ 0 đến n, biến này luôn tăng từ một đơn vị và biến numRefills thay đổi từ 0 đến lớn nhất là n.
Cho một tập hợp $n$ điểm đã xắp thứ tự $x_1,x_2,...,x_n \in \mathbb{R}$. Hãy tìm cách phân nhóm ít nhất cho $n$ điểm trên với điều kiện bất kỳ 2 điểm nào trong cùng một nhóm có khoảng cách nhỏ hơn hoặc bằng 1.
Giải thuật tham lam cho bài toán phân nhóm
- Bắt đầu tại điểm ở ngoài cùng bên trái
- Loại bỏ tất cả các điểm nằm trên đường thẳng đơn vị khỏi tập hợp $n$ điểm
- Lặp lại quá trình trên điến khi không còn điểm nào trong tập hợp.
$R \leftarrow \left\{ \right\}, i \leftarrow 1$
$\text{while }i \leq n:$
$[l,r] \leftarrow [x_i,x_i+1]$
$R \leftarrow R \cup {[l,r]}$
$i \leftarrow i+1$
$\text{while } i \leq n \text{ and } x_i \leq r:$
$i \leftarrow i+1$
$\text{return } R$
Code python
def PointsCoverSorted(x):
R,i=[],0
n=len(x)-1
while i<=n:
[l,r]=[x[i],x[i]+1]
R.append([l,r])
i+=1
while i<=n and x[i]<=r:
i+=1
return len(R)Thời gian chạy của thuật toán là O(n).
Bạn có một chuyến đi bộ đường dài và bạn không biết bao lâu thì tới đích. Vì vậy, để an toàn, bạn cần mang theo đủ thức ăn. Giả sử bạn có một chiếc ba lô có thể đựng được $W(kg)$ thực phẩm 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 thực phẩm bỏ vào ba lô để mang đi sao cho giá trị là cao nhất.
Giải thuật tham lam cho bài toán xếp ba lô
- Chọn i sao cho $\frac{v_i}{w_i}$ lớn nhất
- Nếu ba lô đựng được hết vật phẩm này thì lấy hết vật phẩm và quay lại bước 1
- Ngược lại thì lấy đủ số kg mà ba lô còn thiếu.
$A \leftarrow [0,0,...,0], V \leftarrow 0$
$\text{Lặp lại n lần:}$
$\text{Nếu } W=0:$
$\text{return } (V,A)$
$\text{Chọn i sao cho } w_i>0 \text{ và } \frac{v_i}{w_i} \text{ lớn nhất}$
$a \leftarrow min(w_i,W)$
$V \leftarrow V+a.\frac{v_i}{w_i}$
$W_i \leftarrow W_i-a,A[i] \leftarrow A[i]+a,W \leftarrow W-a$
$\text{return } (V,A)$
Code python
def knapsack(W,w,v):
V,n=0,len(w)
A=[0]*n
i=1
while i<=n:
if W==0:
return (V,A)
i_max=0
for j in range(1,n):
if v[i_max]*w[j]<=v[j]*w[i_max] and w[j]>0:
i_max=j
a=min(w[i_max],W)
V=V+a*(v[i_max]/w[i_max])
w[i_max],A[i_max],W=w[i_max]-a,A[i_max]+a,W-a
i+=1
return (V,A)Thời gian chạy của thuật toán là $O(n^2)$
Không có nhận xét nào:
Đăng nhận xét