1

我必须在 python 中编写一个程序来最小化布尔函数，但问题是我必须使用搜索算法，例如 A* 或更简单的算法 BFS 或类似的东西。我用迭代加深写了一个程序，它解决了所有问题，但是速度太慢（每个问题限制为 20 秒）。

所以我用 A* 算法写了另一个程序，（我们被告知如果我们想要更好的成绩，我们必须使用这个），但我设法让它比使用迭代加深的程序慢 10 倍，这是因为我可以没有弄清楚算法的正确启发式。我无法弄清楚有效最小化（良好的启发式）的标准是什么。

问题：

您将获得代表真值表的列表列表 ([[0,1,0,1],[...],[...],[....],...])内部列表表示函数的值）。编写一个程序，仅使用搜索算法（例如 A*、BFS、IDA*、DFS 等）找到布尔函数的最小析取形式。对于每个问题，你有 20 多岁的时间来解决它。

4

1 回答 1

1

我将假设您的状态是有效的合取集合。这是一个简单的可接受的启发式方法。令 U 为映射到 1 的一组函数输入，这些输入与当前状态下的任何合取都不匹配。当 U 不为空时，在 U 中选择一个输入 x。从 U 中删除所有输入 y，使得存在匹配 x 和 y 的有效合取。返回从 U 中选择的元素数。

实际上，这个问题可以看作是集合覆盖的一个实例，这个启发式正在贪婪地构造一个解决 LP 松弛对偶的方法。如果您可以使用 LP 求解器，则可以通过将对偶 LP 求解到最优来获得更高质量（但可能更慢）的启发式算法。

于 2011-11-14T14:53:20.923 回答