一种高效的FDE并行传播算法

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题上维持fPWC.目前, FDE的合适STR算法是STRFDE和STR2,而不是CT.这是由于CT算法可能产生内存溢出问题.在维持相容性算法的过程中,需要将迭代地调用各个约束执行其相容性算法过滤搜索空间,这个过程称为约束传播.动态提交方案是一个并行约束传播框架,可以并行地调度约束执行传播算法.它在大规模问题中,改进效果尤为明显.改进STRFDE和动态提交传播算法.针对FDE提出了PSTRFDE算法. PSTRFDE可以嵌入到动态提交方案中,进一步提高了约束规划问题的求解效率.大量的实验表明, PSTRFDE与CT和STRbit相比,可以减少内存占用;与STRFDE和STR2相比,可以提高算法的效率.所作工作充分说明了PSTRFDE是FDE上最为高效的过滤算法.

基于相容性任务分配的三维建模集群方法

针对现有集群方法在倾斜影像三维建模时节点上存在的CPU和GPU资源浪费现象及三维建模效率不高等问题,本文提出了基于相容性任务分配的集群三维建模方法。首先,通过对三维重建任务进行两步提交划分,在建模效果不变的前提下提升集群的执行效率。然后,针对集群节点资源浪费现象,提出了相容性任务节点分配方式,实现了基于相容性任务分配的三维建模集群。最后,进行大规模影像三维重建试验测试,验证了大数据试验环境下相容性理论对分配方式优化的优越性,证明了本文方法对三维建模效率有明显提升作用。