最小功耗算法

Question

您将看到一个逻辑电路，它可以建模为一个有根的树--叶子是主输入，内部节点是门，根是电路的单一输出。每个栅极可以由高或低的电源电压供电。由较低的电源电压供电的门消耗较少的功率，但具有较弱的输出信号。您希望在确保电路可靠的同时将功耗降至最低。为了确保可靠性，您不应该让一个由低电源电压供电的门驱动另一个由低电源电压供电的门。当连接到低电源电压时，所有栅极消耗1纳瓦，当连接到高电源电压时，所有栅极消耗2纳瓦。

设计一种高效的算法，将逻辑电路作为输入，并为每个门选择电源电压，以最大限度地减少功耗，同时确保可靠的运行。

在这个问题中，我认为它可以通过贪婪或动态来解决。但我感到困惑，我从哪里开始思考这个问题。请帮帮忙。

Answer 1

从“你不应该让一个由低电源电压供电的门驱动另一个由低电源电压供电的门”的要求中，我们得到的任务是在树中找到一个最大的独立集(可能减去树叶，我不知道它们是否被认为是供电的)。

这个问题对于一般图来说是NP难的，而对于树来说可以快速有效地解决。您可以阅读此simple 3-page article以了解详细信息。

Answer 2

你需要找到树的最大独立集，而属于独立集的点具有较低的电源电压。除了动态编程，还有一个非常简单的线性贪婪算法：

1. 选择所有的叶子(不被其他门驱动的门) as low voltage.
2. Delete所有的叶子和它们的直接父。现在
3. 一些内部节点成为新的叶子。重复到1，直到处理完所有节点。