ในสาขาว ทยาการคอมพ วเตอร เราจะกล าวว าป ญหาใด ๆ ม โครงสร างย อยท เหมาะท ส ด อ งกฤษ optimal substructure ก ต อเม อป ญหาน

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

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

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

ตัวอย่าง

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

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

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

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

อ้างอิง

Introduction to Algorithms, 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. .

[1] Introduction to Algorithms, 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. .