寻找最小路径的动态规划
寻找最小路径的动态规划
提问于 2018-11-13 18:40:46
我在设计DP问题的解决方案时遇到了问题。
假设你想从城市A旅行到城市B，在途中有n个中途停留站，你有许多选择在每个中途停留时选择一家酒店。所涉及的成本是在中途停留时到某家酒店的旅行成本(让我们称其为tij，其中i是当前中途停留，j是下一个中途停留)，以及在中途停留j的酒店停留的成本(让我们称之为sj)。设计一种动态规划算法来选择B城市的最优路线和一家旅馆，以最小化整个旅行的成本。分析其正确性和运行时间。
回答 1
Stack Overflow用户
发布于 2019-04-23 05:13:08
这里有一个可能正确的算法:将停靠点定义为a1、a2、a3、a4、a5、a6.....an，每个停靠点的最小成本为c1、c2、c3、c4、c5...cn
第一站。计算A城市到a1的路由开销，并存储在c1中。
第二站。计算A到a2的路由开销，计算a1到a2的路由开销加c1。选择较小的成本并将其存储到c2
第三站。计算从A到a3的路由开销、a1到a3加上c1的开销以及a2到a3加上c2的开销。选择最小的成本并将其存储到c3
……..。
最后，在相同的步骤下，我们可以找到从A到B的最小代价cn+1
动态表达式为ci=min(c1+t(1，i)，c2+t(2，i)，c3+t(3，i)，...，c(i-1)+t(i-1，i))
我们尝试所有可能的路线到每个停靠点，并找到最小的成本，因此为什么答案是我们选择的路线是最小化的
该算法运行时间为O(n^2)，考虑构建一个大小为n*n的二维数组
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53279189
复制相关文章
相似问题
腾讯云开发者
