无否定地找到产品布尔和的所有解决方案的算法

Question

我正在开发一款益智游戏，其中每个级别都可以通过一系列动作来完成。有八个不同的动作标记为 a-h。我已经开发了一个解决函数，可以通过一个级别 L 和一组可用的移动 S，它会 return 是否可以仅使用 S 的移动来解决该级别。

例如，如果我调用 solve(L, {a,b})，那么该函数可能会发现一系列移动 aaabbaaba 解决了难题，因此它 returns True.

我有兴趣编写一种算法来查找足以解决关卡的所有可用动作集。由于有八种不同的着法，所以有 2⁸ = 256 种可能的着法。我可以检查所有这些，但这似乎很浪费。求解器相对较慢，因此目标是使用逻辑来减少我需要 运行 求解器的次数。

如果仅移动 c 足以解决一个级别（即 solve(L, {c}) == True），那么该级别也可以同时使用移动 c 和 d（其中移动 d 可用但不必要）来解决。同样，如果除了 c（即 solve(L, {a,b,d,e,f,g,h}) == False）之外的每一步都无法解决某个关卡，那么除了 c 和 d 之外，该关卡也将仍然无法解决。

更一般地说：

• 如果solve(L, S) == True和S⊆T，则solve(L, T) == True
• 如果solve(L, S) == False和T⊆S，则solve(L, T) == False

我相信这意味着级别可以表示为乘积之和而不需要取反。例如，一级可以表示为a ∨ c∧d∧e ∨ d∧e∧f。 （在这种情况下，关卡可以用集合 {a}、{c,d,e}、{d,e,f} 以及这些集合的任何超集求解。）

我怀疑一个好的算法可能会从检查只包含一个动作的集合和只包含一个动作的集合开始，这样大量的可能性就可以被 p运行ed。我试图想出一个递归算法，但我无法合并这两种类型的 p运行ing.

Answer 1

给定 n 个不同的移动，即使是最好的算法也需要 运行 求解器非常接近 O(2ⁿ )次在最坏的情况下，这几乎不比蛮力好多少。

考虑具有八个不同移动和可以通过四个移动的任意组合解决的关卡的情况。这些动作组看起来像 {a,b,c,d}, {a,b,c,e} 等。有 8 选择 4 = 70 组四个动作从八个选项中选出。 None 这些集合是彼此的子集，因此此级别的最简单的乘积求和表达式将包含 70 个项。

考虑一个已经提供的算法，所有 56 组三步棋都没有提供这个级别的解决方案。该算法仍然至少需要检查所有 70 组四次移动以验证每组是否足够。

概括这个最坏情况级别，给定 n 个不同的移动，算法需要 运行 求解器至少 n 选择 ⁿ/₂次。对于大 n,

source

因此，不存在在所有情况下都表现良好的高效算法。正如 j_random_hacker and kcsquared 推测的那样，最佳策略必然取决于关卡总体的特征和求解器的算法复杂性。