首页> 外文期刊>Journal of logic and computation >A Local Search Approach to Modelling and Solving Interval Algebra Problems
【24h】

A Local Search Approach to Modelling and Solving Interval Algebra Problems

机译:建立和求解区间代数问题的局部搜索方法

获取原文
获取原文并翻译 | 示例

摘要

Local search techniques have attracted considerable interest in the artificial intelligence community since the development of GSAT and the min-conflicts heuristic for solving propositional satisfiability (SAT) problems and binary constraint satisfaction problems (CSPs) respectively. Newer techniques, such as the discrete Langrangian method (DLM), have significantly improved on GSAT and can also be applied to general constraint satisfaction and optimization. However, local search has yet to be successfully employed in solving temporal constraint satisfaction problems (TCSPs). This paper argues that current formalisms for representing TCSPs are inappropriate for a local search approach, and proposes an alternative CSP-based end-point ordering model for temporal reasoning. The paper looks at modelling and solving problems formulated using Allen's interval algebra (IA) and proposes a new constraint weighting algorithm derived from DLM. Using a set of randomly generated IA problems, it is shown that local search outperforms existing consistency-enforcing algorithms on those problems that the existing techniques find most difficult.
机译:自从GSAT的发展以及分别解决命题可满足性(SAT)问题和二元约束满足问题(CSP)的最小冲突启发式方法以来,本地搜索技术在人工智能界引起了极大的兴趣。诸如离散朗朗日方法(DLM)之类的较新技术在GSAT上已有显着改进,并且还可应用于一般约束满足和优化。但是,本地搜索尚未成功地用于解决时间约束满足问题(TCSP)。本文认为,目前代表TCSP的形式主义不适用于本地搜索方法,并提出了一种基于CSP的替代方法,用于进行时间推理。本文着眼于建模和解决使用艾伦区间代数(IA)提出的问题,并提出了一种新的基于DLM的约束加权算法。通过使用一组随机生成的IA问题,可以证明在现有技术发现最困难的那些问题上,本地搜索的性能优于现有的一致性增强算法。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号