标签: constraint-programming

我正在学习一些CSP(约束满足)理论的东西,并且正在使用这个库来解析XML文件.我正在使用Xcode作为IDE.

我的程序编译得很好,但是当它链接文件时,我得到XMLParser_libxml2.hh文件的重复符号错误.我的文件是这样分开的:

包含上面的XMLParser文件的类头文件包含类头文件
的类实现文件包含类头文件
的主文件

重复的符号出现在main.o和classfile.o中,但据我所知,我实际上并没有两次添加.hh文件.

完整错误:

ld: duplicate symbol bool CSPXMLParser::UTF8String::to<std::basic_string<char,
std::char_traits<char>, std::allocator<char> > >(std::basic_string<char,
std::char_traits<char>, std::allocator<char> >&) constin
/Users/vash265/CSP/Untitled/build/Untitled.build/Debug/Untitled.build/Objects-
normal/x86_64/dStructFill.o and
/Users/vash265/CSP/Untitled/build/Untitled.build/Debug/Untitled.build/Objects-
normal/x86_64/main.o`

将类的实现复制到主文件中并将类实现文件从编译目标中删除会消除错误,但这种混乱是一种混乱,我将很快添加更多类(并且它会很好将它们放在单独的文件中).

正如我已经理解的那样,这是由文件(XMLParser_libxml2.hh)在一个文件中同时具有类和函数定义和实现引起的(似乎这可能是由于在那个'标题'文件).关于如何在main.cpp中粘贴所有类文件的任何想法？(我试过#ifdefs,他们不工作).

我试图解决数独作为家庭作业的约束满足问题.我已经为特定行中的所有元素以及列构建了约束.我正在尝试为子区域中的元素构造约束,但我遇到了一些麻烦.

我当前算法背后的一般思想是将子区域中的所有变量(例如,9x9网格的3x3框)添加到列表中,然后置换该列表中的所有值以在每个变量之间构造NotEqualConstraints .下面的代码适用于NxN网格的第一个子区域,但我不知道如何更改它以迭代整个网格的其余部分.

int incSize = (int)Math.sqrt(svars.length);

ArrayList<Variable> subBox = new ArrayList<Variable>();

for (int ind = 0; ind < incSize; ind++) {
for (int ind2 = 0; ind2 < incSize; ind2++) {
    subBox.add(svars[ind][ind2]);
    }
}

for (int i = 0; i < subBox.size(); i++) {
for (int j = i + 1; j < subBox.size(); j++) {
   NotEqualConstraint row = new NotEqualConstraint(subBox.get(i), subBox.get(j));
   constraints.add(row);
   }
}

任何人都可以指导我如何修改代码来打击每个子区域而不仅仅是左上角的方向吗？

编辑:我也愿意尝试任何有效的算法,没有必要为每个子区域的ArrayList添加所有值.如果您看到更好的方式,请分享见解

我有一个表达,假设,

a = 1 && (b = 1 || b != 0 ) && (c >= 35 || d != 5) && (c >= 38 || d = 6)

我希望它减少到,

a = 1 && b != 0 && (c >= 38 || d = 6)

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

Nota Bene:我相信Karnaugh Map或Quine-McCluskey不是一个选择.由于这些方法不处理灰色案例.我的意思是,表达只能减少,就像A或A'或任何东西,或说黑色或白色或缺乏颜色.但是在这里,我有灰色阴影,正如大家们所看到的那样.

解决方案:我已经在Clojure中为此编写了程序.我使用了包含函数值的地图.这非常方便,只是几个组合的一些规则,你很好.谢谢你的有用答案.

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

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

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

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

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

任何或多或少的实用编程语言和编译器都必须处理约束.最常见的约束是类型.通常,类型推导和统一是通过简单的算法(例如Hindley-Milner)完成的,其中最终程序中的所有项都被赋予唯一类型.如果没有发生,则会出现错误指示.

在编译器中可能存在更复杂的约束,其中完全统一是不可能的,并且解决方案仅在某些限制下存在.可能的例子是

• 数据流分析.仿射相等约束的解可以用于循环矢量化.

• 内存管理.如果我们对引用和数据访问模式有一些约束,编译器可以从优化引用计数和垃圾收集中受益.

从另一点来看,约束求解器(如Z3或Yices)在为不同类型的约束寻找可满足的模型方面非常强大.

我正在寻找有关编译器如何从SMT求解器的强大功能以及他们正在解决的任务类型中受益的成功案例.我列出了一些区域,但我没有找到任何具体的例子.你能建议吗？

为了解决一组布尔方程,我正在使用以下输入试验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 …

我是约束编程的初学者，我在我的 c# 程序中使用Google or-tools 库。

我想向我的求解器添加以下约束：

((t1 >= 12 && t1 <= 15) || (t2 >= 16 && t2 <= 18)) && ( t1 + t2 ) < 30

所以我用c#写了下面一段代码：

var solver = new Solver("My_CP_Colver");
var t1 = solver.MakeIntVar(12, 20,"t1");
var t2 = solver.MakeIntVar(12, 20,"t2");

solver.Add(???)//<-((t1 >= 12 && t1 <= 15)||(t2 >= 16 && t2 <= 18)) && ( t1 + t2 ) < 30

请帮助做出上述限制？

我对Choco和CP完全不熟悉,但是我正在制作一个小模型来解决Steiner树问题,而Choco一直强迫第一个节点无论图形是什么(并且它不正确,我检查过).

我有一个esIntVar 数组,如果边缘在解决方案中== 1,否则== 0.对于vs设置顶点的数组也是如此.我使用数组activeEdgeW能够有一个标量约束,其中coeffs是可变的.然后我只有通道约束,树约束和sum == w约束.并尽量减少w.相当简单,但由于某种原因vs[0] == true总是,任何图形.

我的模型老实说非常简单,我真的不知道它来自哪里:

    s = new Solver("Solver");
    vs = VF.boolArray("vs", nbV, s);
    es = VF.boolArray("es", nbE, s);
    w = VF.integer("w", 0, maxW, s);

    IntVar[] activeEdgeW = new IntVar[nbE];
    for(int i = 0; i < nbE; i++) { 
        activeEdgeW[i] = VF.enumerated("activeEdgeW["+i+"]", new int[]{0,ws[i]}, s); //Weight is either 0 or ws[i]
        ICF.arithm(activeEdgeW[i], "=", ws[i]).reifyWith(es[i]); //weight of edge is ws[i] if edge is in, 0 otherwise
    }


    UndirectedGraph …

我正在尝试使用loco进行优化的基本示例.

我有一个成本向量,其索引对应于多个时隙的整数值,并希望最小化时隙的不同子集的成本之和.

请参阅下面的我的尝试,但由于所选插槽与成本之间没有"链接",因此无效.

(def costs [10 10 20 20 30 30 40 40 10 10])

(let [slot-vars (for [i (range 5)] ($in [:slot i] 1 10))
      cost-vars (for [i (range 10)] ($in [:cost i] 10 40))]
  (solution
   (concat
    slot-vars
    cost-vars
    [($distinct (for [i (range 5)] [:slot i]))]
    (for [i (range 5)]
      ($= [:cost i] (get costs i))))
   :minimize (apply $+ (for [i (range 5)] [:slot i]))))

约束编程(CP)和线性规划(LP)或混合整数规划(MIP)之间有什么区别？我知道什么是LP和MIP,但不明白与CP的区别 - 或者CP与MIP和LP相同？我对此很困惑......