Tag Archives: thuattoan

Thuật toán tham lam (Greedy Algorithms)

Thuật toán tham lam là thuật toán để giải quyết một bài toán trong đó ta chọn phương án tối ưu cho các bước địa phương, từ đó đạt được tối ưu toàn cục. Đó chưa hẳn luôn là phương án tối ưu cho bài toán nhưng thường sẽ được đạt được cực trị.

Ý tượng là trong mỗi bước, ta xét các phần tử (thuộc dạng tốt nhất, xấu nhất, lớn nhất hay nhỏ nhất) để đạt được các mục tiêu cần giải quyết.

Ví dụ ta có một xấp tiền gồm các tờ 1k, 2k, 5k, 10k, làm sao ta có thể đổi một số tiền 57k thành các tờ tiền này sao cho số tờ tiền là ít nhất.

Rõ ràng ta cứ chọn các tiền lớn nhất có thể, thuật toán là

  • Chọn lớn nhất $x \in {1, 2, 5, 10}$ thỏa $x \leq M$.
  • Tiếp tục thuật toán cho $M-x$.

Khi đó ta có

  • $x_1 = 10$, $M_1 = 47$, sau lần 1.
  • $x_2 = 10, M_2 = 37$
  • $x_3 = 10, M_3 = 27$
  • $x_4 = 10, M_4 = 17$
  • $x_5 = 10, M_5 = 7$
  • $x_6 = 5, M_6 = 2$
  • $x_7 = 2, M_7 = 0$

Vậy tập cần tìm là $\{10, 10, 10, 10, 10, 5, 2 \}$

Trên đây là một ví dụ đơn giản về thuật toán tham lam, tiếp theo ta xét một số ví dụ khác để các bạn có thể hiểu rõ hơn về thuật toán này.

Ví dụ 1. Chứng minh rằng mọi số nguyên dương $n$ thì đều có thể biểu dưới dạng một lũy thừa của 2 hoặc một tổng các lũy thừa của 2, và sự biểu diễn là duy nhất.

Lời giải
  • Nếu $n$ là lũy thừa của 2 thì coi như xong. Nếu $n$ không là lũy thừa của $2$ ta chọn một lũy thừa của 2 nhỏ hơn $n$ và gần $n$ nhất, giả sử là $2^{a_k}$. Ta có $2^{a_k} < n < 2^{a_k+1}$.
  • Tiếp theo áp dụng thuật toán cho số $n-2^k$, rõ ràng thuật toán dừng vì ta có dãy giảm và bị chặn bởi 0.
  • Khi đó ta có $n = 2^{a_1} + \cdots +2^{a_k}$.
  • Ta chứng minh sự biểu diễn này là duy nhất. Giả sử tồn tại hai cách biểu diễn $2^{a_k} + \cdots + 2^{a_1} = 2^{b_m} + \cdots 2^{b_1}$. Nếu $a_k >b_m \Rightarrow a_k \geq b_m+1$. Khi đó $a^k >a^{b_m+1}-1=\geq 2^{b_m}+2^{b_m-1} + \cdots 2^{1} + 1$
  • Do đó $VT > VP$ (vô lí)
  • Nếu $a_k = b_m$, chứng minh tương tự cũng có 2 dãy $a_1,\cdot a_k$ và $b_1,\cdots b_m$ là trùng nhau. Nên sự biểu diễn là duy nhất.

Ví dụ 2. Cho một đồ thị đơn, trong đó $d$ là bậc cao nhất. Chứng minh rằng có thể tô màu các đỉnh của đồ thị bằng $d+1$ màu sao cho hai đỉnh kề thì khác màu.

Lời giải
  • Giả sử các màu được đánh số từ 1 đến $d+1$. Ta thực hiện cách tô màu như sau
  • Chọn 1 đỉnh ta tô màu nhỏ nhất mà không xuất hiện trong các đỉnh lân cận với đỉnh đó. Việc tô màu này luôn thực hiện được vì bậc của mỗi đỉnh không hơn hơn $d$.

Ví dụ 3. Cho các tập $A_1, A_2 , \cdots, A_{2022}$ là các tập con có 3 phần tử của $X = \{1, 2, \cdots 2022 \}$. Chứng minh rằng ta có thể tô màu $674$ phần tử của $X$ sao cho với mọi tập $A_i$ có một phần tử không được tô màu.

