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

ในสาขาวิทยาการคอมพิวเตอร์ เราจะกล่าวว่าปัญหาใด ๆ มี โครงสร้างย่อยที่เหมาะที่สุด () ก็ต่อเมื่อปัญหานั้นสามารถหาคำตอบที่เหมาะสมที่สุดอย่างมีประสิทธิภาพ ได้จากคำตอบที่เหมาะสมที่สุดของปัญหาย่อยของมัน คุณสมบัตินี้มีความจำเป็นอย่างยิ่งในการแก้ปัญหาด้วยกำหนดการพลวัตและขั้นตอนวิธีแบบละโมบอย่างมีประสิทธิภาพIntroduction to Algorithms, 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. ISBN 0-262-03293-7.  

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

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

ปัญหาที่มีโครงสร้างย่อยที่เหมาะที่สุด
 การเรียงแบบผสาน
 การเรียงแบบเร็ว

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

อ้างอิง

หมวดหมู่:การหาค่าเหมาะที่สุดทางคณิตศาสตร์
หมวดหมู่:กำหนดการพลวัต