...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Applied Intelligence: The International Journal of Artificial Intelligence, Neural Networks, and Complex Problem-Solving Technologies >EXPERIMENTING WITH A TEMPORAL CONSTRAINT PROPAGATION ALGORITHM
【24h】

EXPERIMENTING WITH A TEMPORAL CONSTRAINT PROPAGATION ALGORITHM

机译：用时间约束传播算法进行实验

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

摘要

3-consistency algorithm for temporal constraint propagation over interval-based network, proposed by James Alien, is finding its use in many practical temporal reasoning systems. Apart from the polynomial behavior of this algorithm with respect to the number of nodes in the network, very little is known about its time complexity with respect to other properties of the initially given temporal constraints. In this article we have reported some of our results analyzing the complexity with respect to some structural parameters of the input constraint network. We have identified some regions, with respect to the structural parameters of the input network, where the algorithm takes much more time than it needs over other regions. Similar features have been observed in recent studies on NP-hard problems. Average case complexity of Alien's algorithm is also studied empirically, over a hundred thousand randomly generated networks, and the growth rate is observed to be of the order of quadratic with respect to the problem size (at least up to node 40, and expected to be lower above that). We have analyzed our data statistically to develop a model with which one can calculate the expected time to be consumed by the algorithm for a given input network. [References: 24]
机译：James Alien提出的用于基于时间间隔的网络上的时间约束传播的3一致性算法正在许多实际的时间推理系统中得到应用。除了该算法相对于网络中节点数的多项式行为外，相对于最初给定时间约束的其他属性，其时间复杂度知之甚少。在本文中，我们报告了一些分析输入约束网络某些结构参数的复杂性的结果。关于输入网络的结构参数，我们已经确定了一些区域，在该区域中，该算法比在其他区域上花费的时间要多得多。在有关NP难题的最新研究中，已经观察到类似的特征。还对超过十万个随机生成的网络进行了经验研究，研究了Alien算法的平均情况复杂度，并且相对于问题大小（至少到节点40为止，增长率预计为二次方），并且预期为低于此）。我们已经对数据进行了统计分析，从而开发出一种模型，利用该模型，可以计算出给定输入网络算法所需的预期时间。 [参考：24]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号