Lời giải
  • Ta có thể làm ngược lại, tô màu các số sao cho với mỗi tập $A_i$ có ít nhất một số được tô màu, ta chứng minh là số phần tử cần tô không vượt quá $1348$ số.
  • Ta thực hiện cách tô sau: Chọn phần tử xuất hiện nhiều nhất trong các tập, tô màu phần tử đó. Lặp lại thuật toán đến khi không có tập hợp nào không có phần tử được tô màu
  • Ta chứng minh số phần tử được tô màu không vượt quá 1348 phần tử
  • Giả sử ta tô được $k$ phần tử, và các tập còn lại đều phân biệt rời nhau, có $m$ tập hợp. Rõ ràng vì mỗi bước thực hiện đều giảm được ít nhất 2 tập nên $k \leq \dfrac{2022}{2} = 1011$. (Vì cách chọn số phần từ xuất hiện trong nhiều tập nhất nên ít nhất là 2). Và các tập còn lại phân biệt rời nhau, mỗi tập có 3 phần tử nên $m \leq 1011/3 = 337$.\\
  • Khi đó ta tô màu mỗi phần tử trong $m$ tập còn lại thì sẽ thỏa đề bài, do đó số phần tử cần tô màu là $k+m \leq 1011+ 337 = 1348$.
  • Do đó ta có cách tô màu thỏa đề bài.

Ví dụ 4. Cho một bảng $2 \times n$, người ta điền vào bảng các số dương sao cho tổng hai số trong cùng một cột bằng 1. Chứng minh rằng ta có thể chọn mỗi cột một số sao cho các số trên mỗi dòng không lớn hơn $\dfrac{n+1}{4}$.

Lời giải

Ta sắp xếp từ trái sang phải theo thứ tự tăng dần các số ở hàng thứ nhất $a_1 \leq a_2 \leq \cdot \leq a_n$, hàng dưới tương ứng là $1-a_1, 1-a_2, \cdots, 1-a_n$.

Ta chọn các số ở hàng trên từ trái qua, nhiều nhất sao cho tổng $S$ không lớn hơn $\dfrac{n+1}{4}$. Ta chứng minh tổng các số ở hàng dưới trong các cột còn lại không lớn hơn $\dfrac{n+1}{4} – S$.

Giả sử chỉ số $i$ lớn nhất thỏa $a_{1}+a_{2}+\cdots+a_{i} \leq \frac{n+1}{4} .$ Ta cần chứng minh
$$
\dfrac{n+1}{4} \geq\left(1-a_{i+1}\right)+\left(1-a_{i+2}\right)+\cdots+\left(1-a_{n}\right)=(n-i)-\left(a_{i+1}+a_{i+2}+\cdots+a_{n}\right)
$$

$$
a_{i+1}+a_{i+2}+\cdots+a_{n} \geq \frac{3 n-1}{4}-i
$$
Từ $a_{1} \leq a_{2} \leq \cdots \leq a_{i+1}$, ta có
$$
\dfrac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1} \leq a_{i+1}
$$

và từ $a_{i+1} \leq a_{i+2} \leq \cdots \leq a_{n}$, ta có
$$
\dfrac{a_{i+1}+a_{i+2}+\cdots+a_{n}}{n-i} \geq a_{i+1}
$$
Từ đó ta có
$$
\dfrac{a_{i+1}+a_{i+2}+\cdots+a_{n}}{n-i} \geq \frac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1}
$$

$$
a_{i+1}+a_{i+2}+\cdots+a_{n} \geq(n-i) \cdot \frac{a_{1}+a_{2}+\cdots+a_{i+1}}{i+1}>(n-i) \cdot \frac{\frac{n+1}{4}}{i+1}
$$
do cách chọn $i$ lớn nhất.

Ta cần chứng minh $\dfrac{n-i}{i+1} \dfrac{n+1}{4} \geq \dfrac{3 n-1}{4}-i .$

hay $(n-1)^{2} \geq 4 i(n-i-1)$, áp dụng AM-GM $2 \sqrt{i(n-i-1)} \leq i+(n-i-1)=n-1$, ta có điều cần chứng minh.

Ví dụ 5. (IMOSL 2001) Một tập có 3 số nguyên phân biệt không âm $\{x, y, z\}$ thỏa $x < y< z$ được gọi là tập có tính chất P nên $\{z-y, y-z\} = \{a,b\}$ với $0 < a< b$ nguyên dương cho trước. Chứng minh rằng tập các số nguyên không âm được viết thành hợp các có tính chất P đôi một phân biệt.

