今天我有一个非常有趣的面试问题。我有一个芯片芯片（比如说黄色）和一系列的芯片提供给两个芯片（一个黄色 - >一个绿色，一个蓝色）。为了达到结果集，我必须做的最少交易次数是多少。获取节点子集的路径
所以我们可以说，我开始用一种颜色A，我需要得到的颜色D, E, F, G，
A
A -> B, C
B -> D, E
C -> F, G
我可以交易A到B，C和贸易这两个得到d，E，F ，G.
我需要什么算法来解决这个问题？从结果集中反向工作是一些东西，但交易可以循环（一个A芯片用于两个A芯片）是非常棘手的。这看起来像一个图形问题。 MST看起来很相似，但它是无向的，在我的情况下，我可以重复交易（非独特的路径）。
简单的逻辑就足够了，不需要程序/算法。
由于每个行业的变化，你有相同的量（这是一个）的芯片数量，你可以划分在一组，并在组大小的变化设定的目标之间的芯片的区别：
chipsIn = 1
chipsOut = 2
changePerTrade = chipsOut - chipsIn
numTrades = (goalSet.size - startSet.size)/changePerTrade
几个注意事项：
需要注意的是这只能是因为限制的，所有的行业都有相同的输入和输出尺寸，并假定每一个芯片必须朝着目标集数下工作（例如如果你试图获得AB，那么拥有ABC是失败的）。
这只会告诉你最少的交易次数（这也只是交易的最大次数），而不是是否有可能实现目标集。
这仅仅是一个树的搜索，在树中探索时在树中生成节点。你的树看起来是这样的（你的例子）：
A
|
B,C
/ \
D,E,C B,F,G
| |
D,E,F,G D,E,F,G
其中芯片的树继续，每一个节点是一组（或列表中，如果允许重复）。一些想法可以帮助解释树的概念：
goalSet.size级别。您从节点A开始，循环遍历所有芯片，并一次执行一次可能的交易，每次执行一个更深的交易。
Here是一篇维基百科文章，解释如何做树遍历，您可以在探索它们时调整它以创建节点。深度优先搜索将是最简单的，因为您一次只需跟踪一个节点，但广度优先搜索可能会更快，但更多的实施困难。