发帖
雷达卡
摘要翻译：
提出了新的序列约束过滤算法和基于网络流的序列约束扩展算法。我们在搜索树的一个分支中，在$O(n^2)$时间内对序列约束强制域一致性。这将现有的最佳域一致性算法提高了$O(\logn)$。这些算法中使用的流程是从一个线性规划导出的。其中一些不同于用于传播全局约束的流，如GCC，因为变量的域被编码为边缘的成本，而不是容量。这样的流对于在大域上保持边界一致性是有效的，并且对于其他全局约束可能是有用的。
---
英文标题：
《Flow-Based Propagators for the SEQUENCE and Related Global Constraints》
---
作者：
Michael J. Maher and Nina Narodytska and Claude-Guy Quimper and Toby
Walsh
---
最新提交年份：
2009
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in $O(n^2)$ time down a branch of the search tree. This improves upon the best existing domain consistency algorithm by a factor of $O(\log n)$. The flows used in these algorithms are derived from a linear program. Some of them differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains and may be useful for other global constraints.
---
PDF链接：
https://arxiv.org/pdf/0909.4452
京公网安备 11010802022788号
