回溯算法在多约束分配问题中的应用

以学生宿舍合理分配问题为背景,对分配中所涉及的学生高考入学成绩、生源地、宿舍类别等诸多约束条件进行充分分析和探讨,给出了解决这类问题的一种新的有效算法--基于矩阵存储的回溯算法,并给出了算法的实现细节.在此基础上,讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,说明了该算法在多约束分配问题中更具合理性和有效性.     

基于考生比例的考场编排问题的分治算法

根据高考考场编排的一般要求和约束条件,建立了相应的数学模型,提出了基于考生比例的考场编排问题的分治算法,给出了算法的具体步骤,分析了算法的复杂度,验证了算法的合理性和有效性.实验结果表明,该算法能有效控制考生的分布,编排过程完全可以控制,最大程度地避免了前后左右相邻考生属同一中学,编排结果达到了比较理想的均衡状态.该算法速度快、效率高、易于实现,继承性强,很容易推广到其它类似问题的求解.     

回溯算法及其改进型的分析与比较

针对适于回溯算法求解的问题模型,给出了常规回溯算法及基于最小剩余值启发式的改进型回溯算法,以N皇后问题为例对二者进行了比较与分析.     

改进回溯算法实现N皇后问题求解

回溯算法是基本的算法之一,其重要的思想是不断地用限界函数去测试正在构造的部分解向量,看是否导致合法解,回溯算法通常具有较高的时间复杂度,但对于至今除了穷尽搜索仍未找到其他的方法的问题,回溯算法是较为有效的方法.介绍了回溯算法,以及以经典的N皇后问题为例,讲解了用回溯算法求解问题,并分析了其空间复杂度,介绍了求解N皇后问题的改进回溯算法.     

随机约束满足问题的回溯算法分析

提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型 的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的 平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.     

基于回溯算法的蜂窝通信系统最优信道分配

介绍了k=(k1,k2)条件下蜂窝通信系统的最优信道分配问题,并通过回溯算法得到了有限基站信道分配的最优解,并由此推出无限蜂窝通信系统信道分配最优解。     

基于回溯法的排课算法

多年来,排课算法是众多专家学者感兴趣的课题,同时也取得了诸多研究成果,诸如基于图论的排课算法、利用人工智能进行排课等。但这些算法都相对复杂,在软件实现上有一定的难度。该文利用回溯算法来解决排课问题,方法简单,易于软件实现。     

基于回溯法的排课算法

多年来,排课算法是众多专家学者感兴趣的课题,同时也取得了诸多研究成果,诸如基于图论的排课算法、利用人工智能进行排课等。但这些算法都相对复杂,在软件实现上有一定的难度。该文利用回溯算法来解决排课问题,方法简单,易于软件实现。     

一类工作调度问题的回溯解法

回溯法是解决组合搜索问题的重要方法,该方法的搜索通过一个多阶段的确定过程来实现,在每一阶段都需要从一些选择中选择一个分支,一旦发现前面的选择不可能获得一个解,则算法进行回溯,即重新回到刚搜索过的选择点,并选择该结点另一个没有被试过的分支,如果该点处所有的分支都已试过,则算法回溯到该结点之前被选择的点.首先对一类分配调度问题进行了分析,然后提出一种基于回溯法的解决方案,并给出了算法的具体实现过程,最后对所提出算法的复杂度进行了分析.实验结果验证了方法的有效性.     

启发式回溯算法求解约束满足问题

针对一个典型的具有可变取值域的随机约束满足问题,提出了利用度启发式策略和最少约束值启发式策略来选择变量进行赋值的不完备回溯算法。该算法首先通过度启发式来确定待赋值变量的顺序,然后利用最少约束值启发式对选择的变量进行赋值,最后在有限时间内通过回溯得到变量的一组取值。用此算法对由RB模型生成的随机实例进行求解,实验结果表明,与经典的回溯算法相比,该算法具有显著的优越性。在控制参数(即约束紧度)进入相变区域时,该算法能在较短的时间内有效地找到实例的解。     

