找回密码
 注册
Simdroid-非首页
查看: 229|回复: 1

[其他研讨] 好久没来,发过 Mathematica 求解商人过河问题的代码

[复制链接]
发表于 2015-10-17 23:18:40 | 显示全部楼层 |阅读模式 来自 湖南怀化
好久没来,有人问我要这个问题的代码,所以贴上来;
问题: 3 名商人各带一随从过河,河面上只有一条仅能容两人的空船,船由他们自己划行,
  随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越——但是乘船渡河的方
  案由商人决定.商人们怎样才能安全过河?

p = Table[{0, 0, 0, 0}, {20}];
d = {{1, 0}, {0, 1}, {1, 1}, {2, 0}, {0, 2}};
s = {{3, 3}, {3, 2}, {3, 1}, {3, 0}, {2, 2}, {1, 1}, {0, 0}, {0,
    1}, {0, 2}, {0, 3}};
p[[1]] = {3, 3, -1, 0};
New = 1;
For[i = 1, i <= 20, i++,
  pt = p[[i]];
  If[And[pt[[1]] == 0, pt[[2]] == 0], Break[]];(*找到解*)
  If[New == 1, n = 1];
  For[n, n <= 6, n++,
   If[n == 6, Break[]];(*没有找到安全的点*)
   dt = d[[n]];
   t1 = pt[[1]] + pt[[3]]*dt[[1]];
   t2 = pt[[2]] + pt[[3]]*dt[[2]];
   safe = 0;
   For[j = 1, j <= 10, j++,
    st = s[[j]];
    If[And[t1 == st[[1]], t2 == st[[2]]], safe = 1; Break[]]
    ];
   If[safe == 0, Continue[]];
   same = 0;
   For[k = 1, k <= i, k++,
    qt = p[[k]];
    If[And[t1 == qt[[1]], t2 == qt[[2]], -1^(i + 1) == qt[[3]]],
     same = 1; Break[]]
    ];
   If[same == 0, Break[]]   (*找到了下一个点*)
   ];
  If[n == 6, New = 0; n = p[[i]][[4]] + 1; p[[i]] = {0, 0, 0, 0};
   i = i - 2; Continue[]];(*退*)
  New = 1; p[[i + 1]] = {t1, t2, (-1)^(i + 1), n}(*找到新的点*)
  ];
p

 楼主| 发表于 2015-10-17 23:20:35 | 显示全部楼层 来自 湖南怀化
Simdroid开发平台
下面的是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]);
        }
}

回复 不支持

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-29 18:38 , Processed in 0.028299 second(s), 10 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表