ว่าด้วยเรื่องของ Greedy Algorithm

Greedy Algorithm คืออะไร ? .. มันคือขั้นตอนวิธีการแก้ปัญหาที่สุดแสนจะ simple อย่างหนึ่ง แก้ปัญหาโดยมีแนวคิดว่า คำตอบที่ดีที่สุดในปัจจุบันจะสามารถนำมาซึ่งผลลัพธ์ที่ดีที่สุดในตอนท้ายได้

ยกตัวอย่างเช่น เรามีเหรียญบาทอยู่จำนวนหนึ่ง ได้แก่ 5,5,5,10,10,1,2,2,1 ถ้าเราต้องการหยิบเหรียญเพียงแค่ 3 เหรียญและต้องการมูลค่าค่าเงินรวมมากที่สุด เราจะมีวิธีการหยิบเหรียญยังไง ?

ถ้าคิดแบบตรงไปตรงมา (และละโมบ) เราก็แค่หยิบเหรียญที่มีมูลค่ามากที่สุดเพียง 3 เหรียญ ก็จะได้มูลค่าเงินรวมมากที่สุดแล้ว ตามตัวอย่างข้างต้นเราก็ทำการหยิบเหรียญ 10,10,5 รวมเป็น 25 บาท นี้ไง! มากที่สุดที่สามารถทำได้แล้ว

แล้วถ้าเป็นปัญหาแบบนี้บ้างหล่ะ ?

สมมติว่ามีสวนผลไม้อยู่ขนาด n*m ในแต่ละช่องของสวนผลไม้จะมีมูลค่าของผลไม้อยู่ ถ้าเราอยากจะเดินเก็บค่าเหล่านั้นเริ่มจาก มุมซ้ายบน ไปสิ้นสุด ณ มุมขวาล่าง โดยวิธีการเดินสามารถเดินได้เพียง เดินลง และ เดินไปขวาเท่านั้น ถามว่ามูลค่าของผลไม้ที่เก็บได้ที่มากที่สุด คือเท่าไหร่ ? ( คงจะมีหลายคนคุ้นเคยกับโจทย์แบบนี้ เครคิตโจทย์ : Fruit Fruit Fruit ของ otog ไง )

สมมติหน้าตาสวนผลไม้ของเราเป็นแบบนี้ละกันเนอะ .. เราจะมาลองใช้ Greedy Algorithm ในการแก้ปัญหานี้ดู โดยเริ่มจากมุมซ้ายบน แล้วเลือกเดินไปในเส้นทางที่มีมูลค่าผลไม้มากที่สุด (เปรียบเทียบระหว่างค่าผลไม้ข้างล่าง กับ ค่าผลไม้ด้านขวา)

ก็จะได้เส้นทางในการเดินเก็บผลไม้ประมาณนี้ โดยมีมูลค่ารวมที่เก็บได้คือ 1+4+5+6+3+6+3 = 28

แต่!!! นี่ไม่ใช่คำตอบที่ให้มูลค่าผลไม้รวมที่มากที่สุด แต่เป็นเส้นทางการเดินแบบนี้ต่างหาก

อันนี้เดินแบบมั่วๆ และไม่ได้ใช้ Greedy Algorithm เลย

มูลค่ารวมที่เก็บได้

1+4+4+20+10+6+3 = 48

ซึ่งเป็นมูลค่ารวมที่มากที่สุดแล้ว

อ้าววว แบบนี้ Greedy Algorithm อันสุดแสนจะ simple ของเราก็ไม่สามารถ solve ปัญหานี้ได้หน่ะสิ … ใช่ครับ Greedy Algorithm สามารถใช้ solve ได้ใน ‘บาง’ ปัญหาเท่านั้น

In Real life

ในบางครั้ง เวลาเจอปัญหา หลายๆคนมักเลือกใช้ Greedy Algorithm ในการตัดสินใจ (เลือกแบบที่ดีที่สุดในตอนนั้น) โดยคาดหวังว่ามันจะให้ Best result กับเรา แต่ความจริงแล้ว เราไม่สามารถรู้ได้เลยว่า Best decision ในขณะนั้นจะนำมาซึ่ง Best result กับเรา ในบางครั้งมันอาจนำมาซึ่งผลลัพธ์ที่แย่บ้าง ไม่ดีไม่แย่บ้าง หรือเป็น best result ไปเลยบ้าง เพราะฉะนั้น คิดให้ดีก่อนตัดสินใจ เพราะการลงมือทำอะไรของคุณ อาจจะนำมาซึ่งผลลัพธ์ประหลาดๆมากมาย ;

แล้วคุณล่ะ กำลังใช้ชีวิตแบบ Greedy Algorithm อยู่หรือเปล่า ?

ปล. สำหรับวิธีการแก้ปัญหาของข้อ Fruit Fruit Fruit นั้นนนน …………… ลองเก็บไปคิดกันดูนะ