摘要：讨论了回溯算法的形式模型 ,提出了刻画回溯的一些数学概念 ,以隐式搜索为背景提出了状态空间概念 ,给出了分别以邻接方阵和邻接表形式表示的有向图所对应的状态空间 ,从而说明显式搜索是隐式搜索的特例 ,通过展开空间概念揭示了问题求解的不同要求所对应的不同数据结构 ,提出了通用回溯算法 ,并以 N皇后问题、稳定婚姻问题、点着色问题、子集和数问题、跳马问题、最长路径问题和强连通分支问题等多种算法设计问题为例讨论了通用回溯算法的应用 .该文结果有助于扩大回溯算法的使用范围 ,提高回溯算法实现的正确性和效率 .

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

摘要：该文介绍了两种Viterbi译码器回溯译码算法,通过对这两种算法硬件实现结构上的优化,给出了这两种算法的FPGA实现方法,比较了两种实现方法的优缺点。最后将其应用在实际的Viterbi译码器设计上,验证了算法实现的正确性。

摘要：电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-难问题.文章首先研究了该问题良好的数学性质并给予相应的证明,其中包括可以批量确定某些设施一定开设或一定不开设的性质,利用这些性质降低问题的规模,从而降低问题的求解难度;然后设计了上界子算法,下界子算法,分配子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解一个示例来进一步阐述文章算法的原理和执行过程,结果表明所提出的算法能够有效地降低时间复杂度.

摘要：无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是组合优化中经典的NP-Hard问题之一。针对UFLP的变形问题之一,即带惩罚的无容量设施选址问题(Uncapacitated Facility Location Problem With Penalties,UFLPWP),研究了UFLPWP的数学性质,其中包括可以批量确定某些设施一定关闭的性质,并进行了数学证明,利用这些数学性质可以对问题进行降阶,进而缩小问题的规模。在此基础上设计了基于上、下界的回溯算法来求解UFLPWP。通过一个示例分析,进一步阐述该算法的原理。

摘要：有容量集合覆盖选址问题是组合优化中的一个经典的NP-Hard问题,在许多工程领域和科学领域中的应用十分广泛.本文将集合覆盖问题的模型应用到有容量设施选址问题中,首先研究了该问题的数学性质并给予相应的证明,利用这些数学性质能够对问题进行降阶,降低问题求解难度;然后设计了上界子算法、下界子算法和分配子算法,基于这些子算法提出了一种能够快速缩小问题规模同时能得到精确解的降阶回溯算法;最后文章通过分析和求解一个示例来进一步阐述本文算法的原理和执行过程.

摘要：总结了地图分幅需遵循的原则,并针对地图集中可变比例尺的分幅,将其定义为基于约束条件的图分割问题,用最小生成树(minimum spanning tree,MST)将制图区域关联起来,基于回溯算法对MST裁剪实现地图集的分幅。实验结果表明,所提出的方法能较好顾及地图集分幅的相关原则,满足地图集制作的要求。同时,利用该方法设计的地图集分幅工具已成功应用于《武汉市汉阳地区地名图集》等的制作,有效提高了地图设计人员的工作效率。

摘要：无容量限制设施选址问题(uncapacitated facility location problem,UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。

摘要：结合项目开发,提出了多约束条件下合理分配问题的一种解法——基于矩阵存储的回溯算法。以学生合理分班问题为例,以学生成绩和男女生比例等诸多条件作为约束,给出了算法的具体实现过程,分析了算法的时间复杂度。该算法较同类问题的回溯法,效率有很大提高,实际应用的结果表明了算法的合理性和有效性。

摘要：运筹学研究领域中的应急服务设施选址问题有许多求解模型,选取了P-中心模型进行研究,首先研究了该问题的数学性质,并给出了证明,利用这些数学性质能对问题进行降阶从而缩小问题的规模;然后在此基础上设计一个基于上界和下界的回溯算法来求解该问题;最后通过一个示例分析进一步阐述了该算法的原理,并证明了该算法能在较短时间内求得问题的最优解。