代码之家 › 专栏 › 技术社区 › Germán Faller

prolog跳过一些回溯分支

prolog

1

Germán Faller · 技术社区 · 8 年前

我试着创造一些卡库罗,创造而不是解决。

我有所有的规则来产生它,但最初的结果是毫无意义的,那些像正方形。

现在我想跳过一些分支,比如15000,看看在那个点上生成的kakuro。

我试过使用一个辅助变量,但是当它失败时,kakuro生成器再次启动。

1 回复 | 直到 8 年前

1

Marijn 8 年前

可以在知识库中保留动态计数器类谓词,每次执行主谓词时都会增加该谓词。计数器的值更改为 assert 和 retract 也就是说,它不是主谓词中的变量,而是全局存储的值。

在主谓词中,如果添加了计数器应高于某个跳过值的条件,则强制对指定迭代次数的实际规则进行回溯。

例如,考虑内置谓词 permutation/2 它计算列表的排列(注意:使用swi prolog测试,其他解释器有不同的内置谓词)。示例输出:

?- permutation([1,2,3,4,5],L).
L = [1, 2, 3, 4, 5] ;
L = [1, 2, 3, 5, 4] ;
L = [1, 2, 4, 3, 5] ;
L = [1, 2, 4, 5, 3] ;
L = [1, 2, 5, 3, 4] ;
L = [1, 2, 5, 4, 3] ;

如果希望跳过查询中的前5个迭代,可以使用以下代码:

:- dynamic iteration_nr/1.

iteration_nr(0).

get_permutations(L1,L2,Skip) :-
    permutation(L1,L2),
    iteration_nr(N),
    N2 is N+1,
    retract(iteration_nr(N)),
    asserta(iteration_nr(N2)),
    Skip < N2.     % force backtracking here if counter < Skip

示例输出:

?- get_permutations([1,2,3,4,5],L2,5).
L2 = [1, 2, 5, 4, 3] ;
L2 = [1, 3, 2, 4, 5] ;
L2 = [1, 3, 2, 5, 4]

注意 asserta 在这里使用(即,在开始时断言)而不是普通的 断言 ,已弃用。还要注意,计数器将保留该值,因此在同一会话中再次运行该值时,结果将不同。若要重置计数器,可以使用单独的初始化谓词,例如:

init_and_get_permutations(L1,L2,Skip) :-
    retractall(iteration_nr(_)),
    asserta(iteration_nr(0)),
    get_permutations(L1,L2,Skip).

进一步说明:使用 断言 和 收回 并不是真正意义上的“干净”prolog编程,因为它是过程性的,改变了知识库。然而,对于某些应用,它可能是有用的。