交易物品的优化算法
Optimization Algorithm for Trading Items
当您有想要出售的东西或想要购买的东西时,基本上有两种选择:使用金钱或用其他物品进行交易。这种情况发生在现实生活中,也发生在您拥有适当交易系统(开放市场)的游戏中。
我的问题是:是否有一个最佳算法能够接收市场上所有可用的交易并返回最佳、最佳的交易顺序以达到项目 x 哪个最小化总成本?
我举个例子:
假设在市场上我们有两张桌子,一张供想要 trade/sell 东西的人使用,另一张供想买东西的人使用:
卖家:
Item I Have
Items I Want
(or) Price I Want
Item A
-
140
Item A
-
160
Item B
-
50
Item C
Item A + Item B
220
Item D
Item C
240
Item E
Item A + Item D
360
Item X
Item E
360
买家:
Item I Want
Price I'll Pay
Item A
150
Item B
70
它必须考虑以下一些情况:
- 仅使用金钱获得项目 x;
- 使用金钱和交易获得项目 x;
- 仅使用交易获得项目 x;
- 在获得最终交易之前考虑几笔小额交易;
- 市场是动态的,价格并不是真正的“固定”。这意味着一些 sellers/buyers 的价格肯定 buying/selling 低于或高于平均水平。该算法应该在这种“放错地方”的交易中茁壮成长。
不知道能不能说清楚。我有工程和编程方面的背景,并试图找到可以解决这个问题但找不到的东西。我想这与 Greedy Algorithms 有关,但老实说,我不知道是否已经证明对这个问题有好处,或者神经网络是否可以在这里为我做点什么。
我知道这个问题一点都不简单。事实上,有很多人像这样以 buying/selling 物品为生。但他们主要依靠自己的专业知识和对市场上出现的机会的挖掘。
我一开始以为可以把这个问题转化成“旅行商”类型的问题,城市就是物品,城市之间的距离就是价格,我会用一些已经建立的这个问题的算法就可以了。但我不知道它是否有效(如果其他人已经尝试过)。
你可以用single source shortest path algorithm for weighted directed graphs which allows negative-weight edges, such as the Bellman–Ford algorithm解决这个问题。
图中的节点是项目集,源节点是你开始的项目集(可能是空集),边要么是购买项目(边权重是购买价格),出售一个物品(边权重为负的售价),或交易一组物品(边权重为零)。
Bellman–Ford 算法将找到使您最终可能得到的每组项目的成本最小化(即,使您剩余的金额最大化)的路径。然后,您可以简单地采用路径的最低成本到包含您希望获得的项目的任何集合。
您的经济可能允许套利,即通过一系列交易、购买和销售,您可以最终获得与开始时相同的物品,但有更多的钱。 (在您的示例中,您可以以 140 的价格购买商品 A,然后以 150 的价格出售。)在这种情况下,图表包含负权重循环,因此任何商品都没有“最佳”价格,因为您可以利用套利机会无限的利润。如果存在负权重循环,Bellman–Ford 算法将检测并报告它,而不是寻找最短路径。
当您有想要出售的东西或想要购买的东西时,基本上有两种选择:使用金钱或用其他物品进行交易。这种情况发生在现实生活中,也发生在您拥有适当交易系统(开放市场)的游戏中。
我的问题是:是否有一个最佳算法能够接收市场上所有可用的交易并返回最佳、最佳的交易顺序以达到项目 x 哪个最小化总成本?
我举个例子: 假设在市场上我们有两张桌子,一张供想要 trade/sell 东西的人使用,另一张供想买东西的人使用:
卖家:
Item I Have | Items I Want | (or) Price I Want |
---|---|---|
Item A | - | 140 |
Item A | - | 160 |
Item B | - | 50 |
Item C | Item A + Item B | 220 |
Item D | Item C | 240 |
Item E | Item A + Item D | 360 |
Item X | Item E | 360 |
买家:
Item I Want | Price I'll Pay |
---|---|
Item A | 150 |
Item B | 70 |
它必须考虑以下一些情况:
- 仅使用金钱获得项目 x;
- 使用金钱和交易获得项目 x;
- 仅使用交易获得项目 x;
- 在获得最终交易之前考虑几笔小额交易;
- 市场是动态的,价格并不是真正的“固定”。这意味着一些 sellers/buyers 的价格肯定 buying/selling 低于或高于平均水平。该算法应该在这种“放错地方”的交易中茁壮成长。
不知道能不能说清楚。我有工程和编程方面的背景,并试图找到可以解决这个问题但找不到的东西。我想这与 Greedy Algorithms 有关,但老实说,我不知道是否已经证明对这个问题有好处,或者神经网络是否可以在这里为我做点什么。
我知道这个问题一点都不简单。事实上,有很多人像这样以 buying/selling 物品为生。但他们主要依靠自己的专业知识和对市场上出现的机会的挖掘。
我一开始以为可以把这个问题转化成“旅行商”类型的问题,城市就是物品,城市之间的距离就是价格,我会用一些已经建立的这个问题的算法就可以了。但我不知道它是否有效(如果其他人已经尝试过)。
你可以用single source shortest path algorithm for weighted directed graphs which allows negative-weight edges, such as the Bellman–Ford algorithm解决这个问题。
图中的节点是项目集,源节点是你开始的项目集(可能是空集),边要么是购买项目(边权重是购买价格),出售一个物品(边权重为负的售价),或交易一组物品(边权重为零)。
Bellman–Ford 算法将找到使您最终可能得到的每组项目的成本最小化(即,使您剩余的金额最大化)的路径。然后,您可以简单地采用路径的最低成本到包含您希望获得的项目的任何集合。
您的经济可能允许套利,即通过一系列交易、购买和销售,您可以最终获得与开始时相同的物品,但有更多的钱。 (在您的示例中,您可以以 140 的价格购买商品 A,然后以 150 的价格出售。)在这种情况下,图表包含负权重循环,因此任何商品都没有“最佳”价格,因为您可以利用套利机会无限的利润。如果存在负权重循环,Bellman–Ford 算法将检测并报告它,而不是寻找最短路径。