1. 回溯法(back tracking)是一种选优搜索法,又称为试探法,有“通用的解题法”之称,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回到上一步,重新选择,这种走不通就退回再走的技术称为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
2. 回溯是递归的副产品,只要有递归就会有回溯,所以回溯法也经常和二叉树遍历,深度优先搜索混在一起,因为这两种方式都是用了递归。回溯法就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。
3. 问题的解空间:
4. 回溯法基本思想:确定了解空间的组织结构后,回溯法从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。
5. 回溯法的基本步骤
注意:尽管通过剪支提高了算法的性能,但究竟剪去了多少结点与具体的实例数据相关。上述算法最坏情况下的时间复杂度仍然为 O ( n 2 ) O(n^2) O(n2)。
#include
using namespace std;
#define max 100
int a[max],b[max];
int sum = 0, m, n; //m为目标值,n为集合的大小
void Solve(int k)
{
if (k == n)
{
if (sum == m) //相等时输出一个解
{
cout << "符合目标值的一个子集为:";
for (int i = 0; i < n; i++)
if (b[i] != 0)
cout << b[i] << " ";
cout << endl;
return;
}
}
else
{
sum = sum + a[k];
b[k] = a[k];
Solve(k + 1);
sum = sum - a[k]; //回溯时先还原
b[k] = 0;
Solve(k + 1);
}
}
int main()
{
memset(b, 0, sizeof(b)); //将b数组设置为0
cout << "请输入集合S元素个数n:";
cin >> n;
cout << "请输入集合S元素:";
for (int i = 0; i < n; i++)
cin >> a[i]; //数组a存放集合中的值
cout << "请输入目标值:";
cin >> m;
Solve(0);
return 0;
}