如何使用Prolog CLP FD进行路径限制?

问题描述 投票:3回答:2

我正试图通过Prolog CLP FD使用限制编程来解决提出的难题。这个难题包含下一个简单的规则:

现在,在我的代码中,我已经涵盖了2x2网格的限制,并且一个必须连接到相同颜色的至少一个。

问题是,我找不到一种方法来建立限制,说明一件必须有一个PATH(连接)到相同颜色的所有其他部分,而不通过相反颜色的部分,所以我得到这种输出:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 0

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

其中1s并非全部相互连接。

如何在CLP FD中编写这种图形限制?

编辑:我正在使用SICStus Prolog。

prolog puzzle clpfd clp
2个回答
2
投票

改写你的情况,以便我们可以更清楚地思考它:

  1. 你已经可以生成答案了
  2. 但答案目前过于笼统。

为了使您的程序更具体,您必须在您生成的一个答案中找到当前违反的条件,但必须在每个解决方案中保留这些条件,然后使用约束表达此条件。

例如,再考虑一下你的情况:

0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1

这里违反了哪些条件?显然,1片不是沿着一条路。但是用CLP(FD)描述一条完整的路径是非常繁琐的,而且由于这显然是从考试或家庭作业问题中得出的,因此这个想法表明自己有一个简单的局部标准来表达所需的条件。

通过“本地”,我的意思是你只需要考虑几个邻居而不是整个董事会。

所以,再次考虑1件。显然,每个1片都有一个邻居,在这个答案中也是1。还有什么?每个1片都有2个邻居吗?目前没有,不是。每个1片段是否有2个邻居也是1?如果没有,可以接受多少例外?

如果你考虑这些条件,你肯定会得到一个很好的解决方案。

一个提示:有时,具体化的约束在这些任务中很有用。这意味着你可以说:B #<==> (X #= Y),让B表示X #= Y是否成立。请注意,在这种情况下您甚至可能不需要这样做。


0
投票

你们俩最后解决了这个问题吗?

我对这个问题很感兴趣,想看看代码,如果存在的话。

我认为circuit / 1无法帮助,并希望看到解决这个问题的用法。

© www.soinside.com 2019 - 2024. All rights reserved.