ในวิธีโลภเราได้?

2024 ผู้เขียน: Elizabeth Oswald | [email protected]. แก้ไขล่าสุด: 2024-01-13 00:13

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

วิธีโลภมีวิธีแก้ที่เป็นไปได้กี่วิธี

อัลกอริธึม Greedy ทำให้ตัวเลือกที่โลภในแต่ละขั้นตอนเพื่อให้แน่ใจว่าฟังก์ชันวัตถุประสงค์ได้รับการปรับให้เหมาะสม อัลกอริทึม Greedy มีเพียง one shot ในการคำนวณหาทางออกที่ดีที่สุด เพื่อไม่ให้ย้อนกลับมาตัดสินใจ

แนวคิดของวิธีการโลภคืออะไร

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

ความโลภมีประโยชน์อย่างไร

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

เมื่อไหร่ควรใช้ความโลภ

ที่กล่าวถึงด้านล่างนี้คือปัญหาบางอย่างที่ใช้วิธีแก้ปัญหาที่เหมาะสมที่สุดโดยใช้แนวทาง Greedy

• ปัญหาพนักงานขายการเดินทาง
• อัลกอริธึม Spanning Tree ขั้นต่ำของ Kruskal
• อัลกอริธึม Spanning Tree ขั้นต่ำของ Dijkstra
• ปัญหาเป้.
• ปัญหาการจัดตารางงาน