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 回答