k-CARD树问题的一种降阶回溯算法  

A Backtracking Algorithm with Reduction for k-Cardinality Tree Problem

作　　者：彭大江 宁爱兵[1] 尚春剑 张惠珍[1] PENG Dajiang;NING Aibing;SHANG Chunjian;ZHANG Huizhen(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《工业工程与管理》2021年第4期125-133,共9页Industrial Engineering and Management

基　　金：国家自然科学基金(71401106);上海市一流学科建设项目资助(S1201YLXK);高等学校博士学科点专项科研基金联合资助课题(20123120120005)。

摘　　要：k-CARD树问题(k-Cardinality Tree Problem)是组合优化中一个典型的NP-Hard问题,可描述为在一个给定的无向图G中寻找一棵含k条边的子树,使得该子树权值之和最小。首先研究该问题的数学性质,其中包括可以单个减小问题规模和成批减小问题规模的数学性质;然后提出其上下界子算法;最后根据这些性质和子算法设计了一个可以大幅缩减问题搜索解空间,且保证获得全局最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程,并通过数值实验说明算法的可行性与有效性。k-Cardinality Tree Problem is a typical NP-Hard problem in combinatorial optimization.The problem is described as finding a sub-tree with k edges,costing the minimum sum weight from a given undirected graph G. Firstly,mathematical properties of the problem were proposed,which included the properties that were able to delete single node and batched of nodes from the problem;then sub algorithms for calculating the upper and lower bound of the problem were presented;eventually a backtracking algorithm with reduction that returned a global best solution based on these mathematical properties and sub algorithms was presented,which was able to reduce the scale of the solution domain quickly.At the end of the paper,an instance was illustrated to state the procedures of the algorithm. Numerical experiments were carried out to show the feasibility and efficiency of the algorithm.

关 键 词：k-CARD树 精确算法 降阶算法 上界 下界 

分 类 号：O223[理学—运筹学与控制论]