A* 算法的最小化布尔函数启发式
我必须用 python 编写一个程序来最小化布尔函数，但问题是我必须使用搜索算法，例如 A* 或更简单的算法 BFS 或类似的算法。我用迭代深化写了一个程序，它解决了所有问题，但是太慢了（每个问题限制为20秒）。
所以我使用 A* 算法编写了另一个程序（我们被告知，如果我们想要更好的成绩，我们必须使用这个），但我设法让它比使用迭代加深的程序慢 10 倍，这是因为我可以没有找出正确的算法启发式。我无法弄清楚有效最小化的标准是什么（良好的启发式）。
问题：
给出了表示真值表（最后一个）的列表列表（[[0,1,0,1],[...],[...],[....],...]）内部列表中的元素代表函数的值）。编写一个程序，仅使用搜索算法（例如 A*、BFS、IDA*、DFS 等）查找布尔函数的最小析取形式。对于每个问题，你有 20 秒的时间来解决。
I have to write a program in python which minimizes a boolean function, but the catch is that I have to use search algorithms for example A* or simpler algorithm BFS or something like that. I wrote a program using Iterative deepening, it solves every problem, but it is too slow (limit is 20s for each problem).
So I wrote another program using A* algorithm, (we were told that if we want better grade we have to use this one), but I managed to make it 10-times slower than the one using Iterative deepening and this is because I can't figure out right heuristics for algorithm. I can't figure out what would be criteria for effective minimizing (good heuristics).
PROBLEM:
You are given list of lists ([[0,1,0,1],[...],[...],[....],...]) representing the truth table (last element in inner list represent value of the function). Write a program that finds a minimal disjunctive form of boolean function using only search algorithms (example A*, BFS, IDA*, DFS, ..). For each problem you have 20s to solve it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我假设你的状态是有效的合取集。这是一个简单的可接受的启发式。令 U 为映射到 1 的函数输入集合，这些输入与当前状态下的任何合取都不匹配。当 U 不为空时，在 U 中选择一个输入 x。从 U 中删除所有输入 y，以便存在匹配 x 和 y 的有效合取。返回从U中选出的元素个数。
实际上，这个问题可以看作是设置覆盖，并且这种启发式正在贪婪地构建 LP 松弛对偶的解决方案。如果您可以使用 LP 求解器，则可以通过求解对偶 LP 至最优性来获得更高质量（但可能更慢）的启发式方法。
I'm going to assume that your states are valid sets of conjuncts. Here's a simple admissible heuristic. Let U be the set of function inputs mapping to 1 that are not matched by any of the conjuncts in the current state. While U is not empty, choose an input x in U. Delete from U all inputs y such that there exists a valid conjunct matching x and y. Return the number of elements chosen from U.
Actually, this problem can be viewed as an instance of set cover, and this heuristic is greedily constructing a solution to the dual of the LP relaxation. If you have access to an LP solver, you can get a higher-quality (but possibly slower) heuristic by solving the dual LP to optimality.