作为通用解题法的回溯，虽然在方法本质上毫无高妙之处，却是解决许多NP时间复杂性问题的唯一选择。这个假期笔者接触了一些比较有代表意义的回溯题目，从一些犯下的错误中获得了一些感受，下面谈一谈我的一点粗浅的体会。
一、谨慎地辨别是不是仅用贪心算法而不用回溯就可以解决问题
大家知道，贪心算法无论在理解上、编程的难易程度以及所花费的时间上来说都优于回溯，因此可以用它解决的问题应该尽量避免去进行无用的搜索。但是一些问题披着贪心的外貌，却隐藏着一些不易被发现的反例，能不能找出这些特殊的情况并依此选择正确的算法，也算是衡量我们水平的重要标志之一。
来看一看“抓气球的游戏”。有100个分别标有1至100号的气球，两个游戏者每人抢到其中的一些，（也有一些没有被任何人抢到），每个人的得分就是所得气球号码的乘积，报出分高的人获胜。但是经常会出现一些纠纷，比如，甲说自己得了343分，乙说自己得了49分。显然甲的343分只能是由49*7所得，而乙的49分只能是仅抓到了49分一个球，但49分的球只有一个，这导致了矛盾。在这里，我们假设一旦这种情况出现，一定是分高的人说了假话。现在任意给定两个玩家的所得分数，请判断出获胜的一方。显然，问题的实质就是判断给定的两个得分是否矛盾。
[错误的算法]：对小数的分解采取贪心算法，然后用回溯法系统求解大数可能的组合。
[具体过程]：首先，从100逐一递减，对其中每个能被小数除尽的数就除,直到除到商为1，所除的数的组合就是小数的一种组合方案。把以这种方式选定的因子剃除，再对剩下的数用乘法组合较大的数，如果能组合的出来，两数就不矛盾，否则矛盾。
[反例]：这种算法粗看起来蛮有道理，但是由于在拆解小数的过程中可能占用了大数必须用到的因子而导致错误的出现。比如144和198两个数。144按这种方法拆解为72*2,而2一旦被占用，198就无法顺利地被分解了。可是事实上，144可以分解为36*4,18*8,9*16，3*48，3*6*8等多种不占用2的组合,这证明这两个数其实并不矛盾。
[正确的算法]：两层回溯，对小数回溯法系统地求出所有的组合方案，并对每种方案下的因子被剔除后再对大数进行回溯组合，如果能找到合理的分配，两数就不矛盾。如果对于小数的每种组合方案，大数都无法用剩余的因子相乘而得到，才可以确定两个数是矛盾的。
在这个例子里贪心算法的不成立是因为不同气球号码组合得出相同结果的多样性，实际上，大家都能注意到，只要稍微改变一下题目描述，如果气球号码不是连续的而是互质的，那么不单可以用贪心法拆解小数，也可以继续贪心地拆解大数，甚至可以直接拆解两数的积。所以，贪心可能是实质，也可能只是假象，在不能十分明确地看出问题的贪心实质时，还是选择回溯法更加稳妥。
二、剪枝的选择——兼顾平均状况与最差状况下的时间消耗
由于回溯法的时间复杂度往往是问题规模的指数函数，因此对于规模稍大一些的问题往往有些力不从心，而合理的剪枝因为可以减少一些时间上的消耗就显得格外有意义，然而因为对剪枝条件的判断一样需要花费时间，所以剪枝条件的设置并不是越多越好，而要找到一个合适的平衡点。此外，有一些剪枝虽然对所有情况的平均效率影响不大，但是对于改善最坏状况下的时间消耗，却有着立竿见影的效果，这种约束在一些特定的场合（比如，在竞赛中）有着十分重要的意义。
“方格游戏”是96年中国上海ACM/ICPC竞赛上一道经典的回溯题目，游戏者在开始时被给予n*n（2<=n<=5）的格子，每个格子被分为四个三角形，每个三角形中置入0-9之间的一个数字，现在需要判断对于一种特定的设置，能否找出一种格子排列方案，使得任意相邻格子的邻接三角形中被放如相同的数字。比如对于下图，
可以在调换方格的顺序后得出如下的一种解决方案：
从题目来看，可以很快地写出对方格的回溯框架并写出一个具有普遍意义的剪枝,即按照从上到下，每行从左到右的顺序摆放可能的方格，必须保证此方格左三角的数字不等于左边方格的右三角数字，同时此方格上三角的数字不等于上边方格的下三角数字。由于这道题n的上限仅为5，解空间树叶节点数的理论上限为25!，而且加上这个剪枝的设置，笔者认为在时间上不会有很大的问题，但是却出现了超时错误。问题的关键还在于，除了这个剪枝之外，已经很难找出在平均意义下对时间消耗有所改善的剪枝。（笔者曾想过，能否判断此方格的下三角数字是否至少还存在于剩余方格之一的上三角中，答案为否也剪掉，但是实践证明这样的收效甚微，而且判断本身还要花一些时间。）
超时的原因必然是回溯的层次很深但是剪枝效果不显著并且找不到解决方案（因为本题只让判断能否找出一种方案，所以一旦找到一种方案就可以停止回溯了）。应该意识到，对于一些极端的数据，这种情况是存在的。比如5*5的规模，有24个方格的四个数字全部都是0，而最后一个方格的数字中没有0，那么上面提到的剪枝方案简直是形同虚设。考虑到这点，程序可以把完全相同的方格合成一类，在每个节点处仅按照类别选择，而不进行重复的搜索。应该指出，如果数据完全随机化，这种简化所改进的效率并不大，但是对于最坏情况的出现，却起到了很大的限制作用。
当然，仅仅改善最坏情况是否有意义，要根据具体的情况确定，对于竞赛是有的，对于实际则未见得有。那么，如果在实际中出现了类似的时间问题，比较有意义的做法则是运用概率算法或近似算法降低解的准确性来获得时间上的改善，或者消除最坏情况与特定实例之间的联系关系（如运用Sherwood算法），这就是另外的话题了。
最后再说一个比较基本的问题，笔者看到一些程序在回溯中使用的函数递归调用仍然有很长或规模很大的参数列表，这是应该避免的，尤其是层次很深的递归，保留所有层次的变量是一个很大的开销。如果是小程序，其实可以适当地使用全局变量；大一些的应用程序，则建议用类封装，用成员变量记录信息，用成员函数实现递归。