Lời giải

Ta thấy có 2 trường hợp là $z=y=b, y-x=a$ hoặc $z-y=a, y-x=b$ hay tập có tính chất $P$ sẽ có một trong hai dạng {x, x+a, x+a+b} hoặc {x, x+b, x+a+b} với $x$ nguyên dương.

Với mỗi tập có tính chất $P$ là {x, y, z} ta tô màu $x$ đỏ, $y$ xanh $z$ vàng.

Ta tô màu các số nguyên dương như sau:

  • Xét số dương $k$ nhỏ nhất chưa được tô màu.
  • Nếu $k+a$ chưa được tô màu thì ta tô màu cho tập {k, k+a, k+a+b}.
  • Nếu $k+b$ chưa được tô màu thì ta tô màu cho tập {k, k+b,k+a+b}.

Ta chứng minh với cách tô màu như trên thì các tập đều phân biệt và số nào cũng được tô màu. Giả sử ta đã thực hiện tới bước thứ $n$ với phần tử $x_n$ là nhỏ nhất được tô màu. Ta tiếp tục thực hiện với kế tiếp với phần tử $x_{n+1}$ chưa được tô màu. Ta cần chứng minh các phần tử $x_{n+1}+a$ hoặc $x_{n+1}+b$ chưa được tô màu và $x_{n+1}+a+b$ chưa được tô màu trước đó.

  • Thật vậy rõ ràng là $x_{n+1}+a+b$ chưa được tô màu vì nó lớn hơn tất cả các số được tô màu. (Ở bước thứ $n$ thì $x_n$ được tô màu, nên $x_n+a+b $ là số lớn nhất được tô màu.
  • Nếu $x_{n+1} +b$ được tô màu thì không thể là màu đỏ, nếu xanh thì $x_{n+1}+b-a$ được tô màu đỏ, vô lí. Nếu màu vàng thì $x_{n+1}+b-a-b = x_{n+1}-a$ được tô màu đỏ, khi đó $x_{n+1}$ được tô màu, vô lí.

Một số bài tập rèn luyện

Bài 1. (Đức 2000) Có một số đá tổng cộng là 9 tấn cần được vận chuyển bằng xe tải. Mỗi tảng đá không nặng quá  1 tấn, mỗi xe tải chở không quá 3 tấn. Hỏi còn ít nhất bao nhiêu xe tải để chở hết số đá này cùng lúc.

Bài 2. Chứng minh rằng với mọi số nguyên dương $n$ tồn tại các số nguyên dương $a_1, a_2, \cdots, $ sao cho $a_i \leq i$ thỏa

$$n = a_1 \cdot 1! + a_2 \cdot 2! + \cdots + a_k \cdot k! $$

và sự biểu diễn này là duy nhất.

Bài 3. Gọi S là tập hợp n điểm trong mặt phẳng tọa độ. Nói rằng một cặp điểm thẳng hàng nếu hai điểm đó có cùng tọa độ x hoặc y. Chứng minh rằng S có thể được phân chia thành các tập con rời rạc sao cho

(a) mỗi tập con này là một tập hợp các điểm thẳng hàng,
và (b) tối đa $n^{3/2}$ cặp điểm phân biệt không có thứ tự trong S thẳng hàng nhưng không nằm trong cùng một tập con.

Bài 4. (IMOSL 2013). Cho $n$ là một số nguyên dương. Tìm số nguyên $k$ nhỏ nhất thỏa mãn tính chất: Cho bất kỳ số thực $a_1, · · ·, a_d$ sao cho $a_1 + a_2 + · · · + a_d = n$ và $0 \leq  a_i \leq 1$
với $i = 1, 2, · · ·, d$, có thể phân chia các số này thành $k$ nhóm (một số có thể trống)
sao cho tổng các số trong mỗi nhóm nhiều nhất là $1$.

Bài 5.  (IMO 2014). Với mỗi số nguyên dương n, Ngân hàng Cape Town phát hành tiền xu có mệnh giá $\dfrac{1}{n}$. Đưa ra một bộ sưu tập hữu hạn các đồng tiền như vậy (không nhất thiết phải có mệnh giá khác nhau) với tổng số giá trị nhiều nhất là $99+ \dfrac{1}{2}$. Chứng minh rằng có thể chia bộ sưu tập này thành 100 nhóm hoặc ít hơn, chẳng hạn như mà mỗi nhóm có tổng giá trị nhiều nhất là 1.