传送旅行者，时间最优利润问题
我刚接触旅行推销员问题，也刚开始使用StackOverflow，如果我说错了什么，请告诉我。
简介：
我正在为一个游戏编写一个优化利润和时间的多交易算法，这个游戏涉及多个城市（节点）和多个国家（区域），具体情况如下：
- 在两个相连的城市之间旅行所需的时间总是相同的；
- 城市之间不是线性连接的（有些城市之间可以瞬移，所需时间相同）；
- 某些国家（区域）有瞬移路线，使得最短路径可以通过其他国家；
- 旅行者（或商人）有金币、货物重量和在特定交易路线上的交易数量限制。交易路线可以跨越多个城市。
问题参数：
内存中已经存在一个数据库（python:sqlite），它保存了基于源城市和目的城市的交易信息，包括中间最短路径的城市数组和数量，以及限制因素和其对总资本的百分比回报（如果没有限制因素，则选择对总资本回报最高的方法）。
- 我想在某个预设的时间段内找到最佳利润（例如30分钟）；
- 进入新城市的过程是同时进行的；
- 通常在城市地图上旅行所需的时间是固定的（例如2分钟）；
- 发起第一次或任何新交易所需的时间与穿越一个城市地图的时间相同（例如2分钟）；
- 我的起点可能没有有效的交易（我需要去第一个/最近的/最好的交易地点）。
目前的伪解决方案
优化
首先，我意识到由于我有时间限制，并且我知道每次跳跃所需的时间（包括发起交易的时间），我可以将图限制为所有跳跃次数小于或等于 max_hops=int(max_time/route_time) -1 的交易。我会剔除那些不在这个时间限制内的交易，去掉那些最短路径长度大于 max_hops 的城市。
我会在交易数据库中添加一条记录，包含我当前城市与所有现有交易的起始城市之间的最短路径，并将它们的回报设为0%。我会限制这些城市的跳跃次数小于 max_hops，同时计算从当前城市到起始城市的跳跃加上该交易的最短路径跳跃是否超过 max_hops，并去掉那些超过限制的。
然后，我会将剩下的不是 (current_city->starting_city) 的交易添加到所有目的城市和起始城市之间的交易路线，回报设为0%，前提是跳跃次数不超过 max_hops。
最后，我会剔除所有不在交易数据库中的城市，这些城市既不是起始城市，也不是目的城市，或者不是最短路径城市数组的一部分。
图搜索
这样我就得到了一个（大大）缩小的在时间限制内可行的交易图（例如30分钟）。
因为所有相连的节点都是相邻的，连接的权重默认都是1。我将交易的百分比回报除以跳跃次数，然后取倒数再加1（这意味着100%回报的路线权重为1.01）。如果回报为0%，我加... 2？
这样就应该能返回最有利可图的路线...
问题：
主要是，
当我有剩余的资金或空间时，如何添加多条路线的能力，并保持路径寻找仅限于单一交易路线？由于城市中商品以多种价格和数量出售，会有很多重叠的路线。
我该如何惩罚发起新交易路线的行为？
在这种情况下，图搜索真的有用吗？
顺便说一下，
- 我应该（或不应该）对图进行哪些修剪/优化？
- 我的权重方法正确吗？我觉得这会给我不成比例的权重。我应该使用实际回报而不是百分比回报吗？
- 如果我用python编程，像 python-graph 这样的库适合我的需求吗？还是说写一个专门的函数会节省很多开销（因为我了解到，图搜索算法可能计算量很大）？
- 我最好使用A*搜索吗？
- 我应该在交易数据库中预先计算最短路径点并最大化优化，还是应该把所有工作留给图搜索？
- 你能发现我可以改进的地方吗？
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上运行。我还是坚持我的看法：检查所有的选项。我非常怀疑获取路线和交易信息所花的时间会比计算最佳解决方案的时间更长。
我觉得你定义的问题属于一种叫做库存-路线问题的类别。我猜因为你有商品和钱，所以旅行者在选择的路线中既在买东西也在卖东西。首先，我们假设所有的情况都是确定的——需求的商品数量、可用的供应、买卖价格等等，都是提前知道的。随机版本就会复杂得多（这显而易见）。
一个目标是最大化利润，同时要考虑到钱和商品的限制。如果旅行者需要回家，那就像是一个旅游路线；如果不需要，那就像是一条路径。因为你没有要求旅行者访问每一个节点，所以这不是一个旅行商问题（TSP）。这很好，因为最短路径问题通常比旅行商问题要容易解决得多。
由于有额外的限制和每个节点上有限的选择，我建议你可以先尝试使用动态规划来解决这个问题。它可以帮助你列出在每个阶段买卖的东西，而且阶段的数量是有限的。此外，因为你对决策有时间限制，这也限制了选择的状态空间。
对于那些建议使用Dijkstra算法的人，你们可能是对的——标记的方式需要包括时间、钱、商品和相应的利润。可能Dijkstra算法的假设在考虑利润的复杂性时并不适用。我还没有仔细考虑这一点。
这里有一个链接，里面有一个类似的资本预算问题。
祝你好运！