โครงสร้างย่อยที่เหมาะสมที่สุด

ภาพที่ 1. การหาเส้นทางสั้นที่สุดโดยอาศัยการแก้ โครงสร้างย่อยที่เหมาะสมที่สุด ตัวเลขหมายถึงความยาวของเส้นเชื่อม เส้นตรงหมายถึงเส้นเชื่อมเส้นเดียว เส้นคลื่นหมายถึงระยะทางสั้นที่สุด

ในสาขาวิทยาการคอมพิวเตอร์ เราจะกล่าวว่าปัญหาใด ๆ มี โครงสร้างย่อยที่เหมาะสมที่สุด (อังกฤษ: optimal substructure) ก็ต่อเมื่อปัญหานั้นสามารถหาคำตอบที่เหมาะสมที่สุดอย่างมีประสิทธิภาพ ได้จากคำตอบที่เหมาะสมที่สุดของปัญหาย่อยของมัน คุณสมบัตินี้มีความจำเป็นอย่างยิ่งในการแก้ปัญหาด้วยกำหนดการพลวัตและขั้นตอนวิธีแบบละโมบอย่างมีประสิทธิภาพ

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

ตัวอย่าง

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

ปัญหาที่มีโครงสร้างย่อยที่เหมาะสมที่สุด

• การเรียงแบบผสาน
• การเรียงแบบเร็ว

ปัญหาที่ไม่มีโครงสร้างย่อยที่เหมาะสมที่สุด

• ปัญหาวิถียาวสุด