7

我对整个旅行推销员问题以及stackoverflow都是新手，所以如果我说的一些不太正确的话，请告诉我。

介绍：

我正在尝试为涉及多个国家（地区）内的多个城市（节点）的游戏编写利润/时间优化的多交易算法，其中：

  • 在两个相连的城市之间旅行的实际时间总是相同的；
  • 城市不是线性连接的（你可以同时在一些城市之间传送）；
  • 一些国家（地区）有传送路线，使通过其他国家的最短路径可用。
  • 旅行者（或商人）对他的钱包、他的货物的重量以及在某个贸易路线上可交易的数量都有限制。贸易路线可以跨越多个城市。

问题参数：

内存中已经存在一个数据库（python：sqlite），它根据源城市和目的地城市保存交易，中间的最短路径城市作为数组和数量，以及总资本回报率的限制因素（或在没有任何因素限制的情况下，那么只有总资本回报率最高的方法）。

  • 我正在尝试在某个预设的时间段（即 30 分钟）内找到最佳利润
  • 穿越到一个新城市的行为实际上是同时发生的
  • 穿越城市地图通常需要相同的定义时间（即 2 分钟）
  • 发起第一个或任何新交易的行为与穿越一个城市地图所需的时间相同（即 2 分钟）
  • 我的起点可能实际上没有有效的交易（我必须前往第一个/最近/最好的交易）

到目前为止的伪解决方案

优化

首先，我意识到因为我对所花费的时间有限制，并且我知道每一跳需要多长时间（包括启动交易的 -1），我可以将图表限制为跳数小于或等于 的所有交易max_hops=int(max_time/route_time) -1。我删除了贸易数据库中不属于这个时间限制的元素，修剪了最短路径长度大于max_hops.

我再次进入交易数据库，其中包括我当前城市和不是我当前城市的所有现有交易的起始城市之间的最短路径，并给它们 0% 的回报。我会将这些限制在城市跳数少于 的地方max_hops，并且我还将计算当前城市到起始城市加上交易最短路径跳数的城市是否会超过max_hops并删除那些超过此限制的城市。

然后我采取剩余的交易，(current_city->starting_city)并在所有目的地和起始城市之间添加回报为 0% 的贸易路线，其中啤酒花不超过max_hops

然后，我对所有不在交易数据库中的城市作为起始城市、目的地城市或最短路径城市阵列的一部分进行最后一次修剪。

图表搜索 我留下了一个在时间限制（即 30 分钟）内可行的（小得多的）交易图表。

因为所有连接的节点都是相邻的，所以默认情况下，连接的权重都是 1。我将 %return 除以交易中的跳数，然后取倒数并加上 + 1（这意味着一个权重为 1.01 100％返回路线）。在收益率为 0% 的情况下，我添加 ... 2？

然后它应该返回最有利可图的路线......

问题：

大多，

  1. 当我有多余的钱或空间时，如何增加走多条路线的能力，并通过离散的路径寻找单条贸易路线的路线？由于商品在城市内以多种价格和数量销售的性质，会有很多重叠的路线。

  2. 我如何惩罚启动新的贸易路线？

  3. 在这种情况下，图形搜索甚至有用吗？

在旁注中，

  1. 我应该（或不应该）对图表进行哪些类型的修剪/优化？
  2. 我的加权方法正确吗？我有一种感觉，它会给我不成​​比例的重量。我应该使用实际回报而不是百分比回报吗？
  3. 如果我在 python 中编码，那么python-graph之类的库是否适合我的需求？或者它会为我节省很多开销（据我所知，图形搜索算法可能是计算密集型的）来编写一个专门的函数？
  4. 我最好使用 A* 搜索吗？
  5. 我应该预先计算交易数据库中的最短路径点并最大化优化，还是应该将其全部留给图形搜索？
  6. 你能注意到我可以改进的地方吗？
4

2 回答 2

2

如果这是一个与人类对战的游戏，我会假设数据空间的总大小实际上是非常有限的。如果是这样，我会倾向于放弃所有花哨的修剪，因为我怀疑它是否值得。

相反，简单的广度优先搜索怎么样？

建立所有城市的列表，将它们标记为未访问

以您的出发城市，将旅行时间标记为零

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

O()：外循环执行城市*最大跳数。内部循环每个城市执行一次。不需要内存分配。

现在，对于每个城市，看看你可以在这里买什么，在那里卖什么。在计算交易回报率时，请记住增长是指数的，而不是线性的。花费两倍时间的交易获得两倍的利润可不是什么好交易！查看如何计算内部收益率。

如果当前城市没有交易，请不要费心进行全面分析，只需查看邻居并对其进行分析，每次移动的时间都增加一个。

如果你有空闲的 CPU 周期（你很可能，任何供人类玩的东西都会有一个非常小的数据空间），你可以对每个城市运行分析，增加到达城市所需的时间。

编辑：根据您的评论，由于游戏未在您的 CPU 上运行，因此您拥有大量可用的 CPU 能力。我坚持我的解决方案：检查一切。我强烈怀疑获取路线和贸易信息比计算最佳解决方案需要更长的时间。

于 2010-02-13T05:48:11.720 回答
1

我认为您已经定义了适合一类称为库存的问题 - 路由问题。我假设由于您同时拥有商品和硬币，因此旅行者会沿着所选路线进行买卖。让我们首先假设一切都是确定性的——所有商品的需求量、可用供应量、买卖价格等都是预先知道的。随机版本变得更加困难（显然）。

一个目标是在限制钱包和货物的情况下实现利润最大化。如果旅行者必须回家，它看起来像一次旅行，如果不是，它看起来就像一条小路。由于您没有要求旅行者访问每个节点，因此它不是 TSP。这很好——最短路径问题通常比 TSP 更容易解决。

由于侧面约束和每个节点的后续步骤选择有限 - 我会考虑使用动态编程首先尝试解决方案技术。它将帮助您枚举您在每个阶段买卖的东西，并且阶段数量有限。此外，因为您对决策设置了时间限制，这限制了选择的状态空间。

对于那些建议 Djikstra 算法的人——你可能是对的——标签约定需要包括时间、硬币、商品和相应的利润。可能是 Djikstra 的假设可能不适用于这增加了利润的复杂性。还没想好。

这是资本预算中类似问题的链接。

祝你好运 ！

于 2010-02-15T20:31:52.817 回答