计算机算法设计与分析_第五章__2.pdf

第五章 基本检索与周游 1 第五章 基本检索与周游  1. 一般方法 2. 二元树周游 3. 树的周游 4. 图的检索和周游  5. 对策树 2 5. 对策树 博弈问题描述 – 古语有云，世事如棋。生活中每个人如同棋手，其每 一个行为如同在一张看不见的棋盘上布一个子，精明 慎重的棋手们相互揣摩、相互牵制，人人争赢，下出 诸多精彩纷呈、变化多端的棋局。 – 博弈论就是研究“棋手们”“出棋”着数中理性化、 逻辑化的部分，并将其系统化为一门科学。换句话说， 就是研究个体如何在错综复杂的相互影响中做出最合 理的策略。 3 5. 对策树 博弈问题描述 – 博弈论(Game Theory)，亦名对策论、赛局理论，属 应用数学的一个分支, 目前在生物学、经济学、国际 关系、计算机科学、政治学、军事战略和其他很多学 科都有广泛的应用。 – 博弈论衍生于古老的博弈游戏而得名，如象棋、扑 克等。数学家们将具体的问题抽象化，通过建立自完 备的逻辑框架、体系研究其规律及变化。 4 5. 对策树 博弈问题描述 – 双人完备信息博弈： 一人一步:两位选手对垒，轮流走步， 双方信息完备:每一方不仅知道对方已经走过的棋 步，而且还能估计出对方未来的走步。 零和:对弈的结果是一方赢，另一方输；或者双方 和局。 例如，有象棋、围棋等。 我们只讨论双人完备信息博弈问题 – 用对策树的模型来描述对弈局势。 5 5. 对策树 拾火柴棍游戏 – 在盘面上放n支火柴，由弈者A和B两人参加比赛。 – 规则：两名弈者轮流从盘上取走火柴，每次从盘中取 走1，2 或3支火柴为合法着，否则为非法着。 – 胜负：拿走盘中最后一支火柴的弈者为负，而对方赢。 – 棋局：以盘中剩下的火柴数来表示当前时刻的棋局。 – 状态：拾火柴棍游戏在任一时刻的状态由该时刻的棋 局和轮到走下一着的弈者一起决定。 – 终局：表示胜局、负局或和局情况的棋局。 – 非终止棋局：非终局的其它棋局。 – 在本游戏中只有一种终局形式，即盘中没有火柴棍了， 必有一人胜，另一人负，不会出现和局 6 5. 对策树  数学模型 – 棋局序列C ，C ，…，C 称为有效(棋局)序列，如果： 1 2 m ① C 是开始棋局； 1 ② C 不是终止棋局，i ＝1，2，…，m-1； i ③ 由C 按下述规则走到C ：若i是奇数，则A走一 i i ＋1 合法步骤；若i是偶数，则B走一合法步骤。 – 以C 为终局的一个有效棋局序列C ，C ，…，C 是 m