4

我正在使用 CHR（约束处理规则）在 Prolog SWI 中创建几个解谜器

一切都很好，但是，我喜欢测试哪个求解器是最好的。因此，我想找出哪个求解器使用的回溯量最少。

有没有一种聪明的方法来找出（或打印出）求解器解决特定难题所需的回溯量？

从逻辑上讲，计数会有所帮助，但它没有 --> 回溯！<-- 。此外，由于 SWI 的 GUI，在屏幕上打印新行无效。您不能打印超过 +/- 50 行并且不能正确选择

4

1 回答 1

2

鉴于约束处理规则维护一个“约束存储”并且规则的执行可能会在运行时从该存储中添加、重写或删除规则，因此实现这一点确实不是微不足道的。这改变了程序的状态，并使得在整个执行过程中跟踪全局状态变得有些困难。

但是，由于 CHR 集成在 SWI 中，因此您可以使用非逻辑操作nb_setarg/3来保持回溯计数。

来自文档的注释：

  • 兼容 GNU-Prolog 的 setarg(A,T,V,false)

  • 这个实现是线程安全的、可重入的并且能够处理异常

编辑

至于在哪里计算回溯，这当然取决于您的程序，但通常会出现在定义搜索失败条件的 CHR 约束规则中，允许它“分支”（=重写 CHR 规则）。每次在搜索期间重写约束存储时，它都表示回溯，您可以使用上面定义的操作相应地增加计数器。

考虑一个小而抽象的例子：

invalid_state ==> increment_backtracks, fail.
        guess <=> branch
于 2016-03-20T08:37:43.143 回答