确定依赖关系的算法

问题描述 投票:0回答:1

我将使用什么算法来确定哪些交换依赖于另一个交换?

规则

  1. 除非存在依赖关系,否则交换可以并行发生
  2. 交换分批发生,例如。依赖于另一个的交易必须等到依赖交换从前一批处理完毕。

这是一个例子

  • 约翰尼有100美元,还有5个苹果
  • Fern有150美元和3个橙子
  • 比尔有0美元和3个桃子

互换队列

A)Fern为Johnny的5个苹果交易50美元

B)约翰尼向比尔交易了价值140美元的2个桃子

C)Fern以1美元的价格向Bill交易10美元

实际的依赖关系

A - > B.

C

一旦我知道依赖关系,我就可以使用拓扑排序来确定在哪个批处理中处理哪个订单。我如何编写代码来自动确定依赖关系?

如果在当前状态下平衡充足,则进行交换,如果没有找到首先需要完成的交换。

algorithm sorting
1个回答
1
投票

我很确定尝试组织这个以尽可能少的批次运行将是NP完全的。然而,贪婪的解决方案将提供相当好的解决方案,相当容易。

我的意思是,您可以遍历所有交换,将其添加到当前批处理中,以便运行可用资源。运行这些交换。重复下一批。继续,直到所有掉期用完为止。

© www.soinside.com 2019 - 2024. All rights reserved.