Prolog中的弱规则

Question

写了基本的逻辑解算器(Sudoku等)我试图通过写一个宿舍床分配系统来学习更多现实世界的Prolog.

"必须"规则工作(例如"房间容纳3个人","X必须与Y共用一个房间")但是我遇到了"应该"规则可以被打破的问题(例如"人们应该保持同样的"他们住宿的床 - 但如果需要可以移动房间").

Prolog可以处理逻辑不是二进制的弱规则吗？我遇到了概率编程扩展,但是不认为这是一个概率问题.

如果没有,我应该调查哪些方法/语言？

或者,这是我解决问题的方式,我需要考虑从夜晚到夜晚的连续性,因为客人来往不同的方式？

Answer 1

在文献中,你的"弱规则"通常被称为软约束,而不是必须满足的硬约束.正如评论中已经提到的,软约束通常通过引入成本函数来处理.每个违反的软约束都会对成本函数的总价值产生一定的成本.然后,通过寻找降低/最小化总成本的解决方案,可以找到良好/最佳解决方案.

在Prolog中,您可以通过计算所有解决方案的代码来实现这一点,包括满足和不满足的软约束的所有组合.与每个解决方案一起,您可以计算成本函数的关联值.

这是一个例子.通常情况下,成本函数有几个组成部分.在这种情况下,它由与单个房间相关的成本组成,加上连续房间不相等时的罚款.

solution([Room1,Room2], TotalCost) :-
    Rooms = [a-90, b-50, c-20, d-70],       % Room-Cost data
    member(Room1-Cost1, Rooms),             % select Room1
    member(Room2-Cost2, Rooms),             % select Room2
    prefer_equal(Room1, Room2, Penalty),    % penalty for different rooms
    Room2 \= c,                             % some additional constraint
    TotalCost is Cost1+Cost2+Penalty.       % cost function

prefer_equal(R,  R,   0).                   % no penalty if equal
prefer_equal(R1, R2, 30) :- R1\=R2.         % penalty if not equal

这个谓词提供了12个替代解决方案,成本从100到190.如何最好地从这里获得最佳解决方案的细节在某种程度上取决于您的Prolog系统.在ECLiPSe中,您将执行以下操作:

?- branch_and_bound:minimize(solution(Rooms, Cost), Cost).
Found a solution with cost 180
Found a solution with cost 170
Found a solution with cost 100
Rooms = [b, b]
Cost = 100
Yes (0.00s cpu)

这应该说明一般的想法.不幸的是,当与普通的Prolog一起使用时,这种技术并不是真正可扩展的,因为它可以大大增加搜索空间.因此,它通常与约束求解技术一起使用,如在许多现代Prolog系统中实现的那样.