计算机能解决的问题所需的计算时间与其规模有关。 也就是说，问题的规模越大，需要的时间和计算资源越多，问题的规模越小，所需的时间和计算资源就越小，问题的解决也就越容易。 因此，在处理一些困难的问题时，考虑缩小问题的规模从而更容易地解决困难的问题。 在充分研究了这种算法规律后，将其归纳为递归法、分割统治法、动态规划法、贪婪法等缩小算法。 (分治法、动态规划法、回溯法均基于递归算法)

在实际解题的过程中，你会发现并不是每个问题都能直观地分解成几个小问题来解题。 大多数情况下，最容易想到的问题的解决方法是枚举法(也称为穷举法或蛮力法)，即毫无遗漏地验证所有可能试图解决问题的情况，并从中找出符合要求的答案。 因此，列举法通过牺牲时间来换取答案的全面性。 如果在搜索解的过程中加入判定条件以加快搜索速度，则不同的搜索策略有回溯法和分支边界算法。

回溯法(探索和回溯法)是选拔探索法，也称为启发式法，是根据选拔条件进行前进探索，以实现目标。 但是，在探索某一步时，如果原选择不出色或未达到目标，则后退一步重新选择。 这样，如果不顺利的话，返回的技术就是回溯法，满足回溯条件的某个状态的点被称为“回溯点”。 扩大现在的候补解的规模，继续探索的过程称为前瞻性探索。 也就是说，除了当前候选不满足规模要求外，在满足所有其他要求的情况下，继续扩大当前候选解的规模，继续探索。 如果当前的候选解满足包括问题规模在内的所有要求，则该候选解就是问题之一的解。

正在加载视频.

回溯算法实际上是一个类似枚举的检索尝试过程，主要是在检索尝试的过程中寻找问题的解，如果发现不满足求解条件，则“回溯”尝试另一条路径。 请参考一下在迷宫中前进的过程。 最初随机选择一条路前进，直到不能通过为止，直到找到另一条从未尝试过的路为止。 其实，求解迷宫的算法是回溯法的经典问题。

回溯法实际上也是一种反复试验的想法，通过不断尝试解的组合来达到求得可行解和最佳解的目的。 虽然包含在穷举搜索的概念中，但是回溯法和穷举搜索法不同。 虽然对于某个问题的所有事例，穷举法注定非常缓慢，但通过应用回溯法，至少对于非小规模的事例，有望在计算机能够允许的时间内解决问题。

许多复杂规模的问题可以使用回溯法，有“通用求解方法”的美称。 分书问题和八皇后都是典型的上溯及法问题。

分书问题

有编号为0、1、2、3、4的五本书。 准备把a、b、c、d、e分成五个人，写一个程序，输出所有大喜的分文件。

每个人的读书兴趣都用二维排列like来记述：

like I=真I喜欢书j

like I=false I不喜欢书j

设计函数trynext(intI )把书分给第I个人。 用一维数组take表示某本书被分成了谁。 take=I 1；//把第j本书分配给第I个

按顺序试着把书j分成人I。

如果第I个人不喜欢第j本，请尝试下一本书，如果喜欢，但还没有分配第j本，请将第j本分配给I。

如果I是最后一个人，则在计划数上加1，输出该计划。 否则，调用trynext(i 1 )为第I1个人分发书。

如果第I个列出所有喜欢的书，但找不到可行的方案，请返回上一个状态i-1，将分配给i-1的书放回去，重新查找喜欢的书，递归调用函数寻找可行的方案。

# #包含iostream

# #包括连续号h

单一名称空间固态硬盘；

int like 5五号

{ 0，0，1，1，0 }、

{ 1，1，0，0，1 }、

{ 0，1，1，0，1 }、

{ 0，0，0，1，0 }、

{ 0，1，0，0，1 }；

int take [5]={ 0，0，0，0，0 }； //记录每本书的分发情况

铟锡； //n表示分割方案的数量

voidtrynext (整数)；

int主() )

{

n=0；

trynext(0；

getch (；

返回0；

}

分配给第//I个人

voidtrynext (英制) )。

{

国际航空运输协会；

for(j=0； j5； j )日本

{

if (like-j任务==0)

{

take=I 1；//把第j本书分配给第I个

if(I==4)//第五个人的分配结束了，也就是说所有的书都分配完毕，可以输出计划

{

n；

第'个分配方案'最终；

for(k=0； k5； k ) )

cout '本书为“(字符)”) k ) ) a(-1 )最终版；

cout终端；

}

else

三下一个(i1； //递归地分配给以下人员

take[j]=0； //追溯，寻找下一个方案

}

}

}

like矩阵的值为