• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Compiling CSPs into Tree-Driven Automata for Interactive Solving
【24h】

Compiling CSPs into Tree-Driven Automata for Interactive Solving

机译：将CSP编译成树驱动的自动机以进行交互式求解

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Constraint programming techniques are widely used to model and solve decision problems and many algorithms have been developed to solve automatically and efficiently families of CSPs; nevertheless, they do not help solve interactive decision support problems, like product configuration. In such problems, the user chooses the values of the variables, and the role of the system is not to solve the CSP, but to help the user in mis task. Dynamic global consistency maintaining is one of the most useful functionalities that should be offered by such a CSP platform, Unfortunately, this task is intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, compilation methods have been proposed that transform the original problem into a data structure allowing a short response time. In this paper, we extend the work of Amilhastre et al. [1] and Vernpary [15] by the use of a new structure, tree-driven automata, that takes advantage of the structural characteristics of configuration problems (decomposition of the components into independent subcomponents). Tree-driven automata can be far more compact than classical automata while keeping their good properties, especially a tractable complexity for the maintenance of global consistency.
机译：约束编程技术被广泛用于建模和解决决策问题，并且已经开发了许多算法来自动有效地解决CSP系列问题。但是，它们不能帮助解决交互式决策支持问题，例如产品配置。在这样的问题中，用户选择变量的值，而系统的作用不是解决CSP，而是帮助用户完成任务。动态全局一致性维护是这种CSP平台应提供的最有用的功能之一，不幸的是，在最坏的情况下，此任务很难完成。由于交互性要求响应时间短，因此必须以某种方式规避难处理性。为此，已经提出了将原始问题转换为允许较短响应时间的数据结构的编译方法。在本文中，我们扩展了Amilhastre等人的工作。 [1]和Vernpary [15]通过使用树驱动的自动机这一新结构，该结构利用了配置问题的结构特征（将组件分解为独立的子组件）。树驱动的自动机可以比经典自动机更紧凑，同时保持其良好的性能，尤其是维护全局一致性的复杂性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号