อัลกอริทึมที่โลภ (Greedy algorithms) คืออะไร และมันจะทำงานเมื่อใด

Question

Accepted Answer

**อัลกอริทึมที่โลภ** ทำให้ **ตัวเลือกที่ดีที่สุดในท้องถิ่น** ที่แต่ละขั้นตอน โดยหวังว่ามันจะนำไปสู่ค่าเหมาะที่สุดทั่วโลก มันเรียบง่ายและรวดเร็ว แต่ถูกต้องเฉพาะเมื่อปัญหามี **คุณสมบัติการเลือกที่โลภ** และ **โครงสร้างย่อยที่เหมาะสม**

## แนวคิด

ห้ามพิจารณาตัวเลือกที่ผ่านมาอีก — ยึดมั่นกับตัวเลือกที่ดีที่สุดในทันทีและไปต่อ

## ตัวอย่าง: การแลกเปลี่ยนเหรียญด้วยเหรียญตามบัญญัติ

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

สิ่งนี้เหมาะสำหรับเหรียญสหรัฐฯ แต่ **ล้มเหลว** สำหรับชุดเช่น {1, 3, 4} โดยที่กำไรให้ 4+1+1 สำหรับ 6 แทน 3+3

## เมื่อใดที่อัลกอริทึมที่โลภจะทำงาน

- **โครงสร้างย่อยที่เหมาะสม:** วิธีแก้ปัญหาที่เหมาะสมมีวิธีแก้ปัญหาย่อยที่เหมาะสม
- **คุณสมบัติการเลือกที่โลภ:** ค่าเหมาะที่สุดในท้องถิ่นเป็นส่วนหนึ่งของค่าเหมาะที่สุดทั่วโลก

ตัวอย่างที่ใช้ได้: Dijkstra, Kruskal/Prim (MST), Huffman coding, การจัดตารางช่วงเวลา

## ความซับซ้อน

มักจะเร็ว — มักจะ O(n log n) หลังจากการเรียงลำดับ

## ข้อเสีย

อัลกอริทึมที่โลภ **ไม่ได้ถูกต้องเสมอไป** พิสูจน์คุณสมบัติการเลือกที่โลภหรือทดสอบกับ brute-force/DP baseline ก่อนที่จะเชื่อถือ

## ทำไมจึงสำคัญ

เมื่ออัลกอริทึมที่โลภใช้ได้ มันจะง่ายและเร็วกว่า DP หรือ brute force มาก

การรู้ว่า *เมื่อใด* มันถูกต้อง — และเมื่อใดที่มันเงียบ ๆ ให้คำตอบที่ผิด — เป็นเครื่องหมายของความเป็นผู้ใหญ่ด้านอัลกอริทึม

อัลกอริทึมกราฟหลักมากมายมีอัลกอริทึมที่โลภในแก่น