动态规划最优子结构_分析单元最短路径为何具有最优子结构性

作者：小丑西瓜9 | 2024-04-28 04:40:42

踩

分析单元最短路径为何具有最优子结构性

最优子结构是依赖特定问题和子问题的分割方式而成立的条件。各子问题具有最优解，就能求出整个问题的最优解，此时条件成立。

比如求广州到北京的最短距离，假设这个路径必经过中间的南京，那么先把路径分割为（广州，南京）和（南京，北京）。分别求出子路径的最短距离然后再连接，就可以得到广州到北京的最短路径。

因此，寻求最短路径的问题可以利用子路径的最优解获得整个问题的最优解。这样就可以证明，最短路径具有最优子结构。

反之，如果不能利用子问题的最优解获得整个问题的最优解，那么这种问题就不具有最优子结构。

很多问题的最优子结构都表现出非常直观的形式，以至于都不需要另外的证明过程。不过，遇到结构不是很直观的问题时，则需要用反证法证明（假设子问题的最优解不是整个问题的最优解）。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/500490