标签: constraint-programming

考虑以下正方形：

您将获得三个约束：

1. 所有矩形（A、B、C、D 和 E）具有相同的面积；
2. 它们的几何布局构成一个正方形；和
3. A 的高度为 2。

现在，我知道手动解决这个问题非常简单，但我认为这将是一个很好的例子来展示 CLP(Q/R) 与 Prolog 的功能：

剧透警告：如果您想先自己解决难题，请不要继续阅读本文，因为存在一些限制条件会泄露解决方案。

无论如何，这是我尝试用 CLP(Q/R)定义（我认为包括冗余约束）这个难题：

:- use_module(library(clpr)).

solve(Eh) :-
  A = B, B = C, C = D, D = E,

  { A  >= 1, B  >= 1, C  >= 1, D  >= 1, E  >= 1,
    Aw >= 1, Bw >= 1, Cw >= 1, Dw >= 1, Ew >= 1 },
  
  { Ah = 2 },
  
  { A = Ah * Aw,
    B …

我正在开发一个交互式作业调度应用程序.给定一组具有相应容量/可用性配置文件的资源,一组要在这些资源上执行的作业以及一组约束,这些约束确定作业顺序和作业的最早/最晚开始/结束时间我想让用户手动移动周围的工作.基本上我希望用户能够"抓住"作业网络的节点并在不违反任何约束的情况下及时向前/向后拖动它.

该图显示了一个简单的示例配置.最后的三角形作业表示所有作业的最新完成时间,作业之间的连接线对作业施加顺序,灰色/绿色条表示资源可用性和负载.

您可以拖动任何作业来压缩计划.请注意,由于容量配置文件不同,作业的长度会发生变化.

我已经实现了一种有效的ad-hock算法.但是仍然存在失败并违反某些限制的情况.然而,由于作业车间调度是一个研究很充分的领域,有很多算法和启发式方法可以找到一般的NP难问题的最优(或相当好)解决方案 - 我认为解决方案应该存在于我更容易的子集中.我已经研究了约束编程主题甚至基于物理的解决方案(通过静态关节连接的刚体),但到目前为止找不到合适的东西.任何指针/提示/提示/搜索关键词对我来说？

我已经使用我选择的约束求解器进行了练习来解决斑马拼图,我尝试使用Prolog clpfd库.

我知道在Prolog中还有其他更惯用的方法可以解决这个问题,但这个问题是关于clpfd包的!

所以我想解决的难题的具体变化(假设有很多)是这个:

有五个房子

1. 英国人住在红房子里
2. 瑞典人拥有一条狗
3. 丹麦人喜欢喝茶
4. 温室被留给白宫
5. 温室的主人喝咖啡
6. 抽烟Pall Mall的人拥有一只鸟
7. 牛奶在中间的房子里喝醉了
8. 黄屋的主人吸烟了登喜路
9. 挪威人住在第一宫
10. 万宝路吸烟者住在猫主人旁边
11. 马主人住在吸烟的人旁边
12. winfield吸烟者喜欢喝啤酒
13. 挪威人住在蓝屋旁边
14. 德国人吸食罗斯曼
15. 万宝路吸烟者有一个喝水的邻居

我尝试用以下方法解决它:

房屋可以具有的每个属性被建模为变量,例如"英国","狗","绿色"等.属性可以取1至5的值,具体取决于它们出现的房屋,例如,如果变量"狗"取值3,狗住在第三宫.

这种方法可以很容易地模拟邻居约束,如下所示:

def neighbor(X, Y) :-
    (X #= Y-1) #\/ (X #= Y+1).

但不知何故,该clpfd软件包不会产生解决方案,即使(IMO)问题已正确建模(我使用与Choco约束求解器完全相同的模型,结果是正确的).

这是完整的代码:

:- use_module(library(clpfd)).

neighbor(X, Y) :-
    (X #= (Y - 1)) #\/ (X #= (Y + 1)).

solve([British, Swedish, Danish, Norwegian, German], Fish) :-

    Nationalities = [British, Swedish, Danish, Norwegian, German],
    Colors = [Red, Green, Blue, …

我想做一些类似于约会调度算法的事情(N个人有N个自由忙插槽,约束满足).使用Hopcroft-Karp算法.但我的额外要求是我的时间间隔是重叠的.例如.时段可以是上午10点至11点或上午10点15分至11点15分.所以如果我选择上午10点到11点的时段,我不想选择上午10点15分到11点15分.是否有可能在不严重影响性能的情况下实现这一目标？

前段时间我为2014年Codeforces愚人节大赛创造了一个问题 - "Feed the Golorp":http://codeforces.com/contest/409/problem/I .请阅读提供的链接上的问题陈述.

这个问题原本是由那些根本不了解Prolog的人解决的.在比赛期间,只有3人设法解决了这个问题 - 使用Java,Python和C++.

主要挑战是了解需要做什么.对于具有一些Prolog经验的人来说,很明显golorp的名字就像?(_-_/___*__):-___>__.定义Prolog谓词一样,并且任务是找到变量的最小值,使谓词满足.有一些细节:再次,请阅读问题陈述.

实际上在理解目标之后解决问题并非如此微不足道.在算法上,任务是根据约束对变量进行拓扑排序.Golorp的名称最长可达1024个字符,因此需要相当高效的算法.

我用Python用正则表达式编写了我的参考解决方案.但在比赛结束后,我开始想知道如何解决Prolog中的问题.

由于只使用Prolog回溯到暴力强迫,golorp的名称可能长达1024个字符,所有可能性看起来都不可行 - 可能需要约束逻辑编程.

如果我可以从不等式中提取所有变量的列表和变量对的列表,我可以解决它.例如在ECLiPSe CLP中:

:- lib(ic).
solve(Vars, Ineqs, Result) :-
    Vars :: 0..9,
    ( foreach((A, B), Ineqs) do
        A #< B ),
    labeling(Vars),
    concat_string(Vars, Result).

[eclipse]: Vars = [__, ___, __, ___], Ineqs = [(__, ___)], solve(Vars, Ineqs, Result).

Vars = [0, 1, 0, 1]
__ = 0
___ = 1
Ineqs = [(0, 1)]
Result = "0101"

但是我不知道如何在没有太多代码的情况下获得Vars = [__, ___, …

什么是通用、有效的算法来查找离散值矩阵中使行唯一的列的最小子集。

例如，考虑这个矩阵（带有命名列）：

A B C D
 2 1 0 0
 2 0 0 0
 2 1 2 2
 1 2 2 2
 2 1 1 0

矩阵中的每一行都是唯一的。但是，如果我们删除列a并d保持相同的属性。

我可以枚举所有可能的列组合，但是，随着矩阵的增长，这很快就会变得棘手。有没有更快、最优的算法来做到这一点？

假设我有一个包含 16 个数字的列表。有了这 16 个数字，我可以创建不同的 4x4 矩阵。我想找到所有 4x4 矩阵，其中列表中的每个元素都使用一次，并且每行和每列的总和等于 264。

首先，我找到列表中元素的所有组合，总和为 264

numbers = [11, 16, 18, 19, 61, 66, 68, 69, 81, 86, 88, 89, 91, 96, 98, 99]

candidates = []
result = [x for x in itertools.combinations(numbers, 4) if sum(x) == 264]

result成为一个列表，其中每个元素都是一个包含 4 个元素的列表，其中 4 个元素的总和 = 264。我认为这些是我的行。然后我想对我的行进行所有排列，因为加法是可交换的。

for i in range(0, len(result)):
    candidates.append(list(itertools.permutations(result[i])))

现在给出总和为 264 的所有可能行。我想选择 4 行的所有组合，以便每列的总和为 264。

test = []
for i in range(0, len(candidates)):
    test = test + candidates[i]
result2 = …

我正在努力熟悉约束编程.

到目前为止,我看到的所有文档/视频都只包含基于CP库利用率的顶级概念和代码示例的描述(如Choko,Gecode,JaCoP等).

我想在没有任何库的情况下在Java中实现至少一些简单的东西.

有没有资源可以在Java/C#/ C++/Python中找到实现主要CP思想的工作代码？(至少"发送更多钱"问题解决方案).

(或者,也许,如果有人可以在这里解释,那就太好了).

为了解决一组布尔方程,我正在使用以下输入试验Constraint-Programming Solver MiniZinc:

%  Solve system of Brent's equations modulo 2

%  Matrix dimensions
int: aRows = 3;
int: aCols = 3;
int: bCols = 3;
int: noOfProducts = 23;

%  Dependent parameters
int: bRows = aCols;
int: cRows = aRows;
int: cCols = bCols;
set of int: products = 1..noOfProducts;

%  Corefficients are stored in arrays
array[1..aRows, 1..aCols, products] of var bool: A;
array[1..bRows, 1..bCols, products] of var bool: B;
array[1..cRows, 1..cCols, products] of var …

我正在尝试解决具有时间窗口限制的 TSP。我正在评估以下工具。

1. OptaPlanner - 由 Jboss 社区支持。不是特定于 TRP 的，而是通用约束求解器引擎。

2. Jsprit - 不确定它的支持。它是由 GraphHopper 开发的吗？它在 GitHub 上列出了 Graph Hopper 的子项目之一。

3. Google OR 工具 - 它是用 C++ 编写的。但可以在java中运行。

上述每种工具的优点和缺点是什么？市场上有更好的开源/付费工具吗？