And*_*lls 11 algorithm networking graph np-complete minimum
有一个城镇网络,由各种整数长度的道路连接.
旅行者希望从一个城镇到另一个城镇乘车.但是,他不想最大限度地减少行进距离; 相反,他希望尽量减少旅程中的汽油成本.汽油可以在任何城市购买,但每个城市以各种(整数)价格供应汽油(因此最短的路线不一定是最便宜的).1单位汽油使他能够驾驶1个单位的距离.他的汽车只能在油箱中装载这么多汽油,他可以选择在他经过的每个城市购买多少汽油.找到最低的汽油成本.
有谁知道可以用来解决这个问题的有效算法？即使是这类问题的名称也是有用的,这样我自己就可以研究它!显然它与最短路径问题并不完全相同.任何其他提示赞赏!
编辑 - 我所说的实际问题是将有<1000个城市; <10000道路; 汽油箱的容量将介于1到100之间.
如果您愿意增加图表的大小,可以使用Djikstra算法直接解决这个问题.
假设你的汽油箱可容纳0到9个汽油.
这个想法是将每个城镇分成10个节点,城镇t的节点x代表城镇t,其中有x个单位的汽油.
然后,您可以在此展开的图表上构建零成本边缘,以表示在不同城镇之间行驶(在此过程中使用汽油,因此如果距离为3,您将从8级节点转到5级节点),以及更多边缘到代表用每单位汽油填充每个城镇的水箱(费用取决于城镇).
然后应用Djikstra应该从开始到结束给出最低成本路径.
我认为问题是：汽油是否有可能使潜在的旅行商问题在计算上更加可行？如果不是，则不存在有效的非逼近算法。
当然，您可以找到针对边缘情况的有效解决方案，并且在汽油条件下可能会有更多边缘情况，例如，始终首先考虑这个城市，因为汽油非常便宜。