3

我正在尝试在 prolog 中使用 clp 解决问题。问题如下：

基本上，一艘船载有许多集装箱，我们想卸下它们。集装箱被描述为谓词 container(I,N,D)，其中 I 是集装箱标识符，N 是需要卸货的人数，D 是持续时间。一个示例可能如下所示：

容器（a,1,1）。
容器（b,2,2）。
容器（c,2,2）。
容器（d,3,3）。

容器也可以放在另一个容器上，例如：

上（a，c）。
上（b，c）。
上（c，d）。

容器 a 在 c 之上，依此类推...

问题是最小化卸载集装箱的成本。成本定义为雇佣人数乘以所需时间。在整个卸货期间雇用所有人员。

我从问题开始就遇到了问题，因为我不熟悉 prolog 的 clp 部分。有没有人对如何解决问题或在哪里可以找到有关 clp prolog 如何工作的示例有任何建议？

4

2 回答 2

3

如果为每个作业的开始和结束声明时间变量，那么 累积/2 可以对整个过程进行建模，而序列化/2 可以对 on/2 约束进行建模：

...
Tasks =
    [task(SA,1,EA,1,_)
    ,task(SB,2,EB,2,_)
    ,task(SC,2,EC,2,_)
    ,task(SD,3,ED,3,_)],
cumulative(Tasks, [limit(MAX)]),

serialized([SA,SC,SD],[1,2,3]),
serialized([SB,SC,SD],[2,2,3]),
...

这已经产生了一个合理的解决方案，并且易于表达总时间的最小化。

...
labeling([min(max(EA,max(EB,max(EC,ED))))], [SA,SB,SC,SD]).

[SA,SB,SC,SD] = [0,0,2,4]

但是您必须计算进度的成本，乘以所需的工人数量和总工期。实际上，这是一个复杂的计算，因为它依赖于任务的重叠。我们不能简单地在重叠任务上添加工作人员，因为不同持续时间的任务可能使用同一组工作人员。

我认为有一个适用的“技巧”：从所需的绝对最小值开始（在这种情况下，容器 d 为 3），迭代加深限制（MAX）。

编辑

对不起，我对序列化/2 错了。应该用显式比较代替，比如

EA #=< SC,
...
于 2015-10-26T19:13:51.657 回答
2

好的，所以我添加了

EA #=< SC,
EB #=< SC,
EC #=< SD,

解决方案似乎是正确的，所以很好。但我觉得这应该更笼统。有没有办法生成：

EA #=< SC,
EB #=< SC, 
EC #=< SD,

通过调用类似 generate_constrains() 的东西，它使用：

on(A,C).
on(B,C).
on(C,D).

并构造约束。

于 2015-10-27T20:08:28.760 回答