7

我正在尝试拼凑一个算法(最好在 ruby​​ 中),它将分析数据库以寻找 3+ 方式交易的机会,就像棒球队通常如何做的那样。

例如:

想象一下有 100 支球队,每支球队有 20 名左右的球员。每个玩家都有一些可能的属性组合。(比如“跑得快”、“防守好”等)

每支球队都有球员需求(具有来自上述可能集合的特定属性)以及要提供的球员,(每个球员都具有与上述可能选项相匹配的属性)。

这种理论算法可以搜索所有需求和提议,以找到可以相互交易的团队组合。

在一个理论场景中,想象三个团队:

A队有一名速度快的球员,需要一名防守好的球员 F队有一名防守好的球员,需要一名投球好的球员 Q队有一名投球好的球员,需要一名速度好的球员

所以 A、F 和 Q 队可以进行三路交易,每个人都赢。

我的问题是关于可以识别这个机会的算法。这是以前用算法解决过的问题吗?如果是这样,我将不胜感激在哪里看的任何方向。我对如何巧妙地使用缓存和 cron 在数据库中构建它有一些不同的想法。在 Rails 中构建它。只是有点卡在机会寻找算法上。

4

1 回答 1

4

您可以将您的需求和报价建模为图表:每个团队都是一个节点,并且A团队B之间的能力存在优势xiif可以从必须提供的玩家中A获利。您可以在 中构建此图表,其中是报价的数量, 是通过按属性对报价进行分类的需求数量。xBO(o + n)on

现在,您需要在此图中找到一个满足您在问题中未说明的特定属性的循环(可能性是:长度> 3,最大长度,最大容量,...)。对于这些问题中的每一个,您都可以使用现有算法来解决它们(最大流量、最短路径、BFS 等)

于 2012-08-30T00:06:45.797 回答