Skip to content

Latest commit

 

History

History
96 lines (87 loc) · 5.65 KB

chapter6.md

File metadata and controls

96 lines (87 loc) · 5.65 KB
Raw

复习题6.4

  1. 回溯算法的主要特征是什么？

    • 在解决问题的过程中，沿着某个决策点前进，如果是正确的，问题得到解决。如果走进死胡同，或者发现决策错误，则退回上层决策点，尝试另一条路径。它的特征是使用了递归。

  2. 用自己的语言来描述，如何用右手规则穿越迷宫。用左手法则是否也能达到同样的效果？

    • 右手规则穿越迷宫，将一只手接触墙壁，并向前一直走，保持手始终不脱离墙壁，直到脱离迷宫。
    • 左手法则能起到同样的效果，只是与右手规则相比，方向相反。
    • 问题的核心在于跟着墙遍历迷宫的路。

  3. 用递归回溯法则解决迷宫问题的核心是什么？

    • 如果有出口，那么肯定在其中一条路线上，如果选对了方向，那么向问题的解决靠近一步。沿着这条正确的路走即使关键核心(小规模的同样问题)
    • 如果已经在迷宫外，则问题已经解决，如果走到死胡同，则此路不通(简单情形)

  4. 在SolveMaze的递归实现过程中，有哪些简单情景？

    • 走到死胡同(当前方格已被标记的场合)
    • 走出迷宫

  5. 为什么说穿越迷宫时做标记是重要的？如果未作标记，那么SolveMaze函数将会发生什么情况？

    • 函数无法正确判断一个位置是否被走过，避免可能出现函数不退出的情况(在一个死胡同打转)

  6. 在SolveMaze的实现中，为什么要在for循环后调用UnmarkSquare函数？这对于该算法是否必要？

    • 回溯到上个情形，重新选择；
    • 实际上是不需要的，因为当需要回溯时，已经走到了死胡同，直接退出即可。但是如果需要进行图解分析，最好还是加上。

  7. SolveMaze函数所返回的布尔结果有何作用？

    • 表明迷宫问题是否被解决，帮助判断是否要继续进行递归调用。

  8. 用自己的语言，解释回溯过程在SolveMaze的递归实现中是如何发挥作用的。

    • 递归的每一个栈都表示程序向前一步，即在迷宫中走过一步，并在栈中记录了这一步的信息；
    • 当走到迷宫的死路回头时，判断了信息，此处已经走过，就返回函数回到上层栈；
    • 上层栈接着执行代码，消除当前标记信息，即表示向后退回一步。

  9. 在简单的拿子游戏中，开始时硬币是13个，人类玩家先走第一步，有利还是不利？为什么？

    • 人类玩家先走第一步是有利的
    • 因为拿到最后一个硬币的人判负，所以要让还剩一个硬币时的情况轮到人类拿子
    • 因为谁拿到12谁就赢定了，依次可推出需拿到8、4，先行无论如何拿不到4，所以无法胜利。(13 - 1) = x * (1 + 3) => x = 3 (轮) (1 + 3)是每一轮都绝对能达到的拿子数量

  10. 编写一个简单C语言程序，局势对当前玩家有利时nCoins的值是TRUE，反之为FALSE(提示：使用%运算符)。

    // How it should be in real code
static bool IsGoodPosition(int nCoins)
{
    return !IsBadPosition(nCoins);
}

// answer to the question
static bool IsGoodPosition(int nConis)
{
    if (   nCoins % 1 != 1 
        && nCoins % 2 != 1 
        && nCoins % 3 != 1)
    {
        return TRUE;
    }
    else
    {
        return !(FindGoodMove(nCoins) == NoGoodMove);
    }
}

  11. 什么是最小最大算法？它的名字有什么意义？

    • 最小最大算法是使得对手处于坏的局势中的算法，它的意思是让对手每一步能选择的最大收益最小化。

  12. 分析一个游戏时，ply这个词是什么意思？

    • 表示单个游戏者的单步动作，它的意义是每个游戏者都具有的操作机会。

  13. 假设您处在下图所示的局势中，分析下两步棋以显示出从您的角度出发的评分结果：

    graph TB;

A((top))---B((s1))
A((top))---C((s2))
A((top))---D((s3))
A((top))---E((s4))
B((s1))---F(("+4"))
B((s1))---G(("+9"))
B((s1))---H(("-4"))
C((s2))---I(("+3"))
C((s2))---J(("+2"))
D((s3))---K(("+4"))
D((s3))---L(("+3"))
D((s3))---M(("-2"))
D((s3))---N(("+5"))
E((s4))---O(("-1"))
E((s4))---P(("0"))
E((s4))---Q(("+5"))
    Loading

    如果采用最小最大策略，那么在该局势下最好走哪一步？从您的角度来看，该步得分几何？

    • 在该局势下最好选从左向右的第二个分支(s2)，因为走向这一步后，无论对手如何选择，我都将获得一个+2或+3的有利局面；

  14. 为什么最小最大算法的抽象开发是很有意义的？

    • 因为最小最大算法是一个非常通用的法则，它能够用在各种游戏中而不依赖游戏的形式。

  15. 使用哪两种数据结构使得最小最大算法的实现独立于某一特殊游戏的特性？

    • stateT(表示当前游戏的状态) 和 moveT(表示一个ply的“走子”)

  16. FindBestMove函数中有3个参数，每个参数的作用是什么？

    • state记录了当前的游戏状态，我们需要根据这个参数决定下一步该如何进行；
    • depth记录了当前递归深度，因为我们不可能真的穷尽所有可能，所以在某个深度没有找到胜利情况的情形下，我们必须在当前深度作出抉择；
    • *pRating表示要返回的步骤的得分。

  17. 解释EvaluateStaticPosition函数在最小最大算法的实现过程中的作用。

    • EvalutateStaticPosition用于评估具体某个情形的分数，它根据不同游戏发生变化；
    • 这样的设计隔离了最小最大算法策略和具体游戏间的不同。