Stable Solutions for Dynamic Constraint Satisfaction Problems
Stable Solutions for Dynamic Constraint Satisfaction Problems
复制标题
动态约束满足问题的稳定解
DOI：
10.1007/3-540-49481-2_32
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Eugene C. Freuder
中科院分区：
文献类型：
--
作者：
R. Wallace;Eugene C. Freuder
约束技术的一个重要扩展涉及到可能使当前解决方案无效的变化。以前的工作动态问题寻求有效地找到新的解决方案的方法。我们采取了一种更积极主动的方法，探索在临时改变有效分配集（稳定解决方案）的变化后找到更有可能保持有效的解决方案的方法。为此，我们研究跟踪问题变化的策略，并将这些信息用于指导搜索更有可能稳定的解决方案。在这项工作中，搜索进行了最小冲突爬山过程中，有关变化的信息是用来偏置值的选择，无论是通过扭曲的目标函数或施加进一步的标准选择。我们研究跟踪价值损失或约束增加的方法，并将有关变化的相对频率的信息纳入搜索。我们的实验表明，这些方法通常是有效的，在寻找稳定的解决方案，并在某些情况下处理解决方案的稳定性和搜索效率之间的权衡相当不错。此外，我们确定了一个条件，在这些方法显着减少努力找到一个稳定的解决方案。
An important extension of constraint technology involves problems that undergo changes that may invalidate the current solution. Previous work on dynamic problems sought methods for efficiently finding new solutions. We take a more proactive approach, exploring methods for finding solutions more likely to remain valid after changes that temporarily alter the set of valid assignments (stable solutions). To this end, we examine strategies for tracking changes in a problem and incorporating this information to guide search to solutions that are more likely to be stable. In this work search is carried out with a min-conflicts hill climbing procedure, and information about change is used to bias value selection, either by distorting the objective function or by imposing further criteria on selection. We study methods that track either value losses or constraint additions, and incorporate information about relative frequency of change into search. Our experiments show that these methods are generally effective in finding stable solutions, and in some cases handle the tradeoff between solution stability and search efficiency quite well. In addition, we identify one condition in which these methods markedly reduce the effort to find a stable solution.