利用改进的回溯算法求解3着色问题

介绍了3着色问题，阐述了回溯算法与静态搜索树，提出了动态搜索树的概念，给出了一个基于动态搜索树的回溯算法，以3着色问题为例，说明该算法所用时间少于静态搜索树方法．     

PRO树及其剪枝问题的研究

介绍了静态和动态两种ＰＲＯ树的生成及为求出目标解在ＰＲＯ树上搜索、匹配和回溯的过程．针对截断谓词可能出现的各种位置，着重讨论了两种ＰＲＯ树的剪枝，同时总结了截断谓词在剪枝时所遵循的两条原则     

基于动态一致性增强技术的Job Shop调度算法研究

为降低CSP调度算法的计算复杂度和减少搜索过程中回溯发生概率,采用动态一致性增强技术来预先修剪和过滤搜索空间。通过基于顺序约束的动态一致性增强算法,将当前搜索状态下的工序取值结果沿工艺路线向上下游工序传播,从而有效修剪了同一零件内剩余待调度工序的开工时间窗;针对Job Shop调度问题中最难满足的能力约束,采用基于能力约束的动态一致性增强算法,根据当前搜索空间的工序取值对竞争同一机床的其它剩余待调度工序的开工时间窗实施修剪。仿真实验证明:这2种方法的综合运用可以显著提高CSP调度算法的搜索效率,从而为CSP调度算法求解大规模Job Shop调度问题提供可能。     

大型水陆两栖飞机海上最优搜索航路规划算法

针对大型水陆两栖飞机的飞行特性和远海搜索救援能力不足的问题,研究设计了海上最优搜索航路规划算法,使其能够在最短时间内完成规定海域的搜索。针对大型水陆两栖飞机的特性参数,结合漏搜率和复搜率的要求指标,将原搜索航路规划问题转化为格点的离散规划问题。本文最优搜索航路规划算法在动态规划的基础上引入回溯路径指标,能够满足复搜率的要求。数值仿真分析结果表明:相对于传统的搜索路径方法,采用本文算法求得的最优航路方案具有更好的性能指标。     

校园网多径混合路由算法

针对目前校园网路由算法中最小生成树的计算和最短路径的生成存在速度慢和效率低的问题,提出了一种多径混合路由算法.结合了静态路由算法和动态路由算法的优点,减少了计算最短路径树时的总执行时间,当网络中链路有新的权重变化时,它使用多径信息来创建最短路径树,并且能够根据网络中链路权重变化的位置来决定使用静态路由算法或者是动态路由算法.与现有的迪杰斯特拉(Dijkstra)算法、动态Dijkstra算法和混合最短路径树算法进行了对比实验,结果表明多径混合路由算法降低了最小生成树的计算时间.在校园网中使用多径混合路由算法可以加快了网络路由的收敛,提高了网络的性能.     

基于动态Internet的群组命令传输算法

由于Internet具有动态特性,使得Internet尽力而为的服务模式在传输群组命令时,容易产生无效(过期)路径. 对此,提出群组动态遗传算法. 该算法分别从静态搜索和动态搜索两个角度考虑无效(过期)路径问题. 其主要优势在于解决传统遗传算法在动态环境下无法收敛问题. 实验验证了该算法相对于当前一些经典算法在支持群组命令传输方面具有较好的性能.     

基于图论的动态频谱分配策略

针对颜色敏感图论着色频谱分配算法一般只应用于静态网络的问题,基于频谱分配的图论模型及颜色敏感图论着色频谱分配原理,提出了一种改进的最大化系统总收益规则下的动态频谱分配算法,并进行了仿真实验,对比分析了原有算法与新算法的性能.仿真结果表明,改进的算法虽然使认知网络总效益有所下降,但大幅度减少了时间开销,提高了系统的时效性.     

图着色问题的蚂蚁算法研究

随机蚂蚁着色算法是根据蚂蚁算法的搜索机制和反馈功能提出的解决图着色问题的新算法,继承了蚂蚁算法快速收敛以及跳出局部最优解的优良特性,结合传统图着色算法的着色思想,提出了逆序蚂蚁着色算法和贪心蚂蚁着色算法,进一步提高了求解质量,加快了收敛速度.实验结果证明了逆序蚂蚁着色算法和贪心蚂蚁着色算法的优良特性.为了合理选取蚂蚁着色算法参数,进行了大量随机图着色实验分析,得出了关键参数的最佳取值范围.     

一种构建严格平衡二叉搜索树的非递归算法

