11

有一个城镇网络，由各种整数长度的道路连接。

一位旅行者希望开车从一个城镇到另一个城镇。但是，他不想最小化行驶的距离；相反，他希望尽量减少旅途中的汽油费用。汽油可以在任何城市购买，但是每个城市以不同的（整数）价格供应汽油（因此为什么最短的路线不一定是最便宜的）。1 个单位的汽油使他能够行驶 1 个单位的距离。他的车只能在油箱里装这么多汽油，他可以选择在他所经过的每个城市购买多少单位的汽油。找出最低的汽油成本。

有谁知道可以用来解决这个问题的有效算法？即使是这类问题的名称也会很有用，这样我就可以自己研究了！显然，它与最短路径问题并不完全相同。任何其他提示表示赞赏！

编辑-我遇到的实际问题表明将有<1000个城市；<10000 条道路；油箱容量将在 1 到 100 之间。

4

6 回答 6

5

如果您愿意增加图形的大小，您可以直接使用Djikstra 的算法来解决这个问题。

假设您的油箱可以容纳 0 到 9 个单位的汽油。

这个想法是将每个城镇分成 10 个节点，城镇 t 的节点 x 表示在城镇 t，油箱中有 x 个单位的汽油。

然后，您可以在此扩展图上构建零成本边以表示不同城镇之间的旅行（在此过程中用尽汽油，因此如果距离为 3，您将从 8 级节点转到 5 级节点），并且更多边到表示在每个城镇用一单位汽油加满油箱（费用取决于城镇）。

然后应用 Djikstra 应该给出从开始到结束的最低成本路径。

于 2012-08-17T18:01:21.150 回答
1

我认为问题是：汽油是否有可能使潜在的旅行商问题在计算上更可行？如果不是，则没有有效的非逼近算法。

当然，你可以为边缘情况找到有效的解决方案，并且在汽油条件下可能会有更多的边缘情况，例如，总是先考虑这个城市，因为汽油很便宜。

于 2012-08-17T16:33:25.987 回答
1

我认为您可以通过动态编程来解决这个问题。对于每个节点，您保存一组汽油成本元组和使用该汽油的路径长度，其中包含最佳解决方案。您循环遍历所有节点的每一步，如果有一个节点可以去，并且已经有解决方案，那么您循环遍历所有节点，您可以使用解决方案去。您选择最低成本，但请注意：您必须考虑当前节点中的汽油成本。阵列中所有高于当前节点成本的成本，都可以在当前节点购买。请注意，应该重新计算已经有解决方案的节点，因为您可以从那里去的节点可能会改变。您从结束节点开始，将解决方案设置为一个空数组（或一个成本和长度为 0 的条目）。

于 2012-08-17T16:36:53.983 回答
0

这可以使用遗传算法进行适当优化。遗传算法在一些复杂问题上击败了人类： http ://en.wikipedia.org/wiki/Genetic_algorithm

遗传算法的要点是：

  1. 提出候选解决方案的排名功能
  2. 想出一组独特的候选解决方案。用一些随机生成的可能性对其进行初始化。也许是 10 或 100 或 1000...
  3. 从池中复制一个候选解决方案并以某种方式对其进行扰动 - 添加一个城镇、删除一个城镇、添加两个城镇等。这可能会改善或恶化问题 - 您的排名功能将帮助您判断。你选哪一个？通常，您会选择最好的，但有时，您会故意选择一个，以免陷入局部最优。
  4. 新解决方案是否已经排名？如果是，请将其丢弃并转到
    1. 如果没有，请继续...
  5. 将受干扰的候选人添加回其新计算的排名下的池中
  6. 继续这个（从#3重复），直到你觉得你已经完成了足够长的时间
  7. 最后，选择排名最高的答案。它可能不是最佳的，但它应该非常好。
于 2012-08-17T23:17:09.447 回答
0

我会试试这个：

  1. 找到从起点到终点的最短路线。Dijkstra 的算法适用于此。
  2. 找出这条路线行驶的最低汽油成本。我不知道有任何现成的算法可以解决这个问题，但除非沿途有许多城市，否则即使是详尽的搜索也不应该在计算上不可行。
  3. 寻找下一条最短的路线...

定义精确的停止标准是一个挑战，最好是在新测试路线的最低成本大于已测试路线的最低成本时停止。

因此，使用 2 种算法，一种用于问题的每个部分。

于 2012-08-17T16:59:13.307 回答
0

您也可以将其表述为整数线性规划 (ILP) 问题。优点是有许多现成的求解器可用于此任务，并且复杂性不会像具有罐大小的彼得斯解决方案那样快速增长。

在这个特定问题中的变量将是在任何一个城镇购买的汽油量、沿途任何城镇的汽车油箱量以及实际使用的道路。约束条件必须保证汽车在每条道路上消耗必要的燃料，并且在任何城镇的燃料不小于 0 或超过 MAX 个单位，并且道路构成从 A 到 B 的路径。目标是购买燃料的总成本。

整个事情可能看起来很可怕（ILP 公式经常这样做），但这并不意味着它不能在合理的时间内解决。

于 2012-08-20T16:06:10.383 回答