gpt4 book ai didi

Prolog 约束处理 : Packing Squares

转载 作者:行者123 更新时间:2023-12-03 07:50:13 25 4
gpt4 key购买 nike

我正在尝试解决 prolog 中的约束处理问题。

我需要在 10x10 的网格中打包 4 个 5x5、4x4、3x3 和 2x2 的正方形。
它们可能不会重叠。

我的变量如下所示:

Name: SqX(i), i=1..10, domain: 1..10

其中 X 是 5、4、3 或 2。索引 i 代表行,域代表网格中的列。

我的第一个约束尝试定义正方形的宽度和高度。我这样表述:
Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0

这样可能的点就被限制在彼此相距 X 行和列的范围内。
然而,Prolog 在这些约束上停止并给出以下结果:
Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
I=1, J=1,
I=1, J=2,
I=1, J=3,
I=1, J=4,
I=1, J=5,
I=1, J=6,
=======================[ End Solutions ]=======================

所以它停在那里,甚至不检查其他方格。我的限制很可能太紧了,但我不明白为什么或如何。有什么建议?

最佳答案

对于每个正方形,定义 XY表示左上角的变量。
这些变量将具有域 1..10-L ,其中 L是正方形的长度。如果您将域设置为 1..10 ,正方形可能部分放置在 10x10 矩形之外。

然后您可以为每对矩形发布约束(X,Y)(X1,Y1)表示如果它们在 x 轴上重叠,则它们不能在 y 轴上重叠,反之亦然:

(((X  #=< X1) and (X+L   #> X1)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((X1 #=< X) and (X1+L1 #> X)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((Y #=< Y1) and (Y+L #> Y1)) => ((X+L #=< X1) or (X1+L1 #=< X))),
(((Y1 #=< Y) and (Y1+L1 #> Y)) => ((X+L #=< X1) or (X1+L1 #=< X)))

(您的特定约束语法可能会有所不同)

关于Prolog 约束处理 : Packing Squares,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13623775/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com