ในโพสต์นี้ เราจะเข้าใจความแตกต่างระหว่างอัลกอริธึมโลภและวิธีการเขียนโปรแกรมแบบไดนามิก
อัลกอริทึมที่โลภ
เป็นกระบวนทัศน์ของอัลกอริทึมที่สร้างขึ้นจากโซลูชันในส่วนต่างๆ ทีละขั้นตอน ขั้นตอนต่อไปจะถูกเลือกเพื่อให้เกิดประโยชน์ที่ชัดเจนและทันที
- ปัญหาที่เกี่ยวข้องกับการเลือกค่าที่เหมาะสมในท้องถิ่นจะช่วยในการเลือกค่า/วิธีแก้ไขปัญหาที่เหมาะสมที่สุดทั่วโลก ดังกล่าวกินปัญหาที่เกี่ยวข้องกับอัลกอริทึมที่โลภ
- ไม่มีหลักประกันว่าอัลกอริธึมที่โลภจะนำไปสู่ทางออกที่ดีที่สุด
- มีตัวเลือกที่เหมาะสมในทุกขั้นตอนของปัญหา นั่นคือวิธีแก้ปัญหาที่เหมาะสมที่สุดในพื้นที่
- มีประสิทธิภาพในแง่ของการใช้หน่วยความจำ เนื่องจากไม่จำเป็นต้องย้อนกลับหรือเปลี่ยนโซลูชัน/ค่าก่อนหน้า
- โดยทั่วไป จะรวดเร็วเมื่อเปรียบเทียบกับเทคนิคการเขียนโปรแกรมแบบไดนามิก
- ตัวอย่าง:อัลกอริธึมพาธที่สั้นที่สุดของ Dijkstra ที่ใช้เวลา O(ELogV + VLogV)
- โซลูชันในอัลกอริธึมที่โลภได้รับการคำนวณในวิธีการส่งต่อ จะไม่ไปที่ค่า/โซลูชันก่อนหน้าหรือเปลี่ยนแปลงค่าเหล่านี้
การเขียนโปรแกรมแบบไดนามิก
เป็นเทคนิคการเพิ่มประสิทธิภาพที่ช่วยจัดเก็บผลลัพธ์ของปัญหาย่อยเพื่อไม่ให้ต้องคำนวณใหม่เมื่อจำเป็นในอนาคต พวกเขาสามารถแยกได้จากชุดที่คำนวณล่วงหน้า ช่วยลดความซับซ้อนของเวลาจากความซับซ้อนแบบเอ็กซ์โปเนนเชียลไปจนถึงพหุนามที่ซับซ้อน
- ตัวอย่าง:โซลูชันแบบเรียกซ้ำสามารถเปลี่ยนเป็นปัญหาการเขียนโปรแกรมแบบไดนามิกได้ด้วยการคำนวณ
- ในเรื่องนี้ การตัดสินใจในทุกขั้นตอนจะกระทำโดยพิจารณาปัญหาปัจจุบันในมือ และการแก้ปัญหารวมที่แก้ไขก่อนหน้านี้ ซึ่งจะใช้ในการคำนวณค่า/โซลูชันที่เหมาะสมที่สุด
- รับประกันได้ว่าโซลูชันของปัญหาการเขียนโปรแกรมแบบไดนามิกจะเป็นวิธีที่เหมาะสมที่สุด
- ที่นี่ โซลูชันที่เหมาะสมที่สุดที่เลือกคือโซลูชันที่เหมาะสมที่สุดทั่วโลก ใช้สูตรบางอย่างที่จะใช้ในการจัดเก็บค่าสถานะที่คำนวณไว้ก่อนหน้านี้
- ตารางโปรแกรมแบบไดนามิกจำเป็นสำหรับการท่องจำ สิ่งนี้จะเพิ่มความซับซ้อนของหน่วยความจำ
- ค่อนข้างช้ากว่า
- ตัวอย่าง:อัลกอริทึมของ Bellman Ford ที่ใช้เวลา O(VE)
- การเขียนโปรแกรมแบบไดนามิกกำหนดวิธีแก้ปัญหาโดยใช้แนวทางจากล่างขึ้นบนหรือจากบนลงล่าง โดยพัฒนาจากปัญหาเล็กๆ ที่มีวิธีแก้ปัญหาที่เหมาะสมที่สุด
