โครงสร้างข้อมูล - Greedy Algorithms

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

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

การนับเหรียญ

ปัญหานี้คือการนับเป็นมูลค่าที่ต้องการโดยการเลือกเหรียญที่น้อยที่สุดและวิธีการโลภบังคับให้อัลกอริทึมเลือกเหรียญที่ใหญ่ที่สุด หากเราได้รับเหรียญ₹ 1, 2, 5 และ 10 และเราขอให้นับ₹ 18 ขั้นตอนโลภจะเป็น -

• 1 - เลือกหนึ่ง₹ 10 เหรียญจำนวนที่เหลือคือ 8

• 2 - จากนั้นเลือกหนึ่งเหรียญ₹ 5 จำนวนที่เหลือคือ 3

• 3 - จากนั้นเลือกหนึ่งเหรียญ₹ 2 จำนวนที่เหลือคือ 1

• 4 - และสุดท้ายการเลือกเหรียญ₹ 1 หนึ่งเหรียญจะช่วยแก้ปัญหาได้

แม้ว่าดูเหมือนว่าจะใช้งานได้ดีสำหรับการนับนี้เราต้องเลือกเพียง 4 เหรียญ แต่ถ้าเราเปลี่ยนปัญหาเล็กน้อยวิธีการเดียวกันอาจไม่สามารถให้ผลลัพธ์ที่ดีที่สุดเหมือนกันได้

สำหรับระบบสกุลเงินที่เรามีเหรียญ 1, 7, 10 มูลค่าการนับเหรียญสำหรับมูลค่า 18 จะเหมาะสมที่สุด แต่สำหรับการนับเช่น 15 อาจใช้เหรียญมากกว่าที่จำเป็น ตัวอย่างเช่นวิธีโลภจะใช้ 10 + 1 + 1 + 1 + 1 + 1 รวม 6 เหรียญ ในขณะที่ปัญหาเดียวกันสามารถแก้ไขได้โดยใช้เพียง 3 เหรียญ (7 + 7 + 1)

ดังนั้นเราอาจสรุปได้ว่าแนวทางโลภเลือกโซลูชันที่เหมาะสมทันทีและอาจล้มเหลวในกรณีที่การเพิ่มประสิทธิภาพทั่วโลกเป็นประเด็นสำคัญ

ตัวอย่าง

อัลกอริธึมเครือข่ายส่วนใหญ่ใช้วิธีโลภ นี่คือรายการบางส่วนของพวกเขา -

• ปัญหาพนักงานขายในการเดินทาง
• อัลกอริทึมต้นไม้ที่มีระยะครอบคลุมน้อยที่สุดของ Prim
• อัลกอริทึมต้นไม้ Spanning Tree น้อยที่สุดของ Kruskal
• อัลกอริทึมต้นไม้ Spanning Tree น้อยที่สุดของ Dijkstra
• กราฟ - การระบายสีแผนที่
• กราฟ - ปกเวอร์เท็กซ์
• ปัญหากระเป๋าเป้
• ปัญหาการจัดตารางงาน

มีปัญหาคล้าย ๆ กันมากมายที่ใช้วิธีการโลภเพื่อค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุด