如何防止 Prolog 在不应该回溯的地方回溯 [英] How to prevent Prolog from backtracking where it shouldn't

问题描述

我正在尝试解决一个 CSP，我需要将鸡尾酒分发给调酒师，以便每个调酒师最多有一种鸡尾酒，并且所有鸡尾酒都有一个调酒师.我通过创建一个 clpfd 变量列表解决了这个问题，首先给他们所有调酒师的完整域，然后删除所有不知道如何制作鸡尾酒的调酒师.
我的代码有效，但有一个问题:它太慢了.如果我查看探查器，remove_domain 会被调用 2000 次(对于我给我的程序的输入)，而它的重做统计数据 >100 000.我需要在这些函数之一(或两者)中进行哪些更改，以便 prolog 不需要回溯?

I'm trying to solve a CSP where I need to distribute cocktails over bartenders so that each bartender has at most one cocktail and all cocktails are given a bartender. I solved it by creating a list of clpfd variables,first giving them the full domain of all bartenders and then removing all bartenders that don't know how to make that cocktail.
My code works, but there is one problem: it's too slow. If I look in the profiler, remove_domain gets called 2000 times(for the input I'm giving my program), while it's Redo statistic is >100 000. What do I need to change in one of these functions(or both) so that prolog doesn't need to backtrack?

produce_domains(_,_,[],[]) :- !.
produce_domains(Bartenders,NBartenders,[Cocktail|Cocktails],[Var|Vars]) :-
    Var in 1..NBartenders,
    remove_domain(Bartenders,NBartenders,Cocktail,Var),!,
    produce_domains(Bartenders,NBartenders,Cocktails,Vars),!.

remove_domain([],0,_,_) :- !.
remove_domain([Bartender|Bartenders],NBartenders,Cocktail,Var) :-
    (\+ member(Cocktail,Bartender) -> Var #\= NBartenders;!),!,
    NNBartenders is NBartenders - 1,
    remove_domain(Bartenders,NNBartenders,Cocktail,Var),!.

我已经阅读了这个相关问题，但我使用的是最新的 Windows 版本的 SWI-Prolog(5.10.5)，所以这不应该是这里的问题.

I have already read this related question, but I am using the latest Windows build of SWI-Prolog(5.10.5), so that shouldn't be the problem here.

推荐答案

你不需要那么多 !/0:Prolog 经常可以判断你的谓词是确定性的.

You do not need so many !/0: Prolog can often tell that your predicates are deterministic.

首先让我提供您的代码的以下版本.它使用更相关的名称，不包含 !/0 并使用高阶谓词来缩短代码.

Let me first offer the following version of your code. It uses names that are more relational, contains no !/0 and uses higher-order predicates to make the code shorter.

:- use_module(library(clpfd)).

bartenders_cocktails_variables(Bs, Cs, Vs) :-
        length(Bs, LBs),
        maplist(bartenders_cocktail_variable(Bs, LBs), Cs, Vs).

bartenders_cocktail_variable(Bs, N, C, V) :-
        V in 1..N,
        foldl(compatible_bartender(C,V), Bs, 1, _).

compatible_bartender(C, V, Cs, N0, N1) :-
        (   member(C, Cs) -> true
        ;   V #\= N0
        ),
        N1 #= N0 + 1.

请注意，我是向上计数而不是向下计数来列举调酒师(这只是他们能够混合的鸡尾酒清单)，因为这看起来更自然.我还可以通过简单地切换 if-then-else 的分支来省略 (\+)/1.

Notice that I am counting upwards instead of downwards to enumerate the bartenders (which are just lists of cocktails they are able to mix), since this seems more natural. I was also able to omit a (\+)/1 by simply switching the branches of the if-then-else.

示例查询，显示该用例中的谓词是确定性的:

Example query, showing that the predicate is deterministic in this use case:

?- bartenders_cocktails_variables([[a,b],[a,b],[x,y]], [x,a,b], Vars).
Vars = [3, _G1098, _G1101],
_G1098 in 1..2,
_G1101 in 1..2.

我们看到:鸡尾酒x必须由第三个调酒师等混合.

We see: Cocktail x must be mixed by the third bartender etc.

我认为您程序的这一部分可能不对您所描述的缓慢性能负责.也许您的程序的其他部分(无意中)不是确定性的?也许尝试不同的标签策略或其他限制?如果您发布更多背景信息，我们可能会为您提供更多帮助.

I think this part of your program may not be responsible for the slow performance you are describing. Maybe other parts of your program are (unintentionally) not deterministic? Maybe try different labeling strategies or other constraints? We may be able to help you more if you post more context.

这篇关于如何防止 Prolog 在不应该回溯的地方回溯的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！