回溯算法
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。满足某个状态的点叫做回溯点。回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。
用回溯算法解决问题的一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
商人渡河问题：
问题：3名商人各带一名随从过河，河面上只有一条仅能容两人的空船，船由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是乘船渡河的方案由商人决定，商人们怎样才能安全渡河？
相对来说我们可以把当前状态称为此岸；在此岸可能出现的商人和仆从的人数我们可以一一枚举出来：
[0,0],[0,1],[0,2],[0,3]
[1,0],[1,1],[1,2],[1,3]
[2,0],[2,1],[2,2],[2,3]
[3,0],[3,1],[3,2],[3,3]
注：前面数字表示商人数； 后面数字表示仆从人数
我们很容易得知：此岸的安全状态(同时彼岸也是安全的)
[0,0],[0,1][,0,2],[0,3] [1,1]
[2,2],[3,0],[3,1],[3,2],[3,3]
设置变量
p[i][5]：存放渡河的状态，{闲置，商人数，随从数，(-1)^i，获得该状态采用的决策序号}；
d[n][3]：存放所有可行的渡河决策变量，{闲置，船上商人数，船上随从数}；
s[1][3]：存放保证安全的此岸的状态，{闲置，商人数，随从数}；
nin：记录第i次过河次数的奇偶性，nin = (-1)^i； -1，渡河次数为奇，1，渡河次数为偶；
nnew：0，当前一步的试探不可行，回溯搜索下一种渡河决策的可行性； 1，当前一步的试探点可行，从第一种渡河决策开始搜索下一个可行状态；
flag：0，未找到解； i，第i次渡河后所有人安全渡河！
safe：0，试探点不可行，即不能保证商人安全； 1，试探点安全；
same：0，该试探点与前面无重复；1试探点的状态变量值和下一次渡河的奇偶性与前面某些状态相同。
#include <stdio.h>
#include <stdlib.h>
void main (void)
{ int p[21][5] = {0,0,0,0,0,0,3,3,-1,0},
d[ 6][3] = {0,0,0, 0,1,0, 0,0,1, 0,1,1, 0,2,0, 0,0,2},
s[11][3] = {0,0,0, 0,3,3, 0,3,2, 0,3,1, 0,3,0, 0,2,2, 0,1,1, 0,0,0, 0,0,1, 0,0,2, 0,0,3},
n, i, j, k, same, t1, t2, pt1, pt2, pt3, pt4, dt1, dt2, safe, nin, flag;
for (i=2; i<=20; i++) // p[2][]开始都置初值0;
for(j=0; j<=4; j++)
p[i][j] = 0;
nin = -1; // 记录过河次数的奇偶性，－1 表示渡河次数为奇。
n = 1; // 从第一种决策开始搜索；
flag = 0;
// 搜索开始
for (i = 1; i<=20; i++)
{
nin = nin * (-1);
pt1 = p[i][1]; pt2 = p[i][2];
pt3 = p[i][3];
pt4 = p[i][4] ;
if (pt1 == 0 && pt2 == 0) // 所有人成功安全渡河，问题求解完毕；
{ flag = i; //flag 记下结束的状态序号
puts("\n OK, the method is found!");
break; }
for ( n; n <=5; n++) // 搜索各决策的可行性，如果是新的状态点，n初始值为1;
{ dt1 = d[n][1];
dt2 = d[n][2];
t1 = pt1 + pt3 *dt1; t2 = pt2 + pt3 *dt2; //计算试探点的状态变量值
safe = 0;
for (j=1; j<=10; j++) // 检查试探点的可行性，即是否安全；
if ( t1==s[j][1] && t2 == s[j][2])
{ safe = 1;
break; // 试探点安全可行；
}
if (safe == 0)
continue; // 试探点不安全， 继续试探下一决策的可行性
else // 试探点安全
{ same = 0 ;
for (k=1; k<=i; k++) // 检查试探点的状态与前面的状态有无重复
if (t1 == p[k][1] && t2 ==p[k][2] && nin == p[k][3])
// 试探点的状态与前面的状态有重复, 继续试探下一决策的可行性；
{ same = 1; break; }
if (same == 0 ) break;
// 试探点的状态与前面的状态无重复，即成功找到下一可行状态；
}
}
if (n == 6) // 当前状态无可行决策，须退回到上一状态再搜索
{ if (p[1][4] == 5) break; // 第一步就无可行决策，即问题无解
n = p[i][4] + 1;
// 记当前状态为 p[i] = {商人数, 随从数, nin, n},
// 则退回至上一状态去后从第n+1种决策开始继续试探搜索;
// 退回至上一状态去后继续试探搜索的决策序号
p[i][1] = 0 ;
p[i][2] = 0;
p[i][3] = 0;
p[i][4] = 0 ; // 当前状态与可行决策，重置初值0
i = i - 2; // 回撤到上一状态继续试探搜索；
}
else
{ p[i+1][1] = t1;
p[i+1][2] = t2;
p[i+1][3] = nin;
p[i+1][4] = n; // 状态更新;
n = 1; //找到新的可行状态，下一步从1号决策支取搜索试探；
}
} // 搜索结束
if (flag ==0 ) // 求解不成功！
printf("此题无解\n");
else
{ puts(" The status of this side of the river is listed as follows: ");
puts(" 状态 商人数量 仆从数量");
for (i=1; i<=flag; i++) // 过河成功，显示此岸的状态序列；
printf(" %2d : %d %d \n", i, p[i][1], p[i][2]);
}
}
运行结果图
网友评论