有一个城镇网络，由各种整数长度的道路相连。建议算法（图 - 可能是NP-Complete）
一位旅行者希望在他的车上从一个小镇旅行到另一个小镇。但是，他不想尽量减少行驶距离，相反，他希望尽量减少旅程的汽油成本。汽油可以在任何城市购买，但每个城市以各种（整数）价格供应汽油（因此为什么最短路线不一定是最便宜的）。 1个汽油单位使他能驾驶1个单位的距离。 他的汽车只能在汽油箱中装载如此多的汽油，他可以选择在每个城市旅行时购买多少汽油。找到最低汽油成本。
有没有人知道可以用来解决这个问题的有效算法？即使这种类型的问题的名称将是有用的，所以我可以自己研究它！显然这与最短路径问题并不完全相同。任何其他技巧赞赏！
编辑 - 我的实际问题是，将有1000个城市<; < 10000道路;汽油箱容量将介于1到100之间。
我认为问题是：汽油是否有可能使潜在的旅行商问题在计算上更可行？如果不是，则不存在有效的非近似算法。
当然，你可以找到有效的边缘案例解决方案，并且可能会有更多的汽油边缘案例，因为汽油价格如此便宜，所以总是首先考虑这座城市。
我想你可以通过动态编程来解决这个问题。对于每个节点，您都会保存一组汽油成本元组以及使用该汽油的路径长度，其中包含最佳解决方案。您每循环一次都会遍历所有节点，并且如果有可以前往的节点（已经有解决方案），则可以通过解决方案循环遍历所有节点。您选择最低成本，但请注意：您必须考虑当前节点中的汽油成本。阵列中所有高于当前节点成本的成本可以在当前节点处购买。请注意，已经有解决方案的节点应该重新计算，因为您可以从那里访问的节点可能会发生变化。您从最终节点开始，将解决方案设置为空数组（或者一个成本和长度为0的条目）。最终的解决方案是在开始时采取解决方案并总结每个成本*的长度。
我不太明白这是如何工作的，但明天当我不太累时，我会再看一次。 – 2012-08-17 23:11:57
我想试试这个：
定义精确停止标准是一个小小的挑战，它可能是最好只是停止一旦发现一个新测试途径的最低成本比大已经测试的路线的最低成本。
因此，使用2个算法，每个问题的一部分。
这也是一个有效的解决方案，但不幸的是，非常慢。 – 2012-08-17 17:19:45
一旦最低成本开始再次增加，我认为你不能停止，最便宜的路线可能是最长的，最便宜的路线是最短的，例如...为了确保最便宜你必须检查每条路线：/ – 2012-08-17 22:45:04
我同意，这不是一个很好的答案。 – 2012-08-18 08:04:10
如果您愿意增加图形的大小，则可以直接使用Djikstra's algorithm来解决此问题。
假设您的汽油箱可容纳0至9个汽油单位。
的想法是将每个镇分成10个节点，与节点x用于表示与箱汽油的X单元处于镇吨镇吨。
然后，您可以在此扩展图上构造零成本边缘来表示不同城镇之间的行驶（在此过程中使用汽油，因此如果距离为3，您将从8级节点到5级节点），和更多的边缘来代表每个城镇用一个汽油单位填充油箱（费用取决于城镇）。
然后将Djikstra应该给从开始到结束的最低成本路径。
聪明 - 我喜欢这个！虽然如果你有一个大坦克，它确实使图形更大！ – 2012-08-17 22:37:34
这可以使用遗传算法适当地优化。遗传算法在一些复杂的问题，战胜人类： http://en.wikipedia.org/wiki/Genetic_algorithm
遗传算法的要点是：
你也可以制定，作为一个整数线性规划（ILP）问题。优点是有很多现成的解决方案可以完成这项任务，复杂性不会像Peters解决方案的坦克大小那样快速增长。
在这个特定问题的变量将是任何一个城市购买汽油的数量，在途中任何城市，并在汽车油箱量实际道路上拍摄的。 约束必须保证车上花费每条路上所需的燃料，并没有比在任何城镇燃料MAX单位小于0以上的道路构成了从A路径B. 目标将是所购燃料的总成本。
整个事情看起来怪异（ILP配方经常这样做），但并不意味着它不能在合理的时间来解决。
它看起来像背包问题，我想。让我们看看其他人说什么。 – 2012-08-17 16:32:35
我可以建议您将标题更改为“旅行推销员变化”或其他内容。目前的标题有些不伦不类。 – Nicolas78 2012-08-17 16:32:37
这既不是一个背包问题，也不是旅行推销员的问题：他想从A到B，而不是到处都是。这是一个特定的图形问题，它没有名称afaik。 – 2012-08-17 16:38:22