java - 约束满足问题实现的回溯搜索

Question

对于家庭作业，我的目标是使用最小剩余值、启发式度数和前向检查进行回溯搜索。需要解决一个 boolean 可满足性问题，该问题由 3 个 boolean 变量的集合组成，并且每个变量集合的计算结果都必须为真。按照我目前的实现情况，我相信它最终会解决它，但它需要很长时间才能完成，以至于我最终遇到了 Java 堆内存不足错误。

除此之外，我的实现如下:

• 有每个约束的arrayList
• 一个值数组，索引是每个变量的值，这些变量要么是真，要么是假，要么还没有给定一个值，最初都没有给定一个值。第 0 个元素用作标志。
• 每个变量域的数组:true 或 false，只有 true，只有 false 或没有可能的值，最初是 true 或 false
• 数组的arrayList，每个数组都是一个值列表；用于避免尝试两次相同的事情
• 变量在约束中的次数数组:这是启发式度数

反向搜索返回一个值数组，并接受一个值数组和一个域数组

首先检查列表中的每个约束，以确保每个变量的域都有效以使其为真。如果它们都不起作用，则设置第 0 个标志并退出。此外，如果 2 个变量的域使得第三个变量必须为真才能使语句生效，则更改该变量的域。

通过该步骤后，它会检查 vals 数组中的每个变量是否都有分配的值，并在成功时结束程序。

接下来它创建一个临时数组来跟踪它尝试过的值，然后开始一个循环。在内部，它添加每个具有找到的最小域 (MRV) 的域并且没有值/尚未尝试的变量，将其添加到列表中，如果找不到则退出递归。然后它根据度数启发式数组从变量中选择出现次数最多的变量。在平局时，它会选择出现在平局中的最后一个，并设置一个标志，这样我们就不会在同一个递归中再次尝试该变量。

仍在循环内，它首先尝试将该变量的域和值设置为 true(如果域不仅为 false)，否则为 false。它检查变量的值组合之前是否已经完成，如果已经完成，则重新选择。如果没有，它会将该值组合添加到列表中并执行递归步骤。如果该递归步骤返回一个停止标志，则将值换回它们的域和所选变量的值，然后再次尝试，这次使域和值为假，但首先将其添加到已尝试组合的列表中，重新选择它是否已经存在，并重置所有还没有值的变量的域，然后执行递归步骤。如果同样失败，则重置变量选择域和值的值，并尝试在同一循环中选择不同的变量。一旦完成或所有组合都失败，循环就会中断，然后返回值数组。

我可以说它不会 self 重复，但我不知道如何修复/加速我的实现，以便它在合理的时间运行。

Answer 1

第一步是为领域创建知识模型。这可以使用领域特定语言 (DSL) 来完成。在 DSL 语法中，制定了该问题的可能解决方案。领域特定语言的副作用是，必须创建可以解析该语言的语法。这种语法可以以相反的顺序使用，称为“生成语法”。目的是在 DSL 中包含尽可能多的领域知识，使求解器更容易测试所有状态。

不幸的是，这个问题只有一些关于域本身的信息。根据描述，可以打开或关闭三个变量。这将生成 2x2x2=8 的可能状态空间，这对于域来说似乎有点太简单了，因为如果他测试了所有 8 个状态，求解器就完成了。所以我猜，这个问题有点难，但在描述中没有解释。然而，第一步是将问题转化为可以用文法解析的语言。