Prolog 中的弱规则 [英] Weak rules in Prolog

问题描述

已经编写了基本的逻辑求解器(Sudoku 等人)，我正在尝试通过编写宿舍床位分配系统来学习更多真实世界的 Prolog.

Having written basic logic solvers (Sudoku et al) I'm trying to learn more real-world Prolog by writing a hostel bed allocation system.

必须"规则有效(例如房间可容纳 3 人"、X 必须与 Y 共用一个房间")但我遇到了可以打破的应该"规则(例如人们应该留下来")入住时在同一张床上 - 但如果需要，可以移动房间").

The "Must" rules work (e.g. "The room holds 3 people", "X must share a room with Y") but I am having a problem with "Should" rules that can be broken (e.g. "People should stay in the same bed for their stay - but can move rooms if needed").

Prolog 能否处理逻辑不是二进制的弱规则?我遇到过概率编程扩展，但不要将其视为概率问题.

Can Prolog handle weak rules where the logic isn't binary? I've come across probabilistic programming extensions, but don't see this as a probabilistic problem.

如果不是，我应该研究哪些方法/语言?

If not, what approaches/languages should I investigate instead?

或者，这是我构建问题的方式吗，我需要考虑随着客人以不同的方式来来去去而从夜到夜的连续性?

Alternatively, is it the way I've framed the problem, and I need to think about continuity from night to night as guests come and go a different way?

推荐答案

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

In the literature, your "weak rules" are usually called soft constraints, as opposed to hard constraints which must be satisfied. As already mentioned in the comments, soft constraints are often handled by introducing a cost function. Every violated soft constraint contributes a certain cost to the total value of the cost function. A good/optimal solution can then be found by looking for a solution that reduces/minimizes the total cost.

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

In Prolog, you can implement this via code that computes all solutions, including all combinations of satisfied and unsatisfied soft constraints. Along with each solution, you compute the associated value of the cost function.

这是一个例子.在实践中经常出现这种情况，成本函数有几个组成部分.在这种情况下，它由与单个房间相关的成本以及连续房间不相等时的罚金组成.

Here is an example. As is often the case in practice, the cost function has several components. In this case, it is made up of costs associated with the individual rooms, plus a penalty when consecutive rooms are not equal.

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 中，您将执行以下操作:

This predicate gives 12 alternative solutions with costs ranging from 100 to 190. The details of how to best get from here to an optimal solution is somewhat dependent on your Prolog system. In ECLiPSe you would do the following:

?- 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 系统中实现的那样.

This should illustrate the general idea. Unfortunately, this technique isn't really scalable when used with plain Prolog, because it can dramatically increase the search space. It is therefore usually employed together with constraint solving techniques, as implemented in a number of modern Prolog systems.

这篇关于Prolog 中的弱规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！