1

假设我在 Prolog 中有一个简单的程序，它正在搜索某个状态空间：

search(State, State) :-
    is_solution(State).

search(State, Solution) :-
    generate(State, NewState),
    search(NewState, Solution).

我知道：

  • generate(State, NewState)NewState正在为任何给定的生产至少一个State
  • 整个状态空间是有限的

我想修改search谓词以确保它始终能够在有限时间内进行检查。所以我写了类似的东西：

search(State, Solution) :-
    empty_memory(EmptyMem),
    add(State, EmptyMem, Memory),
    search(State, Memory, Solution).

search(State, _, State) :-
    is_solution(State).

search(State, Memory, Solution) :-
    generate(State, NewState),
    \+ exist(NewState, Memory),
    add(NewState, Memory, NewMemory),
    search(NewState, NewMemory, Solution).

这是有效的，但它在回溯期间丢失了计算状态，所以现在我有一个空间大小最大高度的搜索树。

有没有办法在回溯期间传播状态而不会丢失任何计算信息？我想要一个带有 O(space_size) 节点的整个搜索树。可能吗？

编辑： 似乎我应该使用它assert/[1,2]来动态创建将用作全局内存的新子句。

4

3 回答 3

1

在 SICStus Prolog 中，您可以使用黑板跨回溯存储信息：请参阅手册中的Blackboard Primitives。用于bb_put(Key, Value)在黑板上存储一些东西，也bb_get(Key, Value)可以用来取回它。请注意，黑板是按模块定义的。

于 2012-05-21T06:15:38.667 回答
1

最干净的解决方案可能是使用支持 B-Prolog、Ciao、XSB 或 YAP 等表的 Prolog 编译器。在这种情况下，您只需将 generate/2 谓词声明为表格。

于 2012-05-21T20:56:47.287 回答
1

assert为什么不使用生成所有可能的状态，而不是使用findall(N, generate(S,N),ALL)。这将消除对回溯的需要，并将解释搜索空间树，然后可以在将访问过的状态作为附加参数传递的同时进行前序遍历。

于 2012-05-25T07:01:35.153 回答