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

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

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

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

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

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

基于MAC的动态回溯算法优化

针对基于MAC的动态回溯算法在求解约束满足问题时, 不仅需要大量空间存储删除解释, 而且回溯机制过于复杂, 对经典的删除解释及动态回溯算法的回溯机制进行优化, 优化后的动态回溯算法减少了存储删除解释的空间, 并可仅使用一次回溯操作返回到可能导致冲突的关键变量. 在最差情况下, 存储删除解释的空间复杂度由O(n²d)改进为O(nd+n²). 通过结合restart技术使优化后的动态回溯算法成为完备算法. 实验结果表明, 优化后的完备动态回溯算法在大部分问题求解中, 整体效率明显优于标准回溯算法.     

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

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

r-排列非递归生成算法及应用

提出一种利用回溯法生成r-排列的算法.该算法使用栈和队列,并引入标记已选元素的方法,避免了回溯时的重复选择.生成的r-排列具有分组和对称性,且符合字典序.此算法也能生成全排列.利用该算法提出了r-组合生成算法,分析了它们的时间和空间复杂度,并介绍了r-排列和r-组合算法在任务安排问题中的应用.     

一种基于规划路标的增量诊断方法

提出一种基于动态路标的启发式方法,改进因候选诊断存在而导致的诊断回溯问题.通过离线标记和在线的动态路标,在候选诊断路径集合中选择当前最优诊断结果,推理增量诊断的可扩展状态;在线过程中,根据在线诊断结果和回溯节点调整路标,提高整体增量诊断结果效率,从而快速得到在线的诊断结果.该启发式方法减少了增量诊断中的回溯次数,在提高诊断效率的同时,也提高了局部诊断的精确度.     

求解一类组合问题的智能回溯法

本文给山一种求解一类组合问题的智能回溯法及其应用条件。若用智能回溯法求解顶点着色等问题将比经典回溯法快若干倍。     

自忆模式中回溯时间积分格式有效性的数值试验

采用Rossby-Haurwitz波函数作初始场,利用准地转正压模式和以其作动力核导出的自记忆模式,分别运用普通中央差格式和回溯时间积分格式进行数值预报试验.结果表明,回溯格式能减小预报误差约2个量级;且其误差不随时间步长的增大而增加.因此,回溯时间积分格式可以提高预报精度,延长预报时效,并减少预报量.     

一种改进的分布约束优化算法MULBS+

完备算法虽然能够求得分布式约束优化问题最优解,但要消耗大量资源及时间,相反,非完备算法通过求得次优解来提高效率.MULBS作为一个有效的非完备算法,虽然在求解质量和时间上有所提高,但在解决赋值冲突时采用的回溯策略及并行搜索方面存在不足.通过对该算法的深入分析,本文针对上述问题进行了改进,提出其改进算法MULBS+.通过在回溯策略中引入最小冲突选择机制,以及在约束图密度较大时采用基于动态子图划分的并行搜索策略,进一步提高了算法的性能.实验表明,该算法除增加一定的通信信息外,其执行时间及求解质量均优于原算法.     

一种改进的基于二叉树的防碰撞算法

针对RFID系统中基于二叉树的标签防碰撞算法存在识别时间长、通信数据量大的问题,提出了一种改进的算法.算法充分利用上一次查询的信息,标签根据碰撞位先后应答读写器以减少碰撞的发生.读写器检测到接收的数据中有2个碰撞位即停止接收后续数据,以减少冗余数据的传输.算法将识别范围内所有标签进行分组,并且整个识别过程采用后退策略.仿真结果表明,提出的算法具有较高的识别效率.     

结合Separator的约束满足问题树分解方法

基于树分解的回溯搜索算法, 结合separator分解算子提出一种新的搜索算法BTD⁺-MAC. 该算法在搜索时, 优先选择separator中的变量进行相容性检查和实例化, 由于树宽度的减小能提高约束传播的效率, 进而提高问题求解效率. 对几组benchmark问题进行测试, 测试结果表明, 该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.     

基于最省功的物流配送路径计算

物流配送路径的合理选择将在很大程度上提高运输效率、节约成本。在人力运输为主的配送方式中,将运输路径长度与配送物品重量相互结合考虑,能实现最有益于配送员工作的最省功配送线路。程序在最小哈密尔顿回路问题的基础上,加入物品重量这一参数,通过回溯法实现最优路径的计算。     

基于启发式搜索算法的无人机航迹快速规划

基于无人机导航系统的自身特点,无人机在导航过程中会出现无法精确定位的情况,从而产生定位误差。如果不能及时校正随时间累积的定位误差,会使无人机无法到达预定目的地,从而导致飞行任务失败。为避免这种情况的发生,本文研究了考虑定位误差的无人机航迹快速规划问题。以航迹距离最短为目标,考虑定位误差校正约束与航迹约束,建立了混合整数规划模型。根据深度优先搜索算法与回溯算法的特点,设计了启发式深度优先搜索+回溯算法来求解问题,并在此算法基础上加入模拟退火机制对解的质量进行优化。以某飞行区域的数据为例进行仿真实验,结果表明启发式深度优先搜索+回溯算法可以快速有效地求解考虑定位误差的无人机航迹规划问题。     

基于BIT位运算的N皇后问题解法

皇后问题是一经典的回溯算法问题,本文使用B IT位运算对非递归的回溯算法进行优化,取得了较好的效果,对其他类似问题的算法的优化有一定指导意义。     

截断谓词的研究与分析

回溯机制是Visual Prolog程序运行的重要机制,是获取所有可能解的一种方法.但在实际问题的解决过程中,有时却不需要回溯.Visual Prolog提供的内部谓词-截断谓词“!”可以用来阻止回溯,而且从某种意义上讲,只有学会了截断谓词的使用,才能自由驾驭Prolog.文章主要结合实例对截断谓词的作用以及使用方法进行了详细介绍,并指出了截断谓词的作用本质上是删除满足一定条件的回溯点。     

基于DFS-回溯算法的公交网络限时免费换乘优化模型求解

基于青岛市“限时免费换乘”政策理念,建立费用与时间、换乘次数的关系模型,采用深度优先遍历与回溯相结合的算法,寻找限定时间内最短时间与超限时条件下最低费用路径,给出起讫点间的最优路径方案,结合车站智能诱导发布平台对算法进行验证。运行结果表明,DFS-回溯算法在数据规模较大的情况下,比蚁群等全局搜索算法效率高,可既快又准的找到最优路线;基于该算法的最佳路径模型方案,可准确的为乘客提供最大选择便利性,实现公共交通资源利用最大化。     

HTN规划中面向多计划生成的顺序任务分解算法

顺序任务分解算法(OTD)是层次任务网规划(HTN)中的一种高效求解算法.由于算法中的计划生成采用一次性回溯机制,每次求解过程只能产生一个可行计划.文中提出了一种能够快速生成多个可行计划的回溯算法.该算法采用分段回溯的计划生成机制,充分利用了求解过程中生成的局部解序列,从而能够一次性地快速生成多个可行计划,为寻求优化的计划和进行计划的评估提供更为有效、灵活的支持.