如何找到3 +路交易的机会（就像运动队如何做）

2018-06-22 11:25:57

我试图拼凑一个算法（最好用红宝石）来分析一个数据库，以找到像棒球队通常那样进行3种以上的交易的机会。

例如：

想象一下有100多支球队，每支球队都有20名左右的球员。每个玩家都有一些可能的属性组合。（比如“快跑速度”，“好防守”等）

每个球队都有玩家需求（具有上述可能集合中的特定属性）以及玩家提供的 （每个都具有与上述可能选项相匹配的属性）。

这个理论算法可以搜索所有的需求和要约，找到可以相互交易的团队的组合。

在理论情景中，想象三个团队：

A队有一名速度球员，并且需要一名防守能力出色的球员.F队有一名防守良好的球员，并且需要一名投篮能力出色的球员。Q队有一名球员有良好的投球并且需要一名速度很快的球员

因此，A，F和Q团队可以进行三方交易，每个人都可以获胜。

我的问题是关于可以识别这个机会的算法。这是一个算法之前解决的问题吗？如果是这样，我会欣赏任何方向在哪里看。关于如何在数据库中巧妙地使用缓存和cron来构建这个概念，我有一些不同的想法。在Rails中构建它。只是有点卡住寻找算法的机会。

您可以将您的需求和报价建模为图表：每个团队都是一个节点，并且从团队A到团队B的能力x iif A可以从B必须提供的x球员中获益。您可以在O(o + n)构建此图，其中o是商品数量， n是通过按商品属性对商品进行分类的需求数量。

现在，您需要在此图表中找到一个循环，以满足您在问题中没有陈述的特定属性（可能性为：长度> 3，最大长度，最大容量......）。对于这些问题中的每一个，您都可以使用现有的算法来解决这些问题（最大流量，最短路径，BFS，...）

链接地址: http://www.djcxy.com/p/63071.html