algorithm - 最小化 A* 算法的 bool 函数启发式

Question

我必须用 python 编写一个程序来最小化 bool 函数，但要注意的是我必须使用搜索算法，例如 A* 或更简单的算法 BFS 或类似的算法。我用 Iterative deepening 写了一个程序，它解决了所有问题，但是太慢了(每个问题限制为 20s)。

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

问题:

给定列表列表 ([[0,1,0,1],[...],[...],[....],...]) 表示真值表 (内部列表中的最后一个元素表示函数的值)。编写一个程序，仅使用搜索算法(例如 A*、BFS、IDA*、DFS 等)找到 bool 函数的最小析取形式。对于每个问题，您有 20 秒的时间来解决它。

Answer 1

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

其实这个问题可以看成set cover的一个实例，并且这种启发式正在贪婪地构造 LP 松弛对偶的解决方案。如果您可以访问 LP 求解器，则可以通过将对偶 LP 求解到最优来获得更高质量(但可能更慢)的启发式。