python - 传送旅行者，随着时间的推移优化利润问题

Question

我对整个旅行商问题以及 stackoverflow 都不熟悉，所以如果我说的不太对，请告诉我。

介绍:

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

在两个相连的城市之间旅行所需的物理时间总是相同的；

城市不是线性连接的(你可以同时在一些城市之间传送)；

一些国家(地区)有传送路线，可以通过其他国家的最短路径。

旅行者(或商人)的钱包、 cargo 的重量以及在特定贸易路线上的可交易数量都有限制。贸易路线可以跨越多个城市。

问题参数:

内存中已经存在一个数据库 (python:sqlite)，它根据源城市和目的地城市、作为数组和金额的最短路径城市以及总资本返回率的限制因素(或如果没有一个因素是限制性的，那么只有总资本返回率最高的方法)。

我试图找到某个预设时间段(即 30 分钟)的最佳利润

穿越到新城市的行为其实是同时发生的

穿越城市 map 通常需要相同的定义时间(即 2 分钟)

发起第一笔或任何新交易的行为与穿越一张城市 map 所需的时间相同(即 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？

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

问题:

主要是

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

如何惩罚发起新的贸易路线？

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

旁注，

我应该(或不应该)对图表进行什么样的修剪/优化？

我的加权方法是否正确？我有一种感觉，它会给我不成​​比例的权重。我应该使用实际返回而不是百分比返回吗？

如果我在 python 中编码，像 python-graph 这样的库是否适合我的需要？或者它会为我节省很多开销(据我所知，图搜索算法可能是计算密集型的)来编写一个专门的函数？

我最好使用 A* 搜索吗？

我应该预先计算交易数据库中的最短路径点并最大化优化，还是应该将其全部留给图形搜索？

你能注意到我可以改进的地方吗？

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():外循环执行城市 * 最大跳数。内循环每个城市执行一次。不需要内存分配。

现在，对于每个城市，看看你可以在这里买什么，在那里卖什么。在计算交易返回率时，请记住增长是指数级的，而不是线性的。需要两倍时间的交易的两倍利润是 不是 一个很好的协议(protocol)!查看如何计算内部 yield 。

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

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

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