标签: 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并强制路径开始和结束,以提高效率

我该怎么做才能提高效率？代码包含在下面以供参考.

skyscrapersinfences.pro

:-use_module(library(clpfd)).
:-use_module(library(lists)).

:-ensure_loaded('utils.pro').
:-ensure_loaded('s1.pro').

print_row([]).

print_row([Head|Tail]) :-
    write(Head), write(' '),
    print_row(Tail).

print_board(Board, BoardWidth) :-
    print_board(Board, BoardWidth, …

假设有n个项目,例如i ₁,i ₂,...... i _n,它们中的每一个都具有已知的有界权重w ₁,w ₂,... w _n.还有一组m背包,例如k ₁,k ₂和k _m.背包是同质的,它们都具有相同的容量W.功能F可以确定每个背包的得分.F的输入是每个背包中的项目.所以,

Score of each knapsack i = F(Items in knapsack i)

现在我想把一些物品放在背包里,这样:

1. 背包中物品的重量不超过其容量W.
2. 所有背包的得分总和最大

是否存在针对此问题的多项式时间解决方案？

注意:问题是0-1,即每个项目都可以选择.所有问题参数都是有界的.

编辑1:是不是可以减少这个问题来装箱,然后得出结论,这是一个NP难问题？

编辑2在此问题中,每个项目都有三个属性,例如属性a _i,b _i和c _i.F函数是一个线性函数,它获取其中项目的属性并生成输出.

编辑3:本文似乎为多背包问题提出了一个精确的解决方案.可以用在我的情况下吗？

我正在研究Java 6 ^*1的源到源转换器.

我需要保持负面信息和正面信息,因此我必须为变压器实施小约束系统.该约束系统是受限制的种类可被定义为下面的CNF式:

(v1 == c1 /\ v2 == c2 ... vn == cn) /\ ((w1,1 != d1,1 \/ w1,2 !== d1,2 ... w1,k != d1,k) /\ (w2,1 != d2,1 \/ ...) /\ ... (wm,1 != dm,1 \/ ... \/ wm,k != dm,k))

其中vi == ci是等式约束(取代,变量赋值),

wj != dj,l是不平等的约束,

vi, wj,l是变量,

ci, dj,l是常量(文字).

常量类型是Java原始类型和映射到整数的引用类型.常量也是任意类似AST的结构(表示部分计算的表达式,可能包含(元)变量).

约束系统的工作原理如下:

当变换器到达条件(例如if(x == …

我想知道是否有人可以帮我解决这个问题:我必须使用Prolog与Constraing Logic Programming订购一个列表,我必须以更有效的方式来做.

所以我定义的主要谓词是下一个:

order(Xs,Ys) :-
    same_length(Xs,Ys),      /* To determine the list Ys with the Xs' length */
    perm(Xs,Ys),             /* Permutation */
    ordered(Ys),             /* Is Ys ordered? */
    ! .

每个先前辅助谓词的实现如下:

same_length(Xs,Ys) :-
    length(Xs,L),
    length(Ys,L).

perm([],[]).
perm([X|Xs],Ys) :- elem(X,Ys,Ws), perm(Xs,Ws).

ordered([]).
ordered([_]).
ordered([X,Y|Xs]) :- X =< Y, ordered([Y|Xs]).

elem(X,[X|Ys],Ys).
elem(X,[Y|Ws],[Y|Zs]) :- elem(X,Ws,Zs).

我已经证明了我制作的节目并且有效!但我不知道是否有可能提高效率,如果是,我怎么能这样做(我在这里阅读这个旧线程).我应该添加或修改任何约束吗？

谢谢!

有人可以提供一个简单的渠道约束示例吗？

通道约束用于组合约束问题的视点.约束编程手册很好地解释了它是如何工作的以及为什么它有用:

搜索变量可以是其中一个视点的变量,比如X1(这将在下面进一步讨论).随着搜索的进行,传播约束C1从X1中的变量的域中移除值.然后,信道约束可以允许从X2中的变量的域中移除值.使用第二模型C2的约束来传播这些值删除可以从这些变量中移除更多值,并且这些移除可以通过信道约束再次转换回第一视点.最终结果可能是在视点V1内移除的值多于仅由约束C1移除的值,导致搜索减少.

我不明白这是如何实现的.究竟是什么限制,它们在真正的问题中看起来如何？一个简单的例子非常有用.

我有一组很多(10000+)项,我必须从中选择20项.我只能选择一个项目.我的项目有利润和成本,以及几个布尔属性(如颜色).

我已阅读并阅读了https://developers.google.com/optimization/mip/integer_opt_cp和https://developers.google.com/optimization/mip/integer_opt中的教程,但我的约束与那些略有不同在那里.

每个项目都表示为一个元组:

item = ('item name', cost, profit, is_blue)

举个例子

vase = ['Ming Vase', 1000, 10000, 0]

plate = ['China Plate', 10, 5, 1]

并且项目的总集是列表列表:

items = [item1, item2, ..., itemN].

我的利润和成本也列出:

profits = [x[2] for x in items]
costs = [x[1] for x in items]

对于所选的每个项目,它需要具有最小值,并且至少5个项目必须将属性(is_blue)标志设置为1.

我想选择具有最高值的20个最便宜的项目,这样其中5个项目的属性标志设置为1.

我在使用谷歌OR工具制定这个问题时遇到了麻烦.

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                       pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x = {}

for i in range(MAX_ITEMS):
    x[i] = solver.BoolVar('x[%s]' % (i))

#Define the constraints 
total_chosen = 20 …

尝试对以下内容进行一些研究而没有运气.以为我会问这里,以防有人以前遇到过它.

我帮助一个志愿者运营的广播电台满足他们的技术需求.其中一个主要问题是他们希望以编程方式安排他们的广告.

有很多简洁而复杂的规则引擎用于广告,但我们需要的只是非常简单(以及任何值得思考的经验).

如果可能的话,我想用SQL编写一些东西来处理这些实体.理想情况下,如果有人为其他广告媒体(网络等)编写了类似的内容,那将非常有用.

实体:

• 广告(包含类别,每天播放次数,开始日期,结束日期或永久播放)
• 广告类别(餐厅,健康,食品店等)

为了过度简化问题,这将是一个优雅的sql语句.到达那里... :)

我希望能够使用上述两个实体每天生成一个播放列表,其中:

• 同一类别中没有两个广告在x个相互广告中播放.
• (很高兴)可以推广高促销广告

目前,还没有"广告位"可供填写.没有"一天中的时间"考虑因素.

我们将当天的广告排队,并在歌曲/节目等之间进行排队.我们知道每小时需要填写多少,等等.

有什么想法/想法/链接/例子吗？我将继续寻找并希望能够找到一些东西,而不是长期学习它.

考虑m乘n矩阵M,其所有条目都是0或1.对于给定的M,问题是是否存在非零向量v,其所有条目都是-1,0或1,其中Mv = 0.例如,

      [0 1 1 1]
M_1 = [1 0 1 1]
      [1 1 0 1]

在这个例子中,没有这样的向量v.

      [1 0 0 0]
M_2 = [0 1 0 0]
      [0 0 1 0]

在此示例中,向量(0,0,0,1)给出M_2v = 0.

给定m和n,我想找到是否存在这样的M,使得不存在非零v,使得Mv = 0.

如果m = 3和n = 4那么答案是肯定的,因为我们可以在上面看到.

我目前通过尝试所有不同的M和v来解决这个问题,这是非常昂贵的.

但是,是否可以将问题表达为整数编程问题或约束编程问题,因此我可以使用现有的软件包,例如SCIP,这可能更有效.

我们必须解决一个难题,我们需要从系统中检查来自多个源的许多复杂规则,以确定系统是否满足这些规则或如何更改以满足它们.

我们最初开始使用Constraint Satisfaction Problems算法(使用Choco)来尝试解决它,但由于规则和变量的数量会比预期的要小,我们希望在数据库上构建所有可能配置的列表并使用多个请求关于过滤此列表的规则并以这种方式找到解决方案.

与将CSP求解器算法用于合理数量的规则和变量相比,进行系统搜索有限制或缺点吗？它会显着影响性能吗？它会减少我们可以实施的约束吗？

例如:

你必须想象它有更多的变量,更大的定义域(但总是离散的)和更多的规则(和一些更复杂的)但不是将问题描述为:

x in (1,6,9)
y in (2,7)
z in (1,6)
y = x + 1
z = x if x < 5 OR z = y if x > 5

把它交给求解器我们会建一个表:

X | Y | Z
1   2   1
6   2   1
9   2   1
1   7   1
6   7   1
9   7   1
1   2   6
6   2   6
9   2   6
1   7   6
6   7   6
9   7 …

考虑以下正方形：

您将获得三个约束：

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 …