简述回溯法的基本思想，采用这种算法的关键是什么？
正确答案:回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的 是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。
答案解析:有
微信扫一扫手机做题