湖 北 经 济 学 院 计 科 系 第五章 回溯法5.1 回溯算法基本思想n 回溯法是一种通用的解决问题的办法，本质上就是一种穷举，并且是一种避免重复的穷举。n 所有回溯算法与走迷宫具有相同的本质。1湖 北 经 济 学 院 计 科 系 迷宫问题回溯：往回退，追根溯源。求解的目标: 确定每一个十字路口的选择，最后走出迷宫。2湖 北 经 济 学 院 计 科 系 问题的解空间树n 问题的解向量：回溯算法希望一个问题的解能够表示成一个n 元式(x1,x2,xn) 的形式。n 解空间树：由解元素x1,x2xn 取不同值所构成组合( 或排列) 序列，迷宫中xi 表示第i 个十字路口做出的选择。Eg. n=3 时的0-1 背包问题解空间树为左图所示二叉树显式约束：对分量显式约束：对分量xixi的取值限定。的取值限定。隐式约束：为满足问题的解对不同分量之间施加的约束。隐式约束：为满足问题的解对不同分量之间施加的约束。x1x2x33湖 北 经 济 学 院 计 科 系 n 回溯算法的本质：确定问题的解空间树后，深度优先遍历此空间树。但是往往问题的解空间树是无法完全存储的（eg ），所以遍历有它的特点。n
