回溯法“>算法—>回溯法

设问：或人要从a路口经过4个路口（含开端路口和意图路口）抵达b路口，已知该区域的路途有一个特色：除起点和结尾外，每个路口都有三条叉路。请找出一条可行的道路。
首要，咱们应该分分出咱们所能找到的有关信息：
1、从开端地到意图地一共有4个路口；
2、除起点和结尾外，每个路口都有三条叉路；
要处理这一问题，首要咱们应该将地形图转换为较标准的途径图，其间途径图中的结点对应地图的路口，途径图中的连线对应地图的路；然后尝试着找出某种规矩进行路的根究。当在某个路口走不通时就回头另找一条新的路，当发现了方针地址就能够中止寻觅。
从问题的某一种或许状况动身, 查找一切能到达的或许状况，然后再以其间的一种或许状况为新的动身点，持续向下根究，这样就走出了一条“路”。当这一条路走到“ 止境”的时分, 再倒回上个动身点, 从另一个或许状况动身, 持续查找。这种不断“回溯”寻觅方针的办法, 称作“回溯法”。
回溯法的基本思想是穷举查找。一般适用于寻觅解集或找出满意某些约束条件的最优解的问题。这些问题所具有的共性是次序性，即有必要先根究第一个步，确认第一步采纳的或许值，再根究第二个步采纳的或许值，然后是第三步，……，直抵到达方针状况。
结合设问，咱们很简单找出问题所涉及到的数据与途径图之间的对应联系：路口地点的层数表明根究步数对应的编号，每个路口的分叉表明从该状况动身一切或许的状况。
在数据的详细描绘中，为表现根究过程的次序性，能够将层数用整数来表明；为表明每个动身点的规律性，咱们一般将状况概括一下，并用次序呈现的整数表明。
关于每个路口而言，其分叉的方式应是共同的。因而一般状况下咱们用整数来表明，因为每个路口都有三个分叉，那么咱们能够依据分叉呈现的次序从左向右顺次用整数1，2，3进行编号就能够了。
在程序中咱们能够用数组a寄存途径，其间下标表明根究的步数编号，数组元素a[k]的值表明在第k步所采纳的或许值的编号。这样对路的根究办法都能够用以下的代码表明：
procedure find (k:integer)； {找第k步的或许性}
begin
if 到意图地 {表明一条路已找出}
then
begin
输出道路；
完毕根究
end
else
if k<=4
then
for i:=1 to 3 do {穷举三种或许的方向并记录下来}
begin
　　　 a[k]:=i；
find(k+1)
end
end；
由此可知，依据每个结点根究具有共性这个特色，在完成中咱们一般选用递归的算法来完成回溯战略。下面给出的是关于该递归算法的非递归代码:
begin
a[1]:=1；k:=1； {确认起步的路标语及寻觅的初始方向}
while 未到意图地 do
begin
while a[k] 无路可走 do {回溯，回来第K-1个路口，另找一条路}
begin
k:=k-1；
a[k]:=a[k]+1
end；
k:=k+1；a[k]:=1； {设定从K+1个路口开端寻觅的初始方向}
end；
输出道路；
end；
经过调查，咱们能够发现完成回溯算法的特性：在处理过程中首要必需要先为问题界说一个解的空间，这个空间有必要包括问题的一个解。在查找路的一起也就产生了新的解空间。在查找期间的任何时刻，仅保存从开端点到当时点的途径。因而，回溯算法的空间需求为O（从开端节点起最长途径的长度）。
回溯的战略是一种常见的战略。它能够防止对规划很大的候选解进行一次性查看，因而适用于一些求解规划很大的问题。在详细完成过程中咱们应该以找出解题办法与途径图对应的数据联系为切入口，运用递归的算法加以完成。运用回溯战略，咱们一般处理自然数的摆放、n皇后问题、迷宫问题、数的拆分、0/1背包问题、旅行商问题、货船装货和图形掩盖正方形等问题。