Game & Graphics Programing, AI & Algorithm Exercises

今天(已经是昨天了)又翻了翻《啊哈,灵机一动》(马丁·加德纳著),有个排列组合的谜题是复杂的路.要求就是寻找在一个错综复杂的路径图里面从一个节点到另一个节点的所有可行路径数目.已规定每次我只能选择向右或者向上移动一个位置.

比如上图是一个棋盘形式的路径图,比较容易找规律,如果我愿意花一个钟头的时间的话,我可以把所有路径列举出来,如果顺利的话,我想可以给我更少的时间.我小时候总是为自己能很快而准确的列举找到答案而洋洋得意.我还记得小时候寻找一个笼子里面兔子和鸡的合适数目,我忙碌的在草稿纸上列举所有兔子的腿数和鸡的腿数.

虽然我知道很少有人愿意按照上面的方法去得到答案,但是如果去做了,我肯定能从中找到规律.不过下面从一个格子开始分析,这样也许是一个很不错的尝试.当我被迫要打开柜子所有抽屉找到所有装了纽扣的抽屉时,从第一个抽屉开始,是个明智的决定,这样不至于后来一团糟,想象一下,当你最后都不知道打开哪些抽屉而又不得不再次打开验证时是多么的令人沮丧.

显而易见,在一个格子里面,从左下角到右上角有两种路径.如上图A→C→B和A→D→B.

为了更好的表现每个节点上到达该节点的路径数目,可以及时的把数目标注上,如上图所示.这样看起来好极了,我开始迫不及待的按照这种方法在棋盘的每个格子的节点上开始标记.

我做的很快.我还不知道是否是正确的,但我很兴奋,没有什么能够阻止我继续写下这些数,不停计算100以内加法对我是一件很过瘾的事情.真不可思议,一分钟内我列举出了所有的数目,我认为肯定是正确的,我必须要证明.归纳法无疑是一个很不错的证明.

1. 已知第一个格子里面,除右上角的节点,其他三个节点的数目已知全部为1,可知从第一个格子的左下角到右上角有两条不同路径.记值为2。有谁还怀疑1+1=2呢?
2. 对于非十字型节点,也可以当做十字形节点处理,把节点左边和下边的十字分支数目定为0
   
3. 参照下图,假如我已经知道某个节点左边节点和下面节点值的话,只要把这两个值做加法就是该节点值
   

再次回到这些棋盘上面的数字,总是相邻两个方向的数字做加法得到下一个节点值.把棋盘旋转45°.真难以置信,这不就是杨辉三角吗?这使我想到当把一个没有头脑的虫子放在棋盘左下角让其按照谜题规律移动,那么这些数字足以代表虫子到达某节点的可能性.在加德纳的《啊哈,灵机一动》书上,谜题本身是苏珊为了避免上学碰到讨厌的斯蒂克而需要每天走不同的路径.呵呵,如果加德纳进一步把这个故事扩展的话.我想苏珊可以完全有根据的选择那些斯蒂克选择可能性小的路径.当然我们得残忍的先认同斯蒂克像虫子一样.杨辉三角最重要的性质是第n行的所有数列式n次二项式展开式的系数列.这也很好的说明了到达节点的概率性.

现在我可以欢呼了.甚至像下图这种不规则格子地图也能用这种方法得到正确答案.

也许已经取得了很大的胜利了,不过我已经厌倦了在每个节点做加法.当有一个复杂的棋盘地图或者蜂窝地图时我就不能逼迫自己做着机械的加法.我需要计算机来帮助我得到一个简洁的答案.

我之所以在上面对这个谜题进行分析,是因为我在看书联想到上周上课时练习的几道动态规划问题.寻找路径问题,可以归结为一个简单的递推.而动态规划能够保正每个节点仅被计算一次,减少重复计算.实际上,我在上面的操作中,就是一个手工的动态规划演绎过程.

下面使用动态规划的方法来重新分析棋盘路径问题,并尝试给出算法.

不妨做如下定义:给棋盘上的每个节点定义坐标,最左下方的为f(0,0),最有上方的为f(M,N).

该问题子问题就可以描述为:从(0,0)走到(x,y),每次只能往右或者往上走一步(对应坐标值增1),一共有多少种走法,该点走法的数目记为f(x,y),原问题就是求解f(M,N)

要得到f(x,y)有两个方法,一个是从(x-1，y)往右走一步到(x,y),另一个就是从(x,y-1)走到(x,y).第一个方法有f(x-1,y)种走法,第二种有f(x,y-1)种走法.所以可以得到f(x,y)=f(x-1,y)+f(x,y-1),这个可以通过归纳法证明.由此得到递推公式为:

1. 当x=0或y=0时,f(x,y) = 1;
2. 当x>0且y>0时,f(x,y)=f(x-1,y)+f(x,y-1)

/// 求解到坐标(m,n)的不同路径数目
public int HowManyWays(int m,int n)
{
    //创建一个二维表来保存每个节点的路径数目值
    int[,] answerMap = new int[m, n];
    //初始化表中所有值为1
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            answerMap[i, j] = 1;

    //使用递推来得到每个节点的解
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            answerMap[i, j] = answerMap[i - 1, j] + answerMap[i, j - 1];

    //返回结果
    return answerMap[m - 1, n - 1];
}

这个算法也就是计算了杨辉三角.如果要计算非规则的棋盘地图节点路径的话,就不能使用简单的二维表,可以考虑使用树形结构或者图来存储地图节点关系数据.不同的移动规则也影响算法过程.

如果你喜欢这样的文章, 请 订阅我的RSS feed吧 !