标签: constraint-satisfaction

在模拟退火(使用bean搜索)和遗传算法之间,在性能和用例方面有哪些相关差异？

我知道SA可以被认为是人口规模只有一个的GA,但我不知道两者之间的关键区别.

此外,我正在考虑一种情况,即SA将胜过GA或GA将胜过SA.只有一个简单的例子可以帮助我理解就足够了.

摘要问题描述:

我看到它的方式,unparsing意味着从AST创建一个令牌流,当再次解析时产生一个相等的AST.

所以 parse(unparse(AST)) = AST持有.

这等于找到一个有效的解析树,它将生成相同的AST.

该语言由使用eBNF变体的无上下文 S属性语法描述.

因此,解析者必须通过所有语法约束所包含的遍历节点找到有效的"路径".这基本上意味着找到AST节点到语法生成规则的有效分配.这通常是一个约束满足问题(CSP),可以通过回溯 O(exp(n))来解决,如解析.

幸运的是,对于解析,这可以使用GLR(或更好地限制语法)在O(n³)中完成.因为AST结构非常接近语法生成规则结构,所以我真的很惊讶看到运行时比解析更糟糕的实现:XText使用ANTLR进行解析和回溯以进行解析.

问题

1. 是一个上下文无关的S属性语法解析器和解析器需要共享的所有东西,还是有进一步的约束,例如解析技术/解析器实现？
2. 我觉得这个问题一般不是O(exp(n)) - 有些天才可以帮助我吗？
3. 这基本上是一个上下文敏感的语法吗？

例1:

Area    returns AnyObject   -> Pedestrian | Highway
Highway returns AnyObject   -> "Foo" Car
Pedestrian  returns AnyObject   -> "Bar" Bike
Car     returns Vehicle     -> anyObjectInstance.name="Car"
Bike    returns Vehicle     -> anyObjectInstance.name="Bike" 

所以,如果我有一个AST包含

AnyObject -> AnyObject -> Vehicle [name="Car"] 我知道root可以是Area,我可以解决它

Area    -> Highway  -> Car

因此(公路|行人)决定取决于子树决策.当一片叶子乍一看是几种类型中的一种时,问题会变得更糟,但必须是特定的一种,以便稍后形成有效路径. …

我正在研究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 == …

问题陈述:

给定四个单词,将它们放在amxn正方形网格中,使得网格区域尽可能小.

单词必须在网格内从左到右,从上到下运行.字母可能重叠,但不能形成其他字.所有单词都必须在一个巨链中相互链接.

可以用4个单词"一,二,三和四"形成的示例网格.请注意,最后一个网格是最优化的.

我正在尝试学习python,我认为这将是一个很好的应用程序,以切断我的牙齿.

任何想法如何构建我的数据和算法来解决这样的问题？我不是在寻找一个直接的答案,但有些提示如下:

使用此库,此类或此数据结构.或者通过可用空间这样迭代.

我只是想让某人验证以下问题是NP完全还是实际上有一个比简单的强力组合检查更好/更容易的解决方案.

我们的软件中存在一种资源分配问题,我将用一个例子来解释它.

假设我们需要4个人在白班工作.这个数字以及它是"白班"的事实记录在我们的数据库中.

但是,我们并不需要任何人填写这些地点,需要填写一些要求才能满足要求.

在这4个中,让我们说其中2个必须是护士,其中1个必须是医生.

其中一名医生也必须作为特定团队的一员工作.

所以我们有这套信息:

白班:4名
   1名医生
   1名医生,需要在A组
   1名护士工作

以上不是问题.当我们开始挑选人们白天工作并试图弄清楚到目前为止我们选择的人是否能够真正满足标准时,问题就出现了.

例如,假设我们选择James,John,Ursula和Mary来工作,其中James和Ursula是医生,John和Mary是护士.

厄秀拉也在A队工作.

现在,根据我们试图适应账单的顺序,我们最终可能会推断出我们是否拥有合适的人,除非我们开始尝试不同的组合.

例如,如果在列表中首先选择Ursula,我们可以将她与"1医生"标准相匹配.然后我们到了詹姆斯,我们注意到,由于他不在A队工作,所以关于"1位医生,需要在A队工作"的其他标准,不能用他来填补.由于其他两个人都是护士,他们也不符合这个标准.

因此,我们首先回溯并尝试詹姆斯,他也可以符合第一个标准,然后厄秀拉可以满足需要该团队的标准.

所以问题在我们看来,因为我们需要尝试不同的组合,直到我们要么全部尝试,在这种情况下我们有一些尚未填充的标准,即使工作头的总数与总数相同需要的头数,或者我们发现了一个有效的组合.

