事物的形状 126 笑和哭 130 小题大作 第4章停机定理(计箅的理论) 136 计算与计算的算氵:… 136 鳄梨酱算法… ……………137 欧几里得算法 38 图灵的不可思议的圹器… t39 不可计算 144 忙碌海狸对策 146 图灵机对策 148 根据无隈性吗 l50 图灵一丘奇论题 15l 形式和内容 52 不可判定 ∴157 制造智慧 限度就是可数无穷… ………170 停机概率… 难耐埘问… L76 P和NP …∷178 计算的模型…… 180 第5章单纯形法(最优化理论) 【83 旅行者的数学 线性地思考 186 单纯形法…… 190 对偶和食语 195 整数规划 ……l98 :99 所以阏络就流功起釆了… …20
高速公路车流 民众的福利 204 登山 …209 网络中的路线… 四城市空运问題 212 让你的投资轶利最大 215 文献日录 人名索引 229 名词索引… ……………232 作者自述……………………………………………………………244
第1章极小极大定理(对策论) 你死我活的对策 在日常闲谈中,“game(游戏)”常被人们认为仅仅是学童的娱 乐,是一种为逃避家庭作业和钢琴课来消磨他们的日子的一种方 法,多半是玩诸如蒙眼捉人、追逐游戏或者捉迷藏之类的游戏但 对许多成人而言,“game(对策)”这一术语使人想起在充满烟雾的 咖啡馆中躬身坐在棋盘前苦练棋艺的棋手,或者在同样是充满烟 雾的董事会的会议室里的实业巨头的形象,他们都在拼命寻求能 使他们比竞争对手处于有利地位的策略.后者这些情景,对策的 结局取决于局中人所采取的策略,就构成了我们现在称为数学对 策论的出发点而使对策论成为一种“理论”的基本组成部分,不 是探索性的论据、经验法则趣闻的根据、荒诞故事的收集,而是 极小极大点的概念,对策中所有局中人的一组最优策略.让我们 先从一个非常实际的例子开始来说明一般的概念 1943年初,新几内亚岛①的北半部由日本控制,而同盟国控 制了该岛的南半部.情报部门的报告指出日本正调集一支护卫 舰队增授其岛上的部队.该护卫舰队可以采取下列两条航线中 的一条:(1)新不列颠岛以北,但预报那里将有雨而且能见度很 差,或(2)南部航线,预期那里的天气晴好.据估计,不论走哪条 ①译注:仅次于格陵兰岛的世界第二大岛
象笔做经默学方续 路线都需要有¨六程 根据收到的这些情报估计,同盟国最高统帅麦克阿瑟(1ou glas Mac Arthr)将车命令同盟国空军西南太平洋地区司令肯尼 ( George C. Kenney)将付日本护卫舰队给予最大可能的打击 肯尼叮以采取把他门大部分侦察机派往南线或北线的选拉.他 的目的是要极大化河期望的能轰炸到该护卫舰队的天数,所以 他要计地的侦察机尽快找到该护卫舰队.因此,肯尼有两种选 择:(1)用他的大多数j察机搜索北线,或(2)集中搜索南线结 果(用对策论中的说就是“支付¨)将由能让肯尼支配k轰炸 到该舰队的叮期η的天数来度量.而临权方司令官的总的情况 叮以用图1.l的¨对策树”来表示,图中概述了称为俾斯麦海每战 3!的情况 航行北线 航行南线 肯尼 肯尼 搜索北戴/搜索 搜索、搜索南线 肯尼 南线 北戴 查炸的天敦 图1,俾斯麦海战的付策树 (用专业术语来讲,付策论学家把这类对策树称为对策的扩张形 式 图1.1应按以下方法读出:从顶部结点开始.日方司令官可 选择左分支(航行北线)或右分支(航行南线)这两个分支的每 个都引出一个标为“肯尼”的结点,它指明这些结点是肯尼将 军的决策点肯尼的选择或是左分支(搜寻北线),或背选择右分 支(搜寻南线)在以方令官做出他们的选择之后,在树的底 部的每个结点的下面列出」一个数字如果双方司令宫的决策
集秦大难游论 导致该特定终点的话,这个数字就是肯尼能利用的情报估汁声 称的轰炸的天数.然,司令官实阿:上邦不按图上建议的顺的 样子做出他们的选地.每个可令都是在不知道对将 公怎样做的情况下独不取行动 然在做出他们的策时,肯尼将军和方令官所六注 的事悄截然相饭:对将军来说什么事情是好事,对力川令 自来说就是坯事,之然.因此、我们用轰炸大数來衡量同盟 国的支付,面把这个亍的负值作为讨H方的“回报¨.所以论 哪一方融、另方就是输.这就是听谓的¨零和局势的-例 子,因为双方令F的攴付加起柬为餮 表达整个局势的吏为简洁的方法是使用所谓的支付矩阵 它定义了对策的正规开式.下面就是俾斯麦海战的攴付矩表 示矩阵的行表示肯尼将车能用的选择而矩阵的例代表目方i↓ 令官排的选掷,按约定,矩阵中的各顼是¨行局中人¨在现在 这种情形,就是肯将钅和同盟国的攴付.因为同盟国和万听 关注的事情恰好相:,列局中人¨(日方的支付就是这些数 的负值.参照图!.1中所示对策树,我们看到从树顶到树底部结 点的每条路径下面的数值和这些支付是相问同的,给定这些能 采取的行动方向和攴付结构,要决定的问题是:应作出什么朴的 合理的命令 航行北线 航行南线 于盟到 搜索北线 搜索南线 仰期攴海战的支∵年阵 我们]假定肯想嚶极大化他能够轰炸H方的天数.如果 他搜索北线,不管,次定航行走哪个向都能保证有人的 轰炸时间.但是如果他搜索南线,如果日方船队航行北线.则片