求解指派问题的一次性分配算法

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。     

基于栈结构的孔明棋算法研究

孔明棋是一种玩法简单,但其中变化无数的益智游戏。对孔明棋求解问题进行分析,提出了基于回溯思想的递归和非递归算法,运行结果表明了算法的有效性。文章还围绕栈在存储数据、消解递归等方面的应用对两个算法的优缺点进行了比较分析,递归算法结构清晰,但递归调用次数多;而非递归算法借助程序栈,将程序向循环转化,降低了时间复杂度,但算法难以分析和理解。因此在求解实际问题时可以采用递归思想来分析,然后借助栈用非递归来实现算法。     

汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).     

指派问题的置换矩阵解法

指派问题是一类特殊的约束满足问题(CSP),其变量的论域是N×N矩阵中所有坐标,要求从中选择N个元素并满足约束条件:所选出的坐标不在同行、同列。指派问题的求解可以使用回溯算法或匈牙利法。本文提出了一种求解指派问题所有可行解的置换矩阵算法,并在此基础上对含不明条件的指派问题也给出的相应的求解方法。     

分治递归算法的解题能力

为了培养学习编程的逆向思维，运用分治思想的递归算法提高解决问题的能力，理解分治和递归的关系，掌握递归算法解决问题的条件和原理是十分必要的。从提出问题、分析问题、抽象问题的特征、解决问题和分析递归算法的局限性的过程，运用比较法比较迭代与递归之间的关系，结合具体问题，对理解递归算法解决问题给出了有效的方法。用分治的递归方法求解问题，其结构简单，可读性强，但是递归算法理解起来有一定难度，研究了递归算法的特征、递归与分治之间的关系、递归与迭代之间的关系，根据时间和空间复杂度，给出了递归算法的深度建议。实践的结果证明，采用这样的方式，能够帮助读者理解逆向思维和分治思想的本质，提升运用递归算法解决生活和学习中的问题的能力。     

一种求解企业员工指派问题的离散状态转移算法

员工指派问题是运筹学中的一类整数规划问题,为了寻找最佳的员工指派方案,使得完成所有任务的总成本代价最小,本文研究了一种新的离散状态转移算法.在一次状态转移的基础上提出了二次状态转移的概念,从而扩大了候选解集的范围,并提高候选解集的多样性.为了克服算法在迭代后期更新缓慢的缺点,提出了停滞回溯策略,即当算法陷入局部最优解时进行回溯操作,从历史停滞解中随机选择一个更新当前最优解.通过与模拟退火算法进行测试比较实验,证明了本文所提出算法的有效性,同时该算法提高了求解员工指派问题的成功率与稳定性.     

分支限界法求解实际TSP问题

提出一种基于分支限界思想来求解实际TSP问题的算法,并着重介绍上下界的计算.下界值是根据当前路径来计算的,简单易行且占用空间少.上界只计算一个全局的上界值,计算过程中用到实际TSP问题的一个特点——三角不等式性质,求得的值不超过最优值的1.5倍.实际TSP问题另一个特点是对称性,对称性可使解空间树缩小一半,进一步加速搜索过程.提出的求上界和求下界的算法是独立,完全可以分割开来,但是通过例子可以看出将这两种方法用分支限界的思想结合起来是行之有效的,可大大加速解空间树的搜索.     

物种生灭算法的改进策略

物种生灭算法（Species Explode and Deracinate Algorithm，SEDA）是一种简单、高效的群智能优化算法。为了进一步提高SEDA算法的寻优速度、解的质量，首先，通过一种无排序筛选幸存物种的递归算法，提出了基于递归筛选的SEDA算法，减少了SEDA算法的时间复杂度，提高了算法的寻优速度；其次，通过引入衍生趋势的方法，提出了基于衍生趋势的SEDA算法，提高了SEDA算法对复杂、难以寻优的优化问题解的质量。三个测试函数的仿真结果表明，改进的方法具有更小的时间复杂度，能够有效改善SEDA算法解的质量。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

解读“匈牙利法”——对《“匈牙利法”存在的问题及改进方法》一文的质疑

“匈牙利法”是目前为止被人们认为求解指派问题最简单有效的方法,但有些人对此算法认识不全面,产生了一些误解。文章详细解读了“匈牙利法”及其求解步骤,并通过两个实例详细演示了“匈牙利法”的具体求解过程,以助学习者更好地理解和运用“匈牙利法”来解决实际问题,同时也澄清了对“匈牙利法”的某些错误认识。为保证求解结果的正确性,利用Excel提供的“规划求解”模块对求解结果进行了验证。     

分配问题的计算机方法

