共查询到20条相似文献,搜索用时 531 毫秒
1.
空间实体之间存在多种时空关系,主要包含拓扑、方向、距离、尺寸和时间等.以往的研究工作主要集中于3种以下时空关系结合的表示和推理,而3种以上结合的研究很少.但多种时空关系之间是相互统一和相互约束的,所以,将它们全部综合起来研究是时空推理研究发展的必然趋势,也是实际应用的迫切需要.提出了采用矩形关系统一表示多种空间关系,以矩形关系变化次数表示时间的时空统一表示模型,并在此基础上,利用概念邻域图推导空间关系变化和时间变化.据此,结合矩形关系网络和路径一致性算法,提出了检验上述统一模型网络一致性的算法,并分析了算法复杂度.该研究成果提高了空间关系分析方法的准确性,减小了时间信息的冗余,对地理信息系统中空间实体间的空间关系以及时间变化的分析和查询等有一定的理论意义与应用价值. 相似文献
2.
3.
快速数据包分流算法研究 总被引:1,自引:0,他引:1
瞿中 《计算机工程与设计》2005,26(9):2322-2325
基于“流”的数据包分类算法已经在第四层交换等领域中得到了应用,该类算法的特点是流表的容量大,流表的更新速度较快.“快速的数据包分流算法”采用了散列算法的基本思想,并引入了流的局部性原理来加速散列查找的过程,用软件对该算法进行了仿真测试,并在最后从时间复杂度和空间复杂度两个方面对其进行了性能分析.实验结果表明,该算法具有良好的时间复杂度和空间复杂度,可以实现快速的分流. 相似文献
4.
一个求解次短和渐次短路径的实用算法 总被引:1,自引:0,他引:1
求解第k短路径问题在决策支持系统和咨询系统中具有广泛的用途,本文基于Dijkstra算法,给出了一个求解次短路径和渐次短路径的算法,并且分析了算法的时间复杂度和空间复杂度。 相似文献
5.
6.
约束满足问题(Constraint Satisfaction Problems CSP)是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O(n^2)。 相似文献
7.
一种高效的层次聚类分析算法 总被引:4,自引:0,他引:4
层次聚类算法是一类重要的聚类分析方法。传统的层次聚类算法的时间和空间复杂度很大,这使得聚类分析在大型数据集上的应用受到限制。该文提出一种基于重叠区的3阶段改进算法,该算法将大大减少算法的时间复杂度和空间复杂度。 相似文献
8.
确定两个任意简单多边形空间关系的算法 总被引:4,自引:0,他引:4
阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。 相似文献
9.
本文通过对定时器原理的分析,结合队列数据结构和网络协议中"时间戳"的概念,提出了一种新的、较完善的多任务处理环境下的定时器应期算法,并且给出了主要程序的流程框图.该算法具有较高的效率和可靠性,其时间复杂度及空间复杂度均为O(n). 相似文献
10.
《计算机工程与应用》2017,(9):51-56
命题μ-演算局部模型检测算法中,目前最好的算法的时间复杂度与不动点算子交替嵌套深度d呈指数关系。针对命题μ-演算局部模型检测算法的计算过程进行分析,得到迭代计算的中间迭代值间满足的一组偏序关系,然后利用该偏序关系设计了一个局部模型检测算法,算法时间复杂度的指数部分为d/2,大大提高了算法的计算效率。 相似文献
11.
M. Cristani 《Artificial Intelligence》2004,156(2):177-196
Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete. 相似文献
12.
13.
《Robotics, IEEE Transactions on》2008,24(5):1107-1120
14.
Culberson JC 《Evolutionary computation》1998,6(2):109-127
The paper is in three parts. First, we use simple adversary arguments to redevelop and explore some of the no-free-lunch (NFL) theorems and perhaps extend them a little. Second, we clarify the relationship of NFL theorems to algorithm theory and complexity classes such as NP. We claim that NFL is weaker in the sense that the constraints implied by the conjectures of traditional algorithm theory on what an evolutionary algorithm may be expected to accomplish are far more severe than those implied by NFL. Third, we take a brief look at how natural evolution relates to computation and optimization. We suggest that the evolution of complex systems exhibiting high degrees of orderliness is not equivalent in difficulty to optimizing hard (in the complexity sense) problems, and that the optimism in genetic algorithms (GAs) as universal optimizers is not justified by natural evolution. This is an informal tutorial paper--most of the information presented is not formally proven, and is either "common knowledge" or formally proven elsewhere. Some of the claims are intuitions based on experience with algorithms, and in a more formal setting should be classified as conjectures. 相似文献
15.
数字签名是一种传统的用于XML文档完整性保护的方法,为XML文档的完整性保护,提出了一种新的基于水印技术的解决方案。实验表明,相比数字签名机制,提出的算法在时间复杂度和空间复杂度有所降低。 相似文献
16.
任务驱动式教学是指在整个教学过程中,以完成一个个具体的任务为线索,把教学内容巧妙地隐含在每个任务之中。在计算机应用课程的"任务"设计中,应使用"单刀直入法"化繁为简,既要使各任务能较好地涵盖课程知识点,又要能使学生在愉快的情景下完成学习任务。 相似文献
17.
18.
利用良性蠕虫来对抗蠕虫是一种新的蠕虫对抗技术。本文针对WAW模型中对抗蠕虫状态不可控、产生流量过大等问题提出了可控蠕虫的概念,给出了可控蠕虫的定义、分布式框 架结构和工作流程,并将可控蠕虫用作W-A-W中的对抗蠕虫,给出了可控蠕虫对抗蠕虫传播模型。经验证明,和已有良性蠕虫相比,用可控蠕虫对抗蠕虫产生流量影响更小状态更易控制,在不影响模型效果的情况下降低了模型的复杂度。 相似文献
19.
20.
Salem Benferhat Zied Bouraoui Odile Papini Eric Würbel 《Annals of Mathematics and Artificial Intelligence》2017,79(1-3):45-75
In real world applications, information is often provided by multiple sources having different priority levels reflecting for instance their reliability. This paper investigates ”Prioritized Removed Sets Revision” (PRSR) for revising stratified DL-Lite knowledge bases when a new sure piece of information, called the input, is added. The strategy of revision is based on inconsistency minimization and consists in determining smallest subsets of assertions (prioritized removed sets) that should be dropped from the current stratified knowledge base in order to restore consistency and accept the input. We consider different forms of input: A membership assertion, a positive or a negative inclusion axiom. To characterize our revision approach, we first rephrase Hansson’s postulates for belief bases revision within a DL-Lite setting, we then give logical properties of PRSR operators. In some situations, the revision process leads to several possible revised knowledge bases where defining a selection function is required to keep results within DL-Lite fragment. The last part of the paper shows how to use the notion of hitting set in order to compute the PRSR outcome. We also study the complexity of PRSR operators, and show that, in some cases, the computational complexity of the result can be performed in polynomial time. 相似文献