prolog - 代码速度问题

Question

我有一个解决方案的问题，它很快就会变得很慢。

下面的代码确定一组“规则”是否有效——示例可以是

rules_valid([rule(2,[1,2,3]), rule(2,[1,2,3])],[]) 

这应该是错误的，因为不可能从列表中选择 4 (2+2) 个不同的数字，并且

rules_valid([rule(2,[1,2,3]), rule(2,[3,4,5])],[]) 

因此是真的。

对于非常小的查询，这执行得很好，但很快就会变慢。如果可能的话，任何人都可以指出如何加速此代码的方向。

rules_valid([], _).
rules_valid( [ rule(RequiredUserNumber, UserIds) | RemainingRules ], UsedUserIds) :-
    n_users_from_rule(RequiredUserNumber, UserIds, UsedUserIds, UpdatedUsedUserIds),
    rules_valid(RemainingRules, UpdatedUsedUserIds).

n_users_from_rule(0, _, UsedUserIds, UsedUserIds).
n_users_from_rule(RequiredUserNumber, UserIds, UsedUserIds, UpdatedUsedUserIds) :-
    0 < RequiredUserNumber,
    UpdatedRequiredUserNumber is RequiredUserNumber - 1,
    select(UserId, UserIds, UpdatedUserIds),
    not(member(UserId, UsedUserIds)),
    n_users_from_rule(UpdatedRequiredUserNumber, UpdatedUserIds, [ UserId | UsedUserIds ] , UpdatedUsedUserIds ).

---

更新

因此，为这部分逻辑切换到 CLPFD 会使该部分更快。但是，我似乎无法全神贯注于如何让我的应用程序的其余部分也使用 CLPFD，以便它适用于整个应用程序。

我有一个用户请求列表:

userRequest(UserId, PrioritizedRequestList) 
request(State, PeriodList)
period(FromDay, ToDay)
i.e.
userRequest( 1 , [request(State,[period(1,5)]),request(State,[period(1,2),period(1,5)])] )

然后我有一个规则组列表，它是我的问题的结构，包裹在

ruleGroup(Day, [rules])

因此，我要做的是将 userRequest 的状态更改为已批准，即我接受第一个请求并批准它，因此从与请求重叠的日期的所有规则组中删除 userId，因为该用户不再能够完成那天的规则。

我很难理解如何更新这些域以从中删除用户。

问题是我一直在处理列表而不是域，并且围绕它们有很多逻辑我也必须更改。

Answer 1

检查 CLP(FD) 约束。许多 Prolog 系统，包括 SICStus Prolog 和 SWI，都带有一个名为 all_distinct/1 的强大约束:这是真的 iff 给定列表中的所有变量都可以赋值 不同的整数。

例如，让我们用 CLP(FD) 陈述您的第一个查询:

?- length(Ls, 4), Ls ins 1..3, all_distinct(Ls).false.

由此，我们看到没有可接受的解决方案。

但是在第二种情况下，我们得到:

?- length(Ls, 4), Ls ins 1..5, all_distinct(Ls).Ls = [_G3409, _G3412, _G3415, _G3418],_G3409 in 1..5,all_distinct([_G3409, _G3412, _G3415, _G3418]),_G3412 in 1..5,_G3415 in 1..5,_G3418 in 1..5.

即，一个在声明上等同于原始查询的残差程序，在这种特殊情况下，我们从中知道确实有一个解决方案。 (注意:这是可能的，因为 all_distinct/1 实现了域一致性。)

因此，在您的规则验证中，您可以编写使用 CLP(FD) 约束来检测不一致的代码，这通常比单纯的方法更有效。我把实现这个翻译作为一个简单的练习。