摘要：时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。

摘要：分支限界算法是一种在问题的解空间树上搜索问题的解的方法,主要采用广度优先或最小耗费优先的方法搜索解空间树,其核心思想就是"剪枝"。首先提出了分支限界算法的一般策略与实施步骤,然后以电路板布线问题为实例,设计并实现该问题的算法,经过实验数据验证了其性能,进而反映了分支限界算法的高效性。

摘要：提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.

摘要：为了解决测试用例自动生成中等式约束的求解问题,提出一种加入等式处理策略的分支限界搜索算法.首先将线性代数中判定线性方程组是否有解的方法引入分支限界测试用例生成框架之中;然后在已有算法模型的基础上提出集成等式处理分支限界搜索算法,以支持多种变量类型的等式处理;最后将等式约束分为等式无解、等式多解和等式唯一解三大类进行处理,包含了等式约束求解问题的所有情况.实验结果表明,文中算法可以实现对一部分不可达路径的检测,在很大程度上减少测试用例生成的时间并提高覆盖率;对大工程的测试以及同开源约束求解工具Choco的对比实验,也证明了该算法可以提升测试效率.

摘要：针对不同任务之间通常存在偏序关系这种实际情况,提出了基于偏序任务的社会网络合作问题(collaboration problem in social networks based on tasks with partial ordering relations,CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集,使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题,然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_***_BBS算法不仅输出有效的团队,而且能给出团队成员的具体任务分配以及每项任务的开始时间.真实数据上的实验结果表明:HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.

摘要：随着航天科技的飞速发展,逐渐出现了由多种异构卫星组成的卫星集群。相比于传统的卫星系统,卫星集群具有规模大、平台多、载荷异构的特点,传统的卫星任务规划方法难以适用。针对卫星集群任务规划中的关键问题——面向任务的卫星Agent团队构建问题,建立了数学模型,提出了基于分支限界的精确搜索算法,并对其时间复杂度进行了分析。针对精确算法时间复杂度较高的缺点,引入了启发式剪枝机制,并按照任务集合排序策略的不同设计了3种启发式卫星团队构建算法。最后,通过多组实验分析了卫星团队构建精确搜索算法与启发式剪枝搜索算法的性能,验证了我们提出算法的有效性和实用性。

摘要：为提高MaxSAT完备算法剪枝率和运算效率,分析失败文字检测寻找冲突集的过程,提出扩展失败文字检测方法。通过延长失败文字搜索冲突的路径,形成搜索1步、2步和任意步的递进失败文字检测方式,实现改进的MaxsatzEF算法。实验测试了MaxSAT国际竞赛4个类别的500多个算例,实验结果表明,递进失败文字检测方法找到了更多独立冲突集,可有效提高算法的下界,大幅缩短复杂算例的运行时间。