基于最小树权矩阵法的改进算法

针对最小树权矩阵法在大型网络应用中的不足，从提高算法效率方面对其进行了改进，并给出了新的算法。新算法减少了运算量，达到了快速寻找最小树的目的。通过对新算法和权矩阵法的比较，结果表明新算法具有较低的复杂度，是一种更为有效的算法。     

An algorithm for assigning multiplexer inputs

The paper describes a completely analytic method for assigning inputs to a multiplexer which involves only operations on the min term list and does not require the use of any graphical devices such as Karnaugh maps or truth tables. An example is described in detail     

基于阈值动态分配空闲灰度级的红外图像增强

分析了直方图均衡化增强算法的优缺点,并结合红外图像的特点对其简并的缺点提出了改进措施.利用全局灰度均值法得到阈值,并依据该阈值将图像灰度分为背景段和目标段,接着将空闲灰度级动态分配给背景段和目标段,最后利用局域直方图均衡化方法对背景段和目标段分别进行增强,从而达到减少简并可能性的目的.     

基于矩阵的改进的Apriori算法

针对Apriori算法的不足之处,提出了基于矩阵的算法,该算法首先将事务数据库用矩阵表示出来,并对矩阵进行处理,找出包含最多项的频繁K-项集,最后再利用矩阵找出从频繁2-项集到频繁K-1项集的所有频繁项集.通过一个实例表明了该算法的具体实现过程,并与其它算法进行比较,阐述了该算法的优缺点.该算法不但充分利用了矩阵这一工具,用与运算的方法代替了到数据库中去查找的算法,而且大大减少了候选频繁项集的产生,从而节省了计算频繁项集的时间,提高了计算的效率.     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

基于群体编码方式的遗传算法求解装箱问题

就传统装箱问题提出了一种改进的混合遗传算法.该改进的遗传算法主要通过基于群体的编码方法,将每一个箱子视为一个群体,使得在进化过程中,只对群体部分进行操作,从而大大减少了冗余,克服了传统的基于物品编码或基于箱子编码的遗传算法的不足.仿真实验结果表明,该编码方式的遗传算法比基于物品编码的遗传算法显著提高了优化效果.     

基于频繁矩阵的Apriori算法改进

针对Apriori算法效率不高的问题,提出一种基于频繁模式矩阵的方法来挖掘最大频繁项目集。算法的基本思想是:只需扫描原始事务数据集一次,将事务数据转换成压缩矩阵,矩阵中保留了项目间的关联信息,同时只存放逻辑型数据,数据挖掘只采用逻辑运算,在挖掘过程中根据条件不断的对事务数据集和候选集进行剪枝,减少了不必要的开销。当数据量较大时,在效率上有一定的优势。实验结果表明改进后的算法具有良好的性能,提高了挖掘的速度。     

基于分类矩阵的决策树算法

为了提高决策树分类的速度和精确率,提出了一种基于分类矩阵的决策树算法.介绍了ID3算法的理论基础,定义了一种分类矩阵,指出了ID3算法的取值偏向性并利用分类矩阵给出了证明.在此基础上,引入了一个权重因子,抑制了原有算法的取值偏向,并利用分类矩阵给出相应证明,同时根据基于分类矩阵增益的特点,提出了新的决策树分类方案,旨在运算速率上进行优化,与原有算法进行了实验比较.对实验结果分析表明,优化后的方案在性能上有明显改善.     

一种基于关系矩阵的关联规则快速挖掘算法

首先对关联规则挖掘问题进行了简单的回顾,然后应用关系理论思想,引入了项目可辨识向量及其“与”运算,设计了一种快速挖掘算法SLIG,将频繁项目集的产生过程转化为项目集的关系矩阵中向量运算过程。算法只需扫描一遍数据库,克服了Aprori及其相关算法产生大量候选集和需多次扫描数据库的缺点。实验证明,与Aprori算法相比,SLIG算法提高了挖掘效率。