4

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

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

例如。我们有这个消费者列表和他们的偏好：

  • 答：{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 程序是微不足道的，但我想要的是一个可以解决任何此类问题的通用程序，或者告诉我不存在给定数据的解决方案。

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

4

1 回答 1

4

这是一个无穷无尽的资源分配任务的例子，逻辑编程确实非常适合并经常使用。相关任务在文献中被称为运输和分配问题，尽管这个公式中的细节有所不同。将此 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第二个参数是一个资源列表。它以对的形式将此实例描述与解决方案联系起来Consumer-Allocated resources。使用 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。

于 2013-10-05T11:55:48.883 回答