Greedy Search – Tìm kiếm nhanh nhưng có đáng tin?

Chọn nhanh nhất, nhưng không chắc là tốt nhất

Trong cuộc sống, có những lúc ta chọn “cái lợi trước mắt” với mong muốn sẽ về đích sớm. Trong thuật toán, Greedy Search (tìm kiếm tham lam) cũng làm như vậy: nó luôn chọn đường có vẻ gần đích nhất tại mỗi bước, mà không xét đến những gì đã đi hay còn lại.

Nghe có vẻ hấp dẫn, nhưng liệu chiến lược “tham lam” này có thực sự hiệu quả trong thế giới dữ liệu?

Greedy Search là gì?

Greedy Best-First Search là một thuật toán tìm kiếm chỉ dựa vào hàm heuristic h(n) – tức là chỉ xét khoảng cách ước lượng từ đỉnh hiện tại đến đích, bỏ qua hoàn toàn chi phí đã đi (g(n)).

Công thức đánh giá:

f(n) = h(n)
(chỉ xét ước lượng đến đích, không quan tâm tổng chi phí đã đi)

Nói cách khác, Greedy Search hành xử như người đang lạc đường mà chỉ đi theo bảng chỉ đường “gần nhất tới mục tiêu” – mà không quan tâm đã đi bao xa, đường đó có tắt không, có tốn kém hay vòng vèo không.

 

Ví dụ cụ thể: Tìm đường từ A đến G

 Bản đồ:

Ta dùng lại sơ đồ đồ thị như ví dụ trong phần A*:

• Mỗi cạnh có chi phí cụ thể (1.5, 2, v.v.)

• Mỗi đỉnh có h(n) – khoảng cách ước lượng đến G.

 Heuristic h(n):

Đỉnh	h(n)
A	4.0
B	3.2
C	3.0
D	2.5
E	1.2
F	1.8
G	0

 

Chiến lược Greedy Search thực hiện:

1. Bắt đầu tại A, chọn đỉnh có h(n) thấp nhất trong các lựa chọn kề:

   • B: h = 3.2

   • C: h = 3.0 → chọn C

2. Từ C → D (h = 2.5) → chọn D

3. Từ D → F (h = 1.8), E (h = 1.2) → chọn E

4. E → G → tìm thấy đích

✅ Đường đi: A → C → D → E → G
❌ Tổng chi phí: 2 + 1 + 2 + 1 = 6.0

Tuy nhiên, cũng có thể tồn tại đường A → B → D → E → G có chi phí ít hơn, nhưng Greedy không xét vì nó chỉ quan tâm đến h(n), không quan tâm tổng chi phí thực.

 

So sánh nhanh với A*, UCS

Thuật toán	Xét chi phí thực (g)	Sử dụng heuristic (h )	Tổng f(n)
BFS	❌	❌	f(n) = depth
UCS	✅	❌	f(n) = g(n)
A*	✅	✅	f(n) = g(n)+h(n)
Greedy	❌	✅	f(n) = h(n)

 

 

Greedy Search dễ gây hiểu lầm – vì sao sinh viên dễ “vấp”?

1. Thấy nhanh nên tưởng tối ưu:
   Greedy thường tới đích nhanh hơn A*, nhưng không đảm bảo tìm được đường đi ngắn nhất. Nhiều sinh viên nhầm đây là giải pháp “tối ưu”.

2. Chọn heuristic sai → Greedy thành “mù đường”:
   Nếu h(n) không phản ánh đúng thực tế, Greedy sẽ rẽ vào ngõ cụt.

3. Không so sánh kết quả với A hoặc UCS:*
   → Dễ bị đánh giá sai hiệu quả, dẫn đến áp dụng sai trong bài toán thực tế.

4. Không quản lý hàng đợi ưu tiên chuẩn:
   Greedy vẫn cần priority queue – nhưng dùng sai logic sắp xếp sẽ dẫn đến thứ tự duyệt sai.

 

Khi nào nên dùng Greedy Search?

✅ Khi tốc độ quan trọng hơn độ chính xác (ví dụ: game AI, robot cần phản ứng nhanh).

✅ Khi bài toán có heuristic rất tốt, ước lượng gần sát thực tế.

✅ Khi không cần thiết phải tìm đường đi tối ưu, chỉ cần “đủ tốt và đủ nhanh”.

 

Cách học Greedy Search hiệu quả

✅ Thực hành nhiều bài toán khác nhau – đặc biệt là so sánh Greedy với A* để cảm nhận sự khác biệt giữa “tham lam” và “chiến lược”.

✅ Tự thiết kế heuristic – tập ước lượng khoảng cách từ một điểm đến đích trong các dạng đồ thị khác nhau.

✅ Mô phỏng từng bước trên giấy – ghi lại đường duyệt theo thứ tự, so sánh với kết quả cuối cùng.

✅ Dùng bảng tổng hợp để thấy rõ ưu – nhược điểm:
→ Học từ việc Greedy thất bại để hiểu sâu bản chất của tìm kiếm tối ưu.

 

Code mẫu: Greedy Best-First Search (Python)

 

Lời kết: Đừng để “tham lam” khiến bạn đi lạc đường

Greedy Search có thể là một giải pháp tuyệt vời khi thời gian là ưu tiên hàng đầu. Nhưng cũng giống như trong cuộc sống – nếu bạn chỉ nhìn cái lợi trước mắt, bạn có thể bỏ lỡ con đường tốt hơn mà chỉ cần một chút kiên nhẫn và tính toán.

Biết khi nào nên “tham lam” và khi nào nên “chiến lược” – đó là kỹ năng bạn không chỉ cần trong giải thuật, mà còn trong cả hành trình học tập và phát triển cá nhân.

 

FacingX.com – Đồng hành cùng bạn để hành trình học tập của bạn không bị lạc hướng bởi những lựa chọn hấp tấp như Greedy Search!

Tại FacingX, chúng tôi giúp bạn:

•  Chọn ngành, chọn nước du học phù hợp nhất – không vội vàng, không “tham lam”

•  Trang bị nền tảng tư duy giải thuật, logic, toán học từ năm nhất

•  Kết nối học tập 1:1 với giáo viên quốc tế – để mỗi bước đi đều có hướng dẫn đúng đắn

---