共查询到16条相似文献,搜索用时 62 毫秒
1.
约束传播技术对于约束满足问题的求解性能至关重要。约束传播技术在一个预处理过程中能彻底地移除一些局部不相容值,或者在搜索期间高效地剪枝搜索树。最大受限路径相容算法(max Restricted Path Consistency,maxRPC)是最近提出的一种强相容性约束传播算法,它能够删除更多不相容值,在解决复杂问题中取得了很好的效果。文中对弧相容算法AC和最大受限路径相容算法maxRPC的相关算法AC3,AC3rm,maxRPC1,maxRPC2,maxRPCrm,maxRPC3等及其相关变体分别进行介绍和比较。在Mistral求解器上的实验测试结果验证了各种算法的性能。 相似文献
2.
3.
4.
广泛弧相容算法(generalized arc consistency,简称GAC),是求解约束满足问题的核心方法.表约束理论上可以表示所有约束关系,在过去10年中,有很多应用于表约束的广泛弧相容算法被提出来.在这些算法中,表缩减算法的效率非常高.但是目前的表缩减算法只能应用于正表约束,无法直接应用于负表约束.首先,提出一种表缩减算法STR-N,可以直接应用于负表约束;然后,给出了STR-N的两个改进版本STR-N2和STR-NIC.实验结果显示,STR-N算法在负表约束上的求解效率具有明显的优势. 相似文献
5.
中文分词在自然语言处理中占据了十分重要的地位。为了提高中文分词的速度,论文提出了一种新的求解最大概率路径的方法。该方法主要分为两步:1)将词频总和的数值减小来解决下溢问题;2)避免使用复杂的计算方法,使用简单的除法操作来降低运行时间提高分词速度。最后,使用搜狗新闻数据集进行实验验证,新方法的中文分词速度相较于JIEBA的中文分词的速度显著提高,并且为了验证分词的性能,对准确率,召回率以及F1进行了计算,三个指标的值均可达到95%以上。 相似文献
6.
弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4\\+GPU与改进算法AC4\\+GPU+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案. 相似文献
7.
8.
研究了路网空间内的路径预测与查询技术,设计了基于统计信息和概率论的最优路径预测算法。实际应用中,路网错综复杂。提出可能路径集合的概念,并设计算法来提取当前路径预测涉及到的路网子网,减小路网规模和路径预测的复杂度。在空间网络环境下,现有移动对象位置预测技术主要针对短期预测,不能预测下一路口的交通情况。为了弥补这一缺陷,降低用户端的位置更新率,设计了路网移动模型来简洁描述提取自大量历史移动路径的移动统计特征,捕捉路口处转向模式。基于移动模型,提出了具有较高精度的交通预测模型来预测对象的运动路径。 相似文献
9.
一种基于预处理技术的约束满足问题求解算法 总被引:4,自引:0,他引:4
相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT MPAC和BT MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2~50倍. 相似文献
10.
文章提出了一种最大概率匹配的矢量量化编码算法,它为码书中的每一码字增加一个计数器,统计在编码图象时每个码字的出现的频数,并进行排序;在量化矢量时,根据当前码字出现频数大小依次选择侯选码字,即频数大的码字优先选为候选码字。该算法可以和已有的预测法结合,形成预测加最大概率匹配的联合矢量量化编码算法。实验表明,联合算法的效率较高,在最初几次的搜索中就能以较高的命中率命中最佳匹配码字。 相似文献
11.
ABSTRACTEnsuring consistency of knowledge systems is always one of the essential requirements because, without it, most of these systems become useless. Because of the importance, many studies have involved the restoration of consistency in knowledge systems. However, these approaches are only implemented on knowledge systems that are represented by logic or probabilistic logic, thus when we apply them to probabilistic knowledge systems, there are many inadequacies. To overcome these drawbacks, in this paper, we put forward a new model for restoring the consistency of a probabilistic knowledge base by focusing on changing the probabilities in this knowledge base via several inconsistency measures. To this end, a set of inconsistency measures is presented and a family of consistency restoring operators for probabilistic knowledge bases is introduced. Next, an axiomatic model consists of a set of axioms is built to characterize the desirable properties of the consistency restoring operators. Finally, the properties of each consistency restoring operator in the introduced family are investigated and discussed. 相似文献
12.
A constraint network is arc consistent if any value of any of its variables is compatible with at least one value of any other variable. The Arc Consistency Problem (ACP) consists in filtering out values of the variables of a given network to obtain one that is arc consistent, without eliminating any solution. ACP is known to be inherently sequential, or P-complete, so in this paper we examine some weaker versions of it and their parallel complexity. We propose several natural approximation schemes for ACP and show that they are also P-complete. In an attempt to overcome these negative results, we turn our attention to the problem of filtering out values from the variables so that each value in the resulting network is compatible with at least one value of not necessarily all, but a constant fraction of the other variables. We call such a network partially arc consistent. We give a parallel algorithm that, for any constraint network, outputs a partially arc consistent subnetwork of it in sublinear ( O(
logn)) parallel time using O(n2) processors. This is the first (to our knowledge) sublinear-time parallel algorithm with polynomially many processors that guarantees that in the resulting network every value is compatible with at least one value in at least a constant fraction of the remaining variables. Finally, we generalize the notion of partiality to the k-consistency problem. 相似文献
13.
This paper discusses the performance analysis of two generic fundamental parallel search techniques on shared memory multi-processor
systems in solving the constraint satisfaction problem (CSP). Probabilistic analysis on their expected computation steps needed
and their inherent load-balancing capability is performed. Corresponding experimental results are alsoprovided to verify the
correctness of the proposed analysis. This fundamental analysis approach can be further applied to various advanced parallel
search techniques or various problem solving techniques on parallel platforms.
This research was supported in part by the University of Texas at San Antonio under the Faculty Research Award program 相似文献
14.
CHEN Yangjun 《计算机科学技术学报》1999,14(4):298-308
In this paper,we propose a new arc consistency algorithm,AC-8,which requires less computation time and space than AC-6 and AC-7.The main idea of the optimization is the divide-and-conquer strategy,thereby decomposing an arc consistency problem into a series of smaller ones and trying to solve them in sequence. In this way,not only the space complexity but also the time complexity can be reduced.The reason for this is that due to the ahead of time performed inconsistency propagation(in the semse that some of them are executed before the entire inconsistency checking has been finished),each constraint subnetwork will be searched with a gradually shrunk domain.In addition,the technique of AC-6 can be integrated into our algorithm,leading to a further decrease in computational complexity. 相似文献
15.
Jean-Charles Régin 《Constraints》2002,7(3-4):387-405
A global cardinality constraint (gcc) is specified in terms of a set of variables X={x
1,...,x
p} which take their values in a subset of V={v
1,...,v
d}. It constrains the number of times each value v
iV is assigned to a variable in X to be in an interval [l
i,u
i]. A gcc with costs (costgcc) is a generalization of a gcc in which a cost is associated with each value of each variable. Then, each solution of the underlying gcc is associated with a global cost equal to the sum of the costs associated with the assigned values of the solution. A costgcc constrains the global cost to be less than a given value. Cardinality constraints with costs have proved very useful in many real-life problems, such as traveling salesman problems, scheduling, rostering, or resource allocation. For instance, they are useful for expressing preferences or for defining constraints such as a constraint on the sum of all different variables. In this paper, we present an efficient way of implementing arc consistency for a costgcc. We also study the incremental behavior of the proposed algorithm. 相似文献