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

发布于 2024-08-21 13:28:41 字数 2177 浏览 7 评论 0原文

我对整个旅行推销员问题以及 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. 你能注意到我有什么可以改进的地方吗?

I'm new to the whole traveling-salesman problem as well as stackoverflow so let me know if I say something that isn't quite right.

Intro:

I'm trying to code a profit/time-optimized multiple-trade algorithm for a game which involves multiple cities (nodes) within multiple countries (areas), where:

  • The physical time it takes to travel between two connected cities is always the same ;
  • Cities aren't linearly connected (you can teleport between some cities in the same time);
  • Some countries (areas) have teleport routes which make the shortest path available through other countries.
  • The traveler (or trader) has a limit on his coin-purse, the weight of his goods, and the quantity tradeable in a certain trade-route. The trade route can span multiple cities.

Question Parameters:

There already exists a database in memory (python:sqlite) which holds trades based on their source city and their destination city, the shortest-path cities inbetween as an array and amount, and the limiting factor with its % return on total capital (or in the case that none of the factors are limiting, then just the method that gives the highest return on total capital).

  • I'm trying to find the optimal profit for a certain preset chunk of time (i.e. 30 minutes)
  • The act of crossing into a new city is actually simultaneous
  • It usually takes the same defined amount of time to travel across the city map (i.e. 2 minutes)
  • The act of initiating the first or any new trade takes the same time as crossing one city map (i.e. 2 minutes)
  • My starting point might not actually have a valid trade ( I would have to travel to the first/nearest/best one )

Pseudo-Solution So Far

Optimization

First, I realize that because I have a limit on the time it takes, and I know how long each hop takes (including -1 for intiating the trade), I can limit the graph to all trades whose hops are under or equal to max_hops=int(max_time/route_time) -1. I cut elements of the trade database that don't fall within this time limit, pruning cities that have shortest-path lengths greater than max_hops.

I make another entry into the trades database that includes the shortest-paths between my current city and the starting cities of all the existing trades that aren't my current city, and give them a return of 0%. I would limit these to where the number of city hops is less than max_hops, and I would also calculate whether the current city to the starting city plus that trades shortest-path-hops would excede max_hops and remove those that exceded this limit.

Then I take the remaining trades that aren't (current_city->starting_city) and add trade routes with return of 0% between all destination and starting cities wheres the hops doesn't excede max_hops

Then I make one last prune for all cities that aren't in the trades database as either a starting city, destination city, or part of the shortest path city arrays.

Graph Search
I am left with a (much) smaller graph of trades feasible within the time limit (i.e. 30 mins).

Because all the nodes that are connected are adjacent, the connections are by default all weighted 1. I divide the %return over the number of hops in the trade then take the inverse and add + 1 (this would mean a weight of 1.01 for a 100% return route). In the case where the return is 0%, I add ... 2?

It should then return the most profitable route...


The Question:

Mostly,

  1. How do I add the ability to take multiple routes when I have left over money or space and keep route finding through path discrete to single trade routes? Due to the nature of the goods being sold at multiple prices and quantities within the city, there would be a lot of overlapping routes.

  2. How do I penalize initiating a new trade route?

  3. Is graph search even useful in this situation?

On A Side Note,

  1. What kinds of prunes/optimizations to the graph should I (or should I not) make?
  2. Is my weighting method correct? I have a feeling it will give me disproportional weights. Should I use the actual return instead of percentage return?
  3. If I am coding in python are libraries such as python-graph suitable for my needs? Or would it save me a lot of overhead (as I understand, graph search algorithms can be computationally intensive) to write a specialized function?
  4. Am I best off using A* search ?
  5. Should I be precalculating shortest-path points in the trade database and maxing optimizations or should I leave it all to the graph-search?
  6. Can you notice anything that I could improve?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

白日梦 2024-08-28 13:28:41

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

相反,简单的广度优先搜索怎么样?

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

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

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

If this is a game where you are playing against humans I would assume the total size of the data space is actually quite limited. If so I would be inclined to throw out all the fancy pruning as I doubt it's worth it.

Instead, how about a simple breadth-first search?

Build a list of all cities, mark them unvisited

Take your starting city, mark the travel time as zero

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(): the outer loop executes cities * maximum hops times. The inner loop executes once per city. No memory allocations are needed.

Now, for each city look at what you can buy here and sell there. When figuring the rate of return on a trade remember that growth is exponential, not linear. Twice the profit for a trade that takes twice as long is NOT a good deal! Look up how to calculate the internal rate of return.

If the current city has no trade don't bother with the full analysis, simply look over the neighbors and run the analysis on them instead, adding one to the time for each move.

If you have CPU cycles to spare (and you very well might, anything meant for a human to play will have a pretty small data space) you can run the analysis on every city adding in the time it takes to get to the city.

Edit: Based on your comment you have tons of CPU power available as the game isn't running on your CPU. I stand by my solution: Check everything. I strongly suspect it will take longer to obtain the route and trade info than it will be to calculate the optimal solution.

梦里泪两行 2024-08-28 13:28:41

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

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

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

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

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

祝你好运 !

I think you've defined something that fits into a class of problems called inventory - routing problems. I assume since you have both goods and coin, the traveller is both buying and selling along the chosen route. Let's first assume that EVERYTHING is deterministic - all quantities of goods in demand, supply available, buying and selling prices, etc are known in advance. The stochastic version gets more difficult (obviously).

One objective would be to maximize profits with a constraint on the purse and the goods. If the traveller has to return home its looks like a tour, if not, it looks like a path. Since you haven't required the traveller to visit EVERY node, it is NOT a TSP. That's good - shortest path problems are generally much easier than TSPs to solve.

Because of the side constraints and the limited choice of next steps at each node - I'd consider using dynamic programming first attempt at a solution technique. It will help you enumerate what you buy and sell at each stage and there's a limited number of stages. Also, because you put a time constraint on the decision, that limits the state space of choices.

To those who suggested Djikstra's algorithm - you may be right - the labelling conventions would need to include the time, coin, and goods and corresponding profits. It may be that the assumptions of Djikstra's may not work for this with the added complexity of profit. Haven't thought through that yet.

Here's a link to a similar problem in capital budgeting.

Good luck !

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文