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

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

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

ใกล้เคียง

โครงสร้างพื้นฐาน โครงสร้างของโลก โครงสร้างเปลือกหอย โครงสร้างผลึก โครงสร้างข้อมูลเซตไม่มีส่วนร่วม โครงสร้างกั้นระหว่างเลือดกับอัณฑะ โครงสร้างนิยม โครงสร้างทรงโค้ง โครงสร้างโมเลกุลของกรดนิวคลีอิก: โครงสร้างสำหรับกรดดีออกซีไรโบสนิวคลีอิก โครงสร้างข้อมูล