Prolog中如何仅在条件A不满足时检查条件B？附优化问题求解困境

问题描述 #

我用Prolog求解一个车辆分配优化问题，规则如下：

• 只有当人的能力值≥车辆难度值时，该人才可驾驶对应车辆
• 优先给每个人分配其心愿单（favcar）中的车辆；若心愿单无法满足（如心愿车被他人占用、无驾驶权限），再分配其他可驾驶的车辆

我尝试用*->运算符结合g1、g2条件实现逻辑，但脚本仅会检查g1（心愿单可驾车），当g1不满足时直接返回false，无法处理心愿单冲突或无法满足的场景。例如原代码中a和b都心愿车1，程序会因冲突直接失败，而我需要覆盖这类场景。

原代码 #

car(1).
car(2).
car(3).
person(a).
person(b).
person(c).
favcar(a, [1]).
favcar(b, [1]).
favcar(c, [1,2]).
ability(a,0).
ability(b,1).
ability(c,2).
diff(1,0).
diff(3,0).
diff(2,1).
candrive(X,Y) :- ability(X,H1),diff(Y,H2),person(X),car(Y),H1>=H2.
wants(X,Y) :- favcar(X, L), member(Y,L), person(X),car(Y).
g1(X,Y) :- person(X),car(Y),candrive(X,Y),wants(X,Y).
g2(X,Y) :- person(X),car(Y),candrive(X,Y).
gen(X,Y) :- g1(X,Y) *-> g1(X,Y); g2(X,Y).
unique([]).
unique([X|Xs]) :- 
    \+ memberchk(X, Xs),
    unique(Xs).
solve(C1,C2,C3) :- gen(a,C1),gen(b,C2),gen(c,C3),unique([C1,C2,C3]).

问题根源 #

*->是Prolog的确定性选择运算符，它的逻辑是：如果左边子句成功匹配，就直接返回结果，不会回溯尝试右边的子句；如果左边失败，才会执行右边。但在分配逻辑中，当某个人的心愿车被他人占用时，需要回溯调整前面人的分配，而*->的确定性会阻断这种回溯，导致直接返回失败。

修改方案 #

要实现「优先心愿单，但允许回溯调整」的逻辑，不能用确定性选择，而是利用Prolog子句的尝试优先级：先定义心愿单分配的子句，再定义非心愿单分配的子句，Prolog会优先尝试前面的子句，只有当前面子句无解时，才会尝试后面的。

修改后的完整代码 #

car(1).
car(2).
car(3).
person(a).
person(b).
person(c).
favcar(a, [1]).
favcar(b, [1]).
favcar(c, [1,2]).
ability(a,0).
ability(b,1).
ability(c,2).
diff(1,0).
diff(3,0).
diff(2,1).

% 判定是否可驾驶车辆
candrive(X,Y) :- 
    person(X), car(Y),
    ability(X,H1), diff(Y,H2),
    H1 >= H2.

% 判定是否在心愿单中
wants(X,Y) :- 
    person(X), car(Y),
    favcar(X, L), member(Y, L).

% 优先分配心愿单中的可驾驶车辆
gen(X,Y) :- candrive(X,Y), wants(X,Y).
% 心愿单无法满足时，分配其他可驾驶车辆
gen(X,Y) :- candrive(X,Y), \+ wants(X,Y).

% 检查车辆分配是否唯一
unique([]).
unique([X|Xs]) :- 
    \+ memberchk(X, Xs),
    unique(Xs).

% 求解分配方案
solve(C1,C2,C3) :- 
    gen(a,C1), gen(b,C2), gen(c,C3),
    unique([C1,C2,C3]).

效果说明 #

修改后，程序会优先尝试给每个人分配心愿车，当出现冲突时会自动回溯调整，生成所有符合规则的最优分配方案。例如：

• a分配车1，b分配车3，c分配车2
• b分配车1，a分配车3，c分配车2

这两种方案都满足「优先心愿单」的规则，同时保证车辆不重复、所有人都有可驾车。

内容的提问来源于stack exchange，提问作者luanpo1234