问题标签 [constraint-programming]

我正在开发一个小型 prolog 应用程序来解决摩天大楼和栅栏难题。

一个未解之谜：

已解决的谜题：

当我通过程序已经解决的难题时，它会很快，几乎是瞬间的，为我验证它。当我通过程序非常小的谜题（例如 2x2，当然要修改规则）时，找到解决方案也很快。

问题在于计算“原生”大小为 6x6 的谜题。在中止它之前，我已经让它运行了 5 个小时左右。时间太多了。

我发现耗时最长的部分是“栅栏”，而不是“摩天大楼”。单独运行“摩天大楼”会产生一个快速的解决方案。

这是我的栅栏算法：

• 顶点由数字表示，0 表示路径不经过该特定顶点，> 1 表示该顶点在路径中的顺序。
• 约束每个单元格使其周围有适当数量的线条。
  • 这意味着如果两个顶点具有连续编号，则它们是连接的，例如 1 -> 2, 2 -> 1, 1 -> Max, Max-> 1 （Max是路径中最后一个顶点的编号。通过计算maximum/2）
• 确保每个非零顶点至少有两个具有序号的相邻顶点
• 约束Max等于(BoardWidth + 1)^2 - NumberOfZeros（BoardWidth+1是沿边的顶点数，NumberOfZeros通过 计算count/4）。
• 用于nvalue(Vertices, Max + 1)确保不同值的数量Vertices是Max（即路径中的顶点数）加上1（零值）
• 找到第一个包含 a 的单元格3并强制路径从那里开始和结束，以提高效率

我可以做些什么来提高效率？代码包含在下面以供参考。

摩天大楼犯罪.pro

实用程序.pro

s1.pro

我正在寻找一个完整的 CSP 求解器，这意味着它总能找到一个解决方案（如果存在），并且会告诉您是否存在解决方案。首选为图形着色优化的求解器，但不是必需的。那里有许多迭代算法/求解器，但我的工作需要完整性（？）。

我已经使用弱承诺搜索算法实现了自己的求解器，但我确信有许多优化和基于线程的功能可以使求解器更快，并允许我增加可以在模拟中使用的变量数量. 我意识到这是一个指数级难题，但每一点都会有所帮助！

你知道是否有办法改变已经解决的 Cplex 约束优化问题中的一些约束，并再次解决它，但结果尽可能接近以前的解决方案。

例子：

任务分配给不同的资源。资源 1 有任务 A、B 和 C，资源 2 有任务 D、E 和 F。

当我添加资源 3 时，我希望新分配类似于：

但 Cplex 可能会返回如下内容：

或任何其他可能与初始解决方案完全不同的组合。

我认为这个问题被称为动态约束满足问题。

我一直在做很多研究，但似乎没有一种简单的方法可以做到这一点。看起来我必须自己实现（没关系）。在那种情况下，你建议我应该如何解决这个问题？

谢谢

我正在尝试使用 prologs 约束求解器解决特定问题，但我被卡住了：D 我的问题要求的更通用版本是这样的：

这是我使用的查询/目标：

并且程序将计算 X 和 Y 的值（在这种情况下 X=1，Y=1 是解决方案）。我在想的是，如果目标/查询中的参数数量可以变化。在这种情况下，我的序言程序需要有一个动态挂起的目标来代替用 %line1 和 %line2 注释的行。

问题是，我如何使这些表达延迟..？我不想在问题中对这些进行硬编码，并认为只有两个表达式会通过目标..

希望问题很清楚。谢谢。

我正在研究序言并面临这种情况 - 在我的查询中，我传递了这样的内容：

现在，我想做的是让 prolog 程序捕获不等式表达式，以便我可以在变量中具有上述不等式，如下所示：

变量 ' Lhs' 将有2*X + 3*Y 变量 ' Rhs' 将有3*Z 现在我希望所涉及的不等式也被分配到某个地方（在一个名为 Opr 的变量中？？），所以说像 Lhs Opr Rhs 这样的东西就像说“ 2*X + 3*Y >= 3*Z”..

这是我正在处理的场景的一般形式。我希望以某种方式识别所涉及的“不平等”，以便稍后在我的代码中使用它。

我正在使用 IC 库开发 Eclipse-CLP。

这是我在 prolog 中的算术不等式表达式：

我像这样使用统一术语操纵器：

现在我Lhs = 2*X + 3*Y, Rhs as 4*Z and Op as > 一切都很好，直到现在。

我想要的是使用 Eclipse Prolog 中的 IC 库为这个表达式构建一个延迟的目标。例如，我希望像这样分配一个新创建的变量：

现在，由于所需的不等式（在本例中为 >）存储在 Op 中，尽管我使用Eq = (Lhs #Op Rhs)，但 eclipse 正在返回错误。

当我的运算符要取自变量 Op 时，我如何创建这个延迟约束？谢谢你。

假设我定义了一些抽象形状，每个形状都有宽度和高度（为简单起见，我们将它们设为矩形）。如何将它们中的尽可能多的放置在定义宽度和高度的单个画布（只是一个术语，不一定是 HTML5 画布）上？

显然这是某种约束满足问题，但我真的不知道从哪里开始（除了蛮力）。谷歌搜索只会出现不相关的结果（可能是因为我不知道要搜索什么）。什么是一个好的算法，或者什么是创建一个算法来做到这一点的好方法？

菲兹就是一个很好的例子。形状（在本例中为圆形）以组的形式出现，并且不会相互重叠，并且不会相互干扰。我的用例更像是一次性定位交易。另一个例子是SpriteRight，它尽可能有效地放置在某些边界内。

我有一个表情，假设，

我希望它减少到，

有没有人有什么建议？指向任何算法的指针？

Nota Bene：我相信，卡诺图或 Quine-McCluskey 不是这里的选择。因为这些方法不处理灰色情况。我的意思是，表达只能减少到像 A 或 A' 或什么都没有，或者说是黑色或白色或无色的情况。但是在这里我有灰色阴影，正如你们所看到的。

解决方案：我已经在 Clojure 中为此编写了程序。我使用包含函数作为值的地图的地图。这很方便，只需几个组合的一些规则，你就很好。感谢您提供有用的答案。

如何在约束编程语言 ECLiPSe ( http://www.eclipseclp.org/examples/ ) 中进行变量求和？

我正在尝试获得此功能：

我得到的错误是：

如何制定有约束的有效作业调度？

调度程序应包括以下方法：

每个作业都有一个 id 和 time 参数。

对此问题的可能解决方案可能是基于技术回溯。作业用作选择点，时间瞬间用作选择（在最坏的情况下，活动的总持续时间是工作持续时间的总和，从而导致完全顺序执行）。

或者，我应该充分地表示数据，然后在时间轴上生成调度，将工作置于约束之下，并在不满足约束时在作业（以及依赖它的所有作业）中前进。但我不知道我如何在java中做到这一点。

换句话说，我在所描述的工作管理中寻找一种避免强烈回溯方法的方法。