回溯法，是通过递归的方式穷举组合问题的所有可能解，关于这个问题的解决方法大致有如下步骤
- 建立解矩阵，如果不知道可行解数量(有待探索)，可以建立动态存储数据结构
- 构建基本问题，首先检查解结构完备与否，如果完备返回解，或者记录解结构，另外如果存在提前结束的可能，可以贪婪的检查当前解结构是否已经违反解规则，如果是则提前结束
- 基本问题的迭代结构，对于一般的组合问题，这个迭代的维度可能保持一致，当然也可能不一致，主要取决于原始问题的结构特征;每一次迭代需要进一步完备解结构，并且递归的进行下一步完备，值得注意的是：我们需要判断当前操作对横向和纵向的影响，如果是在解数量上（如是否有重复解等的）的影响，则需要在当前函数结构下对组合空间进行约束，如减少或者跳过重复项的选择;如果是在解结构上(比如解结构中不能出现重复的选择)的影响，则需要在递归调用之前改变约束组合空间，在递归之后释放约束。
下面举例说明：
1. permutation问题
排列问题是一类典型的可以用backtracking解决的问题，给定n个数字（或者字），打印出所有可能的排列。数学上我们知道这个数量是一个阶乘，很好理解就是n次无放回的选择，这个操作结构如何在用backtracking实现呢？
按照回溯的思路：
solution[n!] //建立一个全局变量，当然也可以不这样做，只是需要在函数递归调用时不断传递解容器和当前解
void backtrack(current_solution, index){
if(current_solution is well_generated)
print it or record it
return
else if current_solution is bad_structure
return // backtrack的迭代函数一般都是无返回值的
for index to space_size
add space[index] to current_solution
backtrack(current_solution, index+1)
如果给定一个初始的排列(结构中可能含有重复元素)，此时可能会存在重复的解，原因在于横向空间中的重复会导致最终生成完全一致的解，并且递归的重复，所以必须在每一层次上改善解空间(不能对纵向产生影响)，即记录已经迭代过的元素，避免重复！但是我们知道在解结构中是可能存在重复元素的，这时我们需要纵向的控制解结构，即通过记录已经构造的解中重复元素的数量来避免破坏解结构。下面的代码是个很好的例子：
int array [ 128 ]; //个别存入128个ASCII字元的出现次数
char solution [ MAX ];
void permutation ( int k , int n )
{
if ( k == n )
{
for ( int i = 0 ; i < n ; i ++)
cout << solution [ i ];
cout << endl ;
return ;
}
for ( int i = 0 ; i < 128 ; i ++) //列举每一个字母
if ( array [ i ] > 0 ) //还有字母剩下来，就要列举
{
array [ i ]--; //用掉了一个字母
solution [ k ] = i ; // char变数可以直接存入ascii数值
permutation ( k + 1 , n );
array [ i ]++; //回收了一个字母
}
}
- next permutation
相邻元素比较大小，直到前一元素小于后一元素，用遍历过的最小元素代替当前停止元素，然后将其他元素逆序输出。 - 有效括号最大长度
下标存储法，通过记录下标来标记相邻的最大有效字串 - 字符串匹配问题一开始应该考虑用组合动态规划去解，考虑能否对0行和0列做初始化，如果能够初始化，则问题多半就能解决，一种求字符串之间距离的算法值得借鉴
网友评论