prolog - 逻辑编程: how to distribute resources among consumers?

Question

我有一项任务，必须在消费者之间分配独特的资源。规则是:

• 每个使用者都有一组可以使用的资源类型，
• 每种资源都是独一无二的，
• 每个消费者必须接收n>0个资源，
• 所有资源都必须分配。

E. G。我们有这份消费者名单及其偏好:

• A:{X，W}
• B:{X，Y，V}
• C:{X，Z}
• D:{Z}

我们有一个资源列表:[X、W、Y、V、Z]。

如果我们通过迭代消费者列表并为他们提供集合中的第一个可用资源来分配资源，我们会在 D 上失败，因为唯一的 Z 已分配给 C。更好的解决方案是:A(W )、B(Y、V)、C(X)、D(Z)。

对我来说看起来像是一个逻辑编程问题!虽然编写一个为这种特殊情况提供解决方案的 Prolog 程序很简单，但我想要的是一个可以解决任何此类问题的通用程序，或者告诉我给定数据不存在解决方案。

我应该去哪里寻找，我应该用谷歌搜索什么，这个问题有名字吗？

Answer 1

这是无数种资源分配任务的示例，逻辑编程确实非常适合并且经常使用。相关任务在文献中被称为运输和分配问题，尽管这个表述的细节有所不同。将此 Prolog 表述视为解决此类任务的工作起点:

distribution([], [], []).
distribution([C-Ps|CPs], Rs0, [C-As|CAs]) :-
        allocation(Ps, As, Rs0, Rs1),
        As = [_|_],
        distribution(CPs, Rs1, CAs).

allocation(_, [], Rs, Rs).
allocation(Ps0, [A|As], Rs0, Rs) :-
        select(A, Ps0, Ps1),
        select(A, Rs0, Rs1),
        allocation(Ps1, As, Rs1, Rs).

distribution/3 期望将 Consumer-Preferences 形式的成对列表作为其第一个参数，并将资源列表作为其第二个参数。它将实例描述与消费者分配的资源对形式的解决方案联系起来。使用 SWI-Prolog 查询您指定的具体任务的示例:

?- distribution([a-[x,w],b-[x,y,v],c-[x,z],d-[z]], [x,w,y,v,z], Ds).
Ds = [a-[w], b-[y, v], c-[x], d-[z]] ;
Ds = [a-[w], b-[v, y], c-[x], d-[z]] ;
false.

您可以使用此公式来完成此类的所有任务。公式是完整的:它报告了所有存在的解决方案(有些是多余的，因为分配的资源可以按任何顺序陈述，正如您在上面的示例中已经看到的那样；您可以在allocation/4 以避免这种情况 - 解决此问题的一种方法是坚持 As 相对于标准术语顺序升序)，因此没有(进一步)如果回答false，则解决方案。