基于矩阵存储的回溯算法在多约束分配问题中的应用探讨

学生宿舍的合理分配涉及学生高考入学成绩、生源地等诸多约束条件,在充分分析现行学生宿舍分配问题的基础上,对学生宿舍的合理分配问题进行了研究,提出了解决这类问题的一种新方法——基于矩阵存储的回溯算法．在对该算法的时间复杂度进行分析的基础上,得出了该算法较同类问题的回溯法具有更好的时间效率,在多约束分配问题中更具合理性和有效性．     

回溯法求解多约束分配问题

回溯法是解决多约束条件下合理分配问题的重要方法之一,经过认真分析研究,提出了解决这类问题的一种新的有效算法——基于矩阵存储的回溯算法,并以学生宿舍合理分配问题为背景,给出了算法的具体实现过程,最后讨论了该算法的时间复杂度,得出了该算法较同类问题的回溯法具有更好的时间效率,实际应用的结果验证了该算法在多约束分配问题中更具合理性和有效性．     

动态武器目标分配问题中改进遗传算法的元级控制

动态武器目标分配问题是一类实时性很强的优化问题.考虑分配的时间约束时,其求解算法应该是anytime算法,即算法在任意时刻都能输出合理解,且解的质量随时间增加而增加.在有限的计算时间内,anytime算法的运行时间应在综合考虑解的质量、计算代价及环境状态的变化而确定,以使解的效用最大化.该文针对有截止期的动态武器目标分配问题的anytime算法,利用元级控制过程控制算法的响应时间.在分析算法解效用影响因素的基础上,建立了时间相关的解效用公式,并基于该公式给出了一种元级控制策略.仿真结果验证了对动态武器目标分配的anytime算法进行元级控制能有效提高解的效用.     

元皇后问题回溯算法改进

回溯算法是解决N元皇后问题最有效的算法之一.在传统回溯算法的基础上,采用动态规划的思想,对算法进行了改进,改进后的算法大大降低了求解的复杂度和比较次数.文章还给出了改进算法的实现并通过理论分析和实验数据证明了算法的可行性.     

基于回溯法油管传输射孔排炮算法研究

根据油管传输射孔特点,为减少射孔枪串接时在射孔井段产生的接头总长度,对如何得到油管传输射孔最优射孔枪串接方案进行了理论分析。采用多叉树对问题进行了数学建模,为减少对多叉树的遍历次数,减少计算机运算时间,采用回溯法搜索最优解,并在回溯法的基础上对算法进行了优化。测试结果表明,油层数据简单时,回溯法与遍历法频率相当;而当油层数据复杂时,回溯法频率变高,最后设计实现了基于回溯法的排炮软件。     

一种基于分布式动态带宽分配的调度算法的研究

针对共享网络结构模型和消息模型，在分析网络控制系统调度算法特点的基础上提出了一种基于分布式动态带宽分配的调度算法，从带宽分配算法和分布式动态调度的实现方法两方面进行了详细描述。该算法可以满足不同节点的时间精度要求，有效利用了带宽，具有更高的灵活性和更好的容错能力。     

一种改进的并行频谱分配算法

针对现有动态频谱分配算法时间开销过大,用户公平性无法满足的问题,提出了一种基于用户公平性的并行频谱分配算法。该算法在基于图着色理论CSGC的动态频谱分配模型的基础上,引入HE社会模型计算出用于改进分配算法的公平系数,进而利用该系数对并行频谱分配算法进行公平性修正,最终使得动态频谱分配算法的时间开销和公平性同时得到满足,同时还详细讨论了公平系数设计对算法的影响。仿真结果表明:当用户数量固定,用户效益的波动与已有算法相比趋于平稳,用户的公平性得到满足;同时随着频带数的不断增加,算法的时间开销维持在一个较低的水平基本保持不变。     

无人机多任务区侦察时间分配模型与应用

为了合理分配无人机对多个任务区的侦察时间,提出了一种包含问题建模、求解和方案决策的无人机多任务区侦察时间分配方法。首先,建立了包含侦察收益和侦察风险两目标的无人机多任务区侦察时间分配模型,该模型属于带约束多目标优化问题;其次,提出了一种改进的基于分解的约束多目标进化算法,该算法具有简单、灵活、无参等特点,可有效求解;最后,利用优劣解距离法从非支配解集中选择最优方案。选择了6种约束多目标进化算法,在3个不同雷达强度指数条件下进行对比实验。Hypervolume指标说明约束多目标进化算法在求解该问题时优于其他算法。实验结果表明：提出的方法在求解无人机多任务区侦察时间分配优化问题中能够实现快速准确决策。     