分配问题是一个组合优化问题。传统计算机求解分配问题的方法中，既有枚举法、最小元素法、行（列）扫描法和损益分析等算法，也有如分枝限界法、匈牙利算法及其改进算法。本文在对这些计算机方法进行分析和仿真的基础上，将一个随机并行算法用在解决分配问题上，并且对各种方法的运行结果进行了比较。     

基于Listwise的新型排序算法

基于Pairwise的排序算法得到的判别式模型准确率较低。为此,提出一种基于Listwise的新型排序算法。采用判别式模型,将基于1-slack的支持向量机作为算法框架,定义算法的优化目标。由于该目标的约束条件太多,难以直接优化,因此使用割平面法求解。对于算法内部寻找最违背排列的子问题,将其看作一个线性指派问题,采用匈牙利法求解。在基准数据集上的实验结果验证该算法的有效性和稳定性。     

异构无线网络密集部署场景下高效网络接入及频谱分配

如何在异构网络重叠覆盖场景下实现动态耦合频谱资源高效分配以满足用户流量需求是下一代无线通信网络的重要挑战。综合考虑网络域频谱属性差异化及用户域需求多样化问题，以用户获得总带宽最大化为目标，将频谱资源分配建模为非线性多约束条件0-1整数规划问题，并设计了两种求解方法。首先，设计了一种基于改进匈牙利算法的化简方法，该方法通过对约束条件进行化简，将复杂模型转化为标准形式0-1规划，并通过对匈牙利算法进行改进，有效求解了该复杂的频谱分配问题；其次，设计了一种改进的遗传算法，把主网络干扰约束及次用户需求融合进适应度评估中，以修正不符合要求的基因，并利用精英主义思想保留优秀个体，以进化迭代到优秀个体。最后通过实验对提出的方法与粒子群优化方法的性能进行对比分析，实验结果显示化简方法具有较大的效率优势，而改进遗传算法可得到更大的带宽。     

Scheme语言递归问题的实现

对于八皇后问题，曾有许多人采用不同的程序设计语言和不同的算法加以解决，本文采用函数式程序设计语言Scheme的递归算法来解决八皇后的问题。     

On the satisfiability of authorization requirements in business process

Satisfiability problem of authorization requirements in business process asks whether there exists an assignment of users to tasks that satisfies all the requirements, and methods were proposed to solve this problem. However, the proposed methods are inefficient in the sense that a step of the methods is searching all the possible assignments, which is time-consuming. This work proposes a method to solve the satisfiability problem of authorization requirements without browsing the assignments space. Our method uses improved separation of duty algebra (ISoDA) to describe a satisfiability problem of qualification requirements and quantification requirements (Separation of Duty and Binding of Duty requirements). Thereafter, ISoDA expressions are reduced into multi-mutual-exclusive expressions. The satisfiabilities of multi-mutual-exclusive expressions are determined by an efficient algorithm proposed in this study. The experiment shows that our method is faster than the state-of-the-art methods.     

A new algorithm of bearings-only multi-target tracking of bistatic system

Much research mainly focuses on the batch processing method （e.g. maximum likelihood method） when bearings-only multiple targets tracking of bistatic sonar system is considered. In this paper, the idea of recursive processing method is presented and employed, and corresponding data association algorithms, i.e. a multi-objective ant-colony-based optimization algorithm and an easy fast assignment algorithm are developed to solve the measurements-to-measurements and measurements-to-tracks data association problems of bistatic sonar system, respectively. Monte-Carlo simulations are induced to evaluate the effectiveness of the proposed methods.     

多Agent 主从粒子群分布式计算框架

面向大规模复杂优化问题,提出了一个基于并行粒子群优化的分布式Agent计算框架.框架中使用一个主群(master swarm)来演化问题的完整解,并使用一组从群(slave swarm)来并行优化一组子问题的解,主群和从群通过交替执行来提高问题的求解效率.采用异步组结构,主群/从群中的各类Agent共享一个解群,并通过相互协作,对解群进行构造、改进、修补、分解和合并等演化操作.该框架可用于求解复杂的约束多目标优化问题.通过一类典型运输问题上的实验,其结果表明,所提出的方法明显优于另外两种先进的演化算法.     

On an assignment problem with side constraints

We describe a branch and bound algorithm for an assignment problem subject to a special set of side constraints. The problem has application in the design of tool carousels for certain flexible manufacturing systems. The resulting model represents a special case of the restricted facilities layout problem in which it is forbidden to locate any facility in certain zones. The bounds for the algorithm are generated by relaxing the side constraints and using the Hungarian method to solve the resulting assignment problem. Partitioning in a manner similar to subtour elimination for the travelling salesman problem leads to encouraging computational results.