java - 使用什么算法/方法来采用蛮力方法？

Question

阅读时making unique combinations from the given characters在 SO 上，我想知道这是否是使用 Brute-Force 方法的程序所应用的技术？我的意思是进行 92 次组合来破解用户 ID 或密码。典型的 Windows 键盘有大约 92 个字符可用于密码。

我不是在问如何通过这种方法破解密码，而是想知道一些复杂的程序使用什么方法作为蛮力方法？

Answer 1

使用蛮力解决问题的 Naive 方法确实很简单 backtracking ，探索所有可能性，对其进行评估，然后选择最好的。

但是，对于某些问题 - 您可能拥有比“它解决了”或“它没有解决”更多的信息。例如，对于 SAT问题(查找 boolean 公式是否有解决方案)- 您可以获得有关“您究竟是如何得到矛盾”的知识(哪些变量无法满足分配)。通常我们将此问题称为约束传播。在DPLL下申请SAT经常用于 SAT 求解器的算法(在变体中)。
如果您有兴趣 - 使用 SAT 求解器的现实生活程序是多种多样的，Software verification算法是一个使用 SAT 求解器来证明软件(或更常见的硬件)正在正常工作的示例。

另一个常见的优化是 Branch and Bound - 意思是，你可以在到达树叶之前修剪你的“搜索树”。一个例子是 Traveling Salesman Problem .如果您已经找到了一条长度为 100 的路径，并且您正在探索一条新路径，并达到了 101，则无需继续探索这种可能性。