求解组合优化NP问题的分支追溯法

摘要：

NP问题是目前研究最广泛的组合问题之一。本文提出了一种解决组合配对问题的新搜索算法——分支追溯法(Branch and Ascend,BA算法)及其改进算法。这一算法适用于学校招生、企业招员、比赛选拔等多种场合的面试组分配问题。以高校自主招生为例进行了仿真实验。结果表明,这一新算法在解的计算效率、可行性以及最优性方面都具有较好的综合性能。

关键词： 分支追溯法 面试组分配 NP问题 求解组合

作者: 夏旻 严晨 娄晓娜

作者单位: 上海东华大学信息科学与技术学院,201620

会议类型: 国内会议

会议名称: 上海科协第五届学术年会“信息化与工业化”上海研究生学术论坛

会议地点: 上海

会议语种:中文

页码: 144-146

在线出版日期: 2007-09-24（万方平台首次上网日期，不代表论文的发表时间）