我将使用什么算法来确定哪些掉期依赖于另一个掉期?
规则
- 交换可以并行发生,除非存在依赖关系
- 掉期是批量发生的,例如依赖于另一个的交易 必须等到从上一个处理完相关交换 批。
下面是一个示例
- 约翰尼有 100 美元和 5 个苹果
- 蕨类植物有 150 美元和 3 个橙子
- 比尔有 0 美元和 3 个桃子
交换队列
A( 弗恩用 50 美元从约翰尼那里换了 5 个苹果
B( 约翰尼用 140 美元换取 2 个桃子给比尔
C( 弗恩用 10 美元换取 1 个桃子给比尔
实际依赖关系
A -> B
C
一旦我知道了依赖关系,我就可以使用拓扑排序来确定在哪个批次中处理哪个顺序。如何编写代码以自动确定依赖项?
如果平衡在当前状态下足够,则处理交换,如果没有找到需要首先完成的交换。
我相当确定尝试将其组织起来以尽可能少的批次运行将是 NP 完成的。 然而,一个贪婪的解决方案会给出相当好的解决方案,相当容易。
我的意思是,您可以运行所有交换,将具有可用资源运行的交换添加到当前批处理中。 运行这些交换。 对下一批重复此操作。 继续,直到所有交换都用完。