工业类SAT实例的内部结构特性

人们一直在尝试找出更多有效的策略去求解SAT实例,我们为此提出一种分治策略：把一个实例分割成若干个小的实例,把一个难的实例分成若干个相对容易的实例去求解。     

基于分治思想的工种图样智能理解方法研究

首次引入分治思想,系统地提出了实际工程图样工程语义的表达方式分治、投影关系分治和尺寸约束分治等三个分治层次,每一层次又根据信息表达的深度,划分为低层的显式分治和高层的隐式分治。较系统地归类了显式语义,并挖掘了隐语义,从而赋予工程图样工程语义的动态性、层次性、易于形式化的特征,初步实现了工程图样的智能理解。     

基于快速排序算法的文献检索技术

文献搜索引擎在资料查找过程中起到重要作用,帮助人们从海量数据资源中找到自己想要的信息。伴随网络技术的推广与发展,目前文献检索网站数据存储量迅速增长,造成检索过程计算量增加。采用快速排序算法,可以有效筛选出与用户需求匹配度较高的文献,方便用户使用,提高运算效率,并利用计算机模拟实现。     

连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。     

星上Clos交换网络的分治调度算法

针对星上交换的特殊要求,该文提出了基于MSM (Memory-Space-Memory)型Clos交换网络的分治调度算法。通过引入冲突域的概念,分治调度算法将MSM型Clos网络中的匹配问题分解成在冲突域内为每个中间级模块选择信元的问题。该调度算法限制了冲突发生的范围,简化了调度的复杂度,并且具有硬件实现简单、能适应多种业务等优点。仿真表明,分治调度算法在各种业务模型下的吞吐率都能接近100%,并具有良好的时延性能,满足了卫星通信的要求。     

一种基于分治的三维匹配问题DNA计算算法

 本文基于Aldeman-Lipton模型的生物操作与粘贴模型的解空间,提出一种三维匹配问题的DNA计算新模型;同时基于此模型和传统计算机中分治策略,提出一种求解三维匹配问题的DNA计算新算法.将提出的算法与已有文献结论的对比分析表明:本算法将穷举算法中的DNA链数从O(2ⁿ)减少至O(2^n/2)≈O(1.414ⁿ),同时生物操作数由O(n²)减少至O(15n+30q),测试试管数由所需的O(n)减少至O(1),最大链长由O(15n+45q)减少至O(15n/2+45q).因此,本算法理论上在试管级生化反应条件下能将求解三维匹配问题的规模从67(2⁶⁷≈10²²)提高到134(67×2=134).同时,与传统的穷举搜索算法相比,该算法具有高效的空间利用率及容错技术的优点.     

改进的隐私保护关联规则挖掘算法

数据挖掘技术可以从收集到的大量数据集中挖掘出潜在的知识,这就可能把涉及到个人隐私的信息挖掘出来,从而产生了隐私保护下的数据挖掘。首先分析了国外学者Rizvi提出的隐私保护关联规则挖掘算法MASK,然后使用分治策略对MASK进行了改进。时间复杂度分析和实验结果均表明,对MASK算法的改进是有效的。     

利用分治技术的智能推理

一、引言“分治”技术是一种分解-合成技术,即对于复杂的不能直接求解的问题,将该问题分割成几个子问题,分别求解子问题,然后合成子问题的解,以获取整个问题的解。若分割出的子问题仍不易求解,则继续分解子问题,一直到可以直接求解为止。因此,这是一个递归模式。同样,人工智能在求解难题时,常常将难题分解为较为简单的子问题,然后合成各个子问题的解决方案,形成一个整体方案。本文通过描述分治技术在基于类比推理、基于事例推理以及基于原型推理的应用,表明了该技术在智能推理中的有效性和灵活性。     

国企内部也要抓大放小,抓优放劣：——兼谈我厂“切块分治”的探索与实践

江泽民总书记在党的十五大报告中指出：“要着眼于搞好整个国有经济,抓好大的,放活小的,对国有企业实施战略性改组”。国有企业应该全面、正确、深刻地领会报告精神,结合自身实际,在企业内部抓大放小、抓优放劣。在这方面,衡阳有色冶金机械总厂起步较早,通过将全厂...