这是唯一的解决方案,任何人都可以想到更好的解决方案吗？

编辑:一些澄清.

对这个问题的评论提到,对于这几个人,我们应该蛮力,我同意,这可能是我们可以做的,我们甚至可以做到这一点,在某些优化看待大小的同一条道路上如果数据量很小,数据并选择不同的排序算法,初始开销较小.

但问题在于,这是一个名册规划系统的一部分,你可能会涉及很多人,"我们在白天需要X人"以及"我们有这个Y人群"这将是",以及一个大的潜力"我们有这个X人的Z标准列表,将不得不以某种方式与这些Y人匹配",然后你补充说我们将有在领导者调整名单的同时,实时进行相同计算的天数,然后需要快速解决方案.

基本上,领导者会在屏幕上看到一个实时信息,说明有多少人仍在失踪,无论是在整个日班,还是有多少人符合各种标准,以及我们实际有多少人除了我们拥有的那些之外.这个显示器必须更新半实时,而领导者调整名单时"如果詹姆斯采取白天而不是厄秀拉,而厄秀拉需要夜班".

但是非常感谢到目前为止已经回答过这个问题的人,约束满足问题听起来像我们需要的方式,但我们肯定会在这里仔细查看所有的链接和算法名称.

这就是为什么我喜欢StackOverflow :)

为什么Arc-Consistency Algorithm O(cd ³)的复杂性？

我有一个整数列表

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

我想找到这个列表的所有排列，这样对于每个排列

1. 元素 0 到 3 加起来为 264，

2. 元素 4 到 7 加起来为 264，

3. 元素 8 到 11 加起来为 264 和

4. 元素 12 到 15 广告最多 264。

目前我有以下策略

1. 使用 itertools.permutations 计算所有排列

2. 检查哪些排列满足我的条件

是否有另一种性能更好的策略？

我正在尝试使用 p5.js (Javascript) 创建一个棋盘游戏

为了设置 6 x 6 网格的游戏板，我必须用 6 种颜色填充网格，并且水平或垂直触摸单元没有相同的颜色。所有 6 种颜色必须在 6 个单元格中使用。

但现在我正在努力创建一个随机放置颜色但保持规则的算法。

我尝试从左上角开始，填充随机颜色。\n然后我开始用不同的颜色填充左侧和底部的单元格。

问题是，当脚本想要填充最后几个单元格时，没有剩余颜色可供使用（要么已经填充了 6 个单元格，要么剩余的颜色是邻居）

示例：\n仍然有两个单元格需要为红色，但只剩下一个位置为红色（在白色下方）：

//fill placedColors Array with zeros\nplacedColors = [];\nfor(let i=0; i<6; i++) {\n    placedColors[i] = 0;\n}\n\n//fill allIndexes Array with indizies to keep control of visited cells\nlet allIndexes = [];\nfor(let i=0; i<36; i++) {\n    allIndexes.push(i);\n}\n\n//build board\n//when I set the limit to 36 the script runs forever because no solution is found\nfor(let i=0; i<33; i++) {\n …

我找到了一种使用此链接中描述的方式找到所有解决方案的方法。

这工作正常，但速度很慢。由于它从一开始就重新计算约束，因此 i_e 没有利用之前的计算。

现在，我在此链接中看到 ，有一种更有效的方法可以使用 MiniSat 作为库来查找所有解决方案。但那里没有描述方法。

您能否为我指出正确的文档，以便有效地找到所有 SAT 解决方案？

谢谢。

任何人都可以向我解释AC-1,AC-2和AC-3算法？我必须了解它们并用代码实现它们.但首先,我想要了解它们真的很好,但它们太难以被我理解了.有什么帮助吗？顺便说一句,我不太熟悉回溯,我试着阅读并观看有关它的视频,但仍然是一样的!谢谢,

前段时间我正在写一篇与 OR 相关的文章以供发表。在这篇文章中，展示了使用 MiniZinc 解决某个优化问题的 MILP 模型。我在 10 个实例中以最佳方式解析了 10 个实例。

顾问对其进行审查并提到以下 2 条评论：

1. 您如何将 MiniZinc 与其他最新一代 MILP 求解器（如 CPLEX 或 Gurobi）在性能方面进行比较？

我一直在使用 MiniZinc，它对我很有效。我如何展示 MiniZinc 的多功能性？是否有参考书目或证明其合理性的方法？

2. 由于 MiniZinc 不是最著名的 MILP 求解器之一，因此您应该避免在摘要中提及它的名称。

出于什么原因，您不建议在摘要中提及它？

使用 MiniZinc 的有效理由是什么？