- 积分
- 6
- 注册时间
- 2008-9-25
- 仿真币
-
- 最后登录
- 1970-1-1
|
楼主 |
发表于 2015-10-17 23:20:35
|
显示全部楼层
来自 湖南怀化
下面的是C语言版的,注释很详细!
/* 变量说明:
p[i][5] : 存放渡河的状态, {闲置, 商人数,随从数,(-1)^i, 获得该状态采用的决策序号};
d[n][3] : 存放所有可行的渡河决策变量,{闲置,船上商人数,船上随人数};
s[11][3]: 存放保证安全的此岸的状态,{闲置,商人数, 随人数};
nin : 记录第 i 次过河次数的奇偶性, nin = (-1)^i;
-1, 渡河次数为奇, 1, 反之;
nnew : 0, 当前一步的试探不可行,回溯搜索下一种渡河决策的可行性;
1, 当前一步的试探点可行,从第一种渡河决策开始搜索下一个可行状态;
flag : 0, 未找到解;
i, 第i次渡河后所有人安全渡河!
safe : 0, 试探点不不可行,即不能保证商人安全;
1, 试探点安全;
same : 1, 试探点的状态变量值和下一次渡河的奇偶性与前面某状态相同;
0, 该试探点与前面无重复;
*/
#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},
nnew, 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 表示渡河次数为奇。
nnew = 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;
puts("\n OK, the method is found!");
break;
}
if(nnew ==1) n = 1 ; // 当前状态为新状态,从第一种决策开支试探搜索;
for ( n; n <=5; n++) // 搜索各决策的可行性
{
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; // 第一步就无可行决策,即问题无解;
nnew = 0; // 记上一状态为 {商人数, 随从数, nin, n},
// 则退回至上一状态去后从第n+1种决策开始继续试探搜索
n = p[i][4] + 1; // 退回至上一状态去后继续试探搜索的决策序号
p[i][1] = 0 ; p[i][2] = 0; p[i][3] = 0; p[i][4] = 0 ; // 当前状态清空,置初值0
i = i - 2; // 回撤到上一点继续试探下一决策是否可行;
}
else
{
nnew = 1; //找到新的可行状态,下一步从1号决策支取搜索试探;
p[i+1][1] = t1; p[i+1][2] = t2; p[i+1][3] = nin; p[i+1][4] = n; // 状态更新;
}
}
// 搜索结束
if (flag ==0 ) // 求解不成功!
printf("The method is failed!!\n");
else
{ puts(" The status of this side of the river is listed as follows: ");
puts(" Step Businessman Servant");
for (i=1; i<=flag; i++) // 过河成功,显示此岸的状态序列;
printf(" %2d : %d %d \n", i, p[i][1], p[i][2]);
}
}
|
|