传送旅行者，随着时间的推移获得最佳利润问题

Question

我对整个旅行推销员问题以及 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. 图搜索在这种情况下有用吗？

旁注，

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

Answer 1

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

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

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

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

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 上运行。我坚持我的解决方案：检查一切。我强烈怀疑获取路线和贸易信息所需的时间比计算最佳解决方案所需的时间要长。

Answer 2

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

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

由于侧面的限制和每个节点后续步骤的选择有限 - 我会考虑使用动态编程作为解决方案技术的第一次尝试。它将帮助您枚举您在每个阶段购买和出售的商品，并且阶段数量有限。此外，由于您对决策施加了时间限制，因此限制了选择的状态空间。

对于那些建议 Djikstra 算法的人来说——你可能是对的——标签约定需要包括时间、硬币、商品以及相应的利润。由于利润的复杂性增加，Djikstra 的假设可能不适用于此。还没有想清楚。

这是一个链接，指向资本预算中的类似问题。

祝你好运 ！