货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。     

排课系统算法及功能的实现

文中介绍了回溯算法的基本思想和特点,分析了回溯算法在排课系统应用与其他算法的不同之处。针对排课系统理念分析,解决排课时教师时间、班级时间与教室利用时间三者之间冲突的判断方式。对排课系统的各项功能进行了设计。     

文化算法在有人/无人机协同作战目标分配中的应用

针对有人/无人机协同作战目标分配问题,基于文化算法提出一种遗传算法和离散粒子群算法相结合的目标分配方法。根据有人/无人机协同目标分配问题的特性,结合文化算法的基本框架,建立了遗传算法和离散粒子群算法的交互机制,充分利用遗传算法和离散粒子群算法对优化问题的搜索能力,改善了2种算法易陷入局部最优的缺点,对约束条件下的有人/无人机协同作战目标分配问题进行了有效求解。实验结果表明,基于遗传和离散粒子群相结合的文化算法优于遗传算法和粒子群算法,收敛速度更快,能够快速找到目标分配问题的最优解。     

一种动态交通分配的快速算法及应用

为了使得动态交通分配技术能够在大规模网络中实现,本文介绍了基于最优控制理论建立的动态用户分配模型,并针对其适用于实际的路径寻优带来的问题,提出了一种实用、快速的算法。该算法采用时间离散技术,结合静态用户分配算法,实现动态效果。减少了数据处理量,从而大大提高了运算速度。在实际应用中取得了明显的效果。     

网格中基于拍卖模型与遗传算法的作业分配

引入微观经济学与遗传工程知识,兼顾时限与成本,设计了一种网格中的作业分配方法.首先基于拍卖模型确定资源购买者和资源提供者之间的资源交易价格,然后使用遗传算法寻找作业分配最优方案.仿真结果表明,该方法是可行和有效的,不仅效用较高,而且作业对资源的分配较均衡,优于PRIMAL方法.     

全路径Logit交通分配模型的求解方法

分析了求解Logit模型的现有算法的不足,根据路网的连通特征提出了一种新的求解全路径Logit分配模型的迭代算法.给出了算法和Logit模型的等价性证明,并和经典的Dial算法进行了比较.     

一种多无人机层次化任务分配方法

针对大规模任务分配问题,为了提高任务分配的效率和合理性,提出了基于任务依赖关系和ISODATA算法相结合的任务分组方法。在任务分组基础上,从无人机负载均衡的角度出发,提出了基于资源福利的任务组级粗粒度任务分配方法,结合粒子群算法提出了任务组内的细粒度任务分配算法。通过实验仿真验证所提方法有效,且性能和灵活性较普通任务分配算法有较大的优势。     

基于多智能体深度强化学习的空间众包任务分配

针对现有空间众包中的任务分配大多只考虑单边、 短期利益和单一场景的问题, 提出一种基于多智能体深度强化学习的空间众包任务分配算法. 首先定义一种新的空间众包场景, 其中工人可以自由选择是否与他人合作； 然后设计基于注意力机制和A2C(advantage actor-critic)方法的多智能体深度强化学习模型进行新场景下的任务分配； 最后进行仿真实验, 并将该算法与其他最新的任务分配算法进行性能对比. 仿真实验结果表明, 该算法能同时实现最高的任务完成率和工人收益率, 证明了该算法的有效性和鲁棒性.     

部分波长可变WDM网中支持优先级的波长分配算法

基于链路波长占用独立性假设,改进了在部分波长转换WDM网中已有的RWA算法,提出了一种支持优先级的动态波长分配算法。该算法保证了较高优先级的光路建立请求具有较低的阻塞率,比原有算法更加适合现代光网络中不同业务请求对应不同服务等级的要求：同时该方法适用于链路上配置任意数目转换器的情况。     

广义分配问题的一种小生境遗传蚁群优化算法

提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚁群优化算法用于求解NP难的广义分配问题,以避免经典求解算法存在的易陷于局部最优的缺陷.以典型的广义分配问题——火力分配为例,对该算法进行实验,并将实验结果与其它算法进行分析比较.结果表明:新复合算法优化效率高,运行时间短,对其它的NP问题同样适用.     

遗传算法在期刊数字化任务分配中的应用

针对印刷图文信息处理专业在期刊数字化的实践过程，提出了一种自适应的实践任务分配方法，并改进遗传算法中基于排序的适应度方法，建立了任务分配优化模型，实现全局最优。实验结果表明，采用遗传算法进行项目分组实践可以使得整体制作效果获得较佳的状态，且优于同类其他方法。