分支定界 分支定界英語Branch and boundBB是用于离散优化组合优化以及数学优化问题的算法设计范式分支定界算法可以视为一种对可行解进行穷举的算法但是和穷举法所不同的是分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界如果界限不比目前最佳解更好那么该分支就会被舍弃从而节约了大量的时间分支定界算法非常依赖合适的上界或下界如果无法找到合适的界限该算法将会退化为穷举法 该方法最初是由阿尔萨兰德和艾莉森哈考特在年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的目前已成为解决NP困难优化问题最常用的工具分支定界一词最早出现在解决旅行推销员问题的时候