针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。     

改进型OVSF码随机动态分配算法

针对WCDMA（Wideband Code—Division Multiple Access）系统下行链路随机动态码分配算法存在码阻塞概率大、进行最小代价分支搜索信令开销大的问题,提出了一种改进型动态码分配算法。该算法采用搜索最小代价函数值、以邻近原则进行码树重排、释放同级码字中具有最大代价函数值的码字策略。仿真结果表明,改进型动态码分配算法码阻塞概率低于随机动态码分配算法的码阻塞概率。在业务量为16Erl时,改进型动态码分配算法使系统码阻塞概率降低18．37％,同时该算法能有效降低系统的复杂度。     

一种解寇克曼问题的计算机算法

寇克曼 (kirkman)于 1 847年提出了著名的“1 5个女生问题” ,本文提出一种解该问题的基于随机搜索和回溯的计算机算法。该算法已在微型机上实现 ,计算结果表明算法是有效的。在任意给定第 1天的安排后 ,该算法均能找出其它 6天满足要求的 3人组安排     

基于人工智能的城市交通系统关键技术研究

通过对城市智能交通系统的数据组织形式、数据结构的分析 ,确立了以四叉树形式组织空间信息的方法 ,以及知识库中规则表示形式 ,提出了用启发式图搜索策略 ,改进逐层回溯策略的方法 ,建立并实现了交通图中求解最优路径的算法 .     

Improved scheme for spectrum allocation in cognitive wireless sensor networks

In order to effectively allocate the idle spectrum and improve spectrum utilization of cognitive wireless sensor networks, it is necessary to design an efficient spectrum allocation algorithm. Aiming at the problem of spectrum allocation in cognitive wireless sensor networks, an improved method for spectrum allocation is suggested. A new chaotic dynamic clonal evolution algorithm is designed. Then the graph theory coloring model is established with the corresponding fitness function derived. Traditional evolutionary algorithms have the problem of premature convergence, so chaotic operators, adaptive operators and cloning operators are added to the traditional evolutionary algorithms to accelerate the convergence of the algorithm. The chaotic dynamic clonal evolutionary algorithm is compared with the simulated annealing algorithm and the ant colony algorithm by simulation. The simulation results show that compared with the ant colony algorithm and the simulated annealing algorithm, the chaotic dynamic clonal evolution algorithm can effectively improve the global search ability, and significantly improve the network benefit value of spectrum allocation. The results also show that the proposed chaotic dynamic clonal evolution algorithm can make full use of existing spectrum resources and improve the system throughput.     

Polynomial algorithm of limited propositional deduction

For the problem of propositional satisfiability a polynomial algorithm of limited propositional deduction is proposed which can be viewed as a sort of boolean constraint propagation mechanism. It can be embodied in a backtracking search program for propositional satisfiability problems to make search efficient. The efficiency is gained in two ways: One is to use the algorithm to derive literals so as to overcome the ambiguities in search. The other is to exploit the consequence sets of unbound atoms generated during limited deduction as a heuristic measure for possible choices. The experiments have shown remarkable improvement in reducing search space. Project supported by the “863” High-Tech Program of China.     

图着色问题的新遗传算法

针对遗传算法求解图着色问题需多次产生初始种群的问题,提出了一种改进算法．该算法采用比较机制,淘汰不可行的基因,然后使用动态的适应度函数,使得有效个体以较大的概率存活到下一代种群中,从而达到无需多次产生初始种群的目的．与传统框架下的算法相比,新算法求得最优解的时间至少缩短了51％,且具有从一个局部最优解快速跳到下一个局部最优解,最终收敛到全局最优解的优点．     

带回溯线搜索的新锥模型信赖域算法

结合线搜索方法计算量小的优点和信赖域算法很好的收敛性,将回溯线搜索应用到新锥模型自适应信赖域方法上构造了一类新的算法,并证明了该算法具有全局收敛性。初步的数值实验表明该算法是可行的。     

机组组合优化问题的穷举算法研究

提出一种解决机组组合优化问题的通用穷举算法,把M台机组组合优化问题转化成从M个数组中各取一个数并且这M个数之和等于一个给定值的数学问题,在此基础上,利用递归回溯的方法搜索每个可能的组合.试验结果表明,该算法能够找出任意台机组在任意技术出力范围内的所有的组合方案,不会产生漏解.应用于经济调度问题时,以煤耗量为目标函数,证明该算法能够得到最优解.最后,分析了该算法的复杂性.