Optimal Substructure

释义 Definition

最优子结构：一种常见于算法（尤其是动态规划与贪心法分析）的性质，指一个问题的最优解可以由其子问题的最优解组合而成。换句话说，把问题拆成更小的部分分别求最优，再合并，就能得到整体最优。（在一些情形下还需配合“重叠子问题”等性质才能高效求解。）

发音 Pronunciation (IPA)

/ˈɑːptɪməl ˈsʌbstrʌktʃər/

例句 Examples

Dynamic programming works well when a problem has optimal substructure.
当一个问题具有最优子结构时，动态规划通常很有效。

In the shortest-path problem, optimal substructure means the best route to a destination contains best routes to intermediate points.
在最短路径问题中，最优子结构意味着到达终点的最佳路线包含到达中间节点的最佳路线。

词源 Etymology

optimal 来自拉丁语 optimus（“最好的”）；substructure 由 *sub-*（“下、次级”）+ structure（“结构”）构成。组合起来，“optimal substructure”字面意思是“最优解由更小层级的结构组成”，在算法语境中被专门用来描述“整体最优可由子问题最优拼合”的性质。

相关词 Related Words

• Dynamic Programming
• Overlapping Subproblems
• Greedy Algorithm
• Recurrence
• Bellman Equation
• Shortest Path
• Subproblem
• Divide And Conquer

文学与经典作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在动态规划章节系统讨论最优子结构与重叠子问题。
• Algorithm Design（Jon Kleinberg, Éva Tardos）：用大量实例说明何时成立最优子结构以及如何据此设计算法。
• The Algorithm Design Manual（Steven S. Skiena）：在算法设计与问题分类讨论中频繁使用该概念作为判断方法。