1

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

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

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

4

2 回答 2

1

从“你不应该让一个由低电源电压供电的门驱动另一个由低电源电压供电的门”的要求，我们知道我们的任务是在树中找到一个最大的独立集（也许减去叶子，我不知道） '不知道他们是否被认为是有动力的）。

虽然这个问题对于一般图来说是 NP-hard，但对于树来说，它可以快速有效地解决。您可以阅读这篇简单的 3 页文章了解详细信息。

于 2012-08-26T08:08:23.687 回答
0

You need to find a maximum independent set of the tree, while the points belong to the independent set have low supply voltage. Besides dynamic programming, there is a very simple linear greedy algorithm:

  1. Choosing all the leaves (the gates which are not drove by other gates) as low voltage.
  2. Delete all the leaves and their direct fathers.
  3. Now some internal nodes become the new leaves. Repeat to 1 until all the nodes are processed.
于 2012-08-26T14:15:38.657 回答