通过使用动态规划找到站点的最佳位置来最小化管道成本
Minimizing cost of pipeline by finding optimal locations for stations using dynamic programming
我有一个关于动态规划的问题，我正在尝试为其描述一个算法。
问题：
要建造一条管道，您必须沿着已经确定的路径确定站点的最佳位置。管道连接点 x1 和 xn 并经过位置 x2、x3...x(n-1)。在 x1 和 xn 有站点，但问题的一部分是决定是否在点 xi 建立一个站点，因为 i = 2,3...n-1.If 建立一个站点相关的成本是 bi 并且如果在 xi 站和 xj 站之间修建一条管道，相应的成本为 cij。总造价为站场造价与相应管段造价之和。目标是确定站点的最佳位置，以使总成本最小化。
我们必须使用动态规划为此描述一个通用算法。
我的方法是将其视为一个杆切割问题，并尝试制作一个矩阵并将成本降至最低，但我不确定如何处理正在建造的车站成本的额外变量。鉴于许多变量，我应该如何处理这个问题？我将如何开发递归公式？
如有任何帮助，我们将不胜感激！
编辑：是的，我同意这个问题有点不清楚，一开始也让我感到困惑，但这就是问题中给出的全部内容。我相信站场和管线的造价不同，应该有一个最优的方式。
这里的关键见解是连接任意两点 xi 和 xj 的最小成本（称之为 m ij) 独立于该段之外的配置（即 x*1* 到 xi 和 xj 到 xn).
您的动态规划问题是索引并存储每个找到的成本，并浮动部分解决方案支持调用树。
基本情况是连接两个相邻节点 xi 和 xj 的成本（其中 j=i+1 ), 就是 cij (你不能在那里建一个新站)。
最简单的情况是j=i+2；在i+1建站有利可图吗？用代数术语来说，c(i)(i+2) < b(i+1) + c(i)(i+1) + c(i+1)(i+2) ?
一般来说，你需要在一个find_first_station(i, j)函数上重复。这应该找到在已经位于 i 和 j 的站之间建立的最低索引站的位置。对于每个点 'k, i<k<j, build a station atk, run a pipeik, and then recur withfind_first_station(k, j). Return the solution (all station locations) with the minimum cost for anyk`，如果 cij 是最小成本，则为空列表.
你能从那里拿走吗？
我有一个关于动态规划的问题，我正在尝试为其描述一个算法。
问题： 要建造一条管道，您必须沿着已经确定的路径确定站点的最佳位置。管道连接点 x1 和 xn 并经过位置 x2、x3...x(n-1)。在 x1 和 xn 有站点，但问题的一部分是决定是否在点 xi 建立一个站点，因为 i = 2,3...n-1.If 建立一个站点相关的成本是 bi 并且如果在 xi 站和 xj 站之间修建一条管道，相应的成本为 cij。总造价为站场造价与相应管段造价之和。目标是确定站点的最佳位置，以使总成本最小化。
我们必须使用动态规划为此描述一个通用算法。 我的方法是将其视为一个杆切割问题，并尝试制作一个矩阵并将成本降至最低，但我不确定如何处理正在建造的车站成本的额外变量。鉴于许多变量，我应该如何处理这个问题？我将如何开发递归公式？ 如有任何帮助，我们将不胜感激！
编辑：是的，我同意这个问题有点不清楚，一开始也让我感到困惑，但这就是问题中给出的全部内容。我相信站场和管线的造价不同，应该有一个最优的方式。
这里的关键见解是连接任意两点 xi 和 xj 的最小成本（称之为 m ij) 独立于该段之外的配置（即 x*1* 到 xi 和 xj 到 xn).
您的动态规划问题是索引并存储每个找到的成本，并浮动部分解决方案支持调用树。
基本情况是连接两个相邻节点 xi 和 xj 的成本（其中 j=i+1 ), 就是 cij (你不能在那里建一个新站)。
最简单的情况是j=i+2；在i+1建站有利可图吗？用代数术语来说，c(i)(i+2) < b(i+1) + c(i)(i+1) + c(i+1)(i+2) ?
一般来说，你需要在一个find_first_station(i, j)函数上重复。这应该找到在已经位于 i 和 j 的站之间建立的最低索引站的位置。对于每个点 'k, i<k<j, build a station atk, run a pipeik, and then recur withfind_first_station(k, j). Return the solution (all station locations) with the minimum cost for anyk`，如果 cij 是最小成本，则为空列表.
你能从那里拿走吗？