KM算法是通过给每个顶点一个标号来把求最大.ppt

KM算法是通过给每个顶点一个标号 叫做顶标 来把求最大权匹配的问题转化为求完备匹配的问题的 设顶点Xi的顶标为A i 顶点Yi的顶标为B i 顶点Xi与Yj之间的边权为w i j 在算法执行过程中的任一时刻 对于任一条边 i j A i B j w i j 始终成立 KM算法的正确性基于以下定理 若由二分图中所有满足A i B j w i j 的边 i j 构成的子图 称做相等子图 有完备匹配 那么这个完备匹配就是二分图的最大权匹配 初始时为了使A i B j w i j 恒成立 令A i 为所有与顶点Xi关联的边的最大权 B j 0 如果当前的相等子图没有完备匹配 就按下面的方法修改顶标以使扩大相等子图 直到相等子图具有完备匹配为止 我们求当前相等子图的完备匹配失败了 是因为对于某个X顶点 我们找不到一条从它出发的交错路 这时我们获得了一棵交错树 它的叶子结点全部是X顶点 现在我们把交错树中X顶点的顶标全都减小某个值d Y顶点的顶标全都增加同一个值d d min A i B j w i j Xi在交错树中 Yi不在交错树中 状态空间搜索 胡俊峰2013 11 29 状态空间搜索 适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料 状态空间搜索 适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料 状态空间搜索 适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料 盲目搜索方法 定义状态 state 对问题在某一时刻进展情况的数学描述状态转移 state transition 问题从一种状态到转移到另一种 或几种 状态的操作状态空间 statespace 问题可以处于的所有状态 盲目搜索算法 深度优先搜索广度优先搜索 随机化搜索 深度优先搜索 Depth firstSearch 搜索顺序 1 2 4 8 走迷宫 深度优先搜索 实现 栈式和递归空间开销 栈的深度 非递归的实现框架 voidDfs inta while 栈不为且尚未到达目标状态 取出 pop 栈顶元素进行扩展将扩展出的元素依次压入 push 栈 栈的应用迷宫老鼠 解决方案 尽可能前进 回溯 记录访问过的状态 具体 依次探查所有可能的没有被探查过的方向对探查过的位置进行标记无法继续前进则回溯 在某一位置 i j 进行试探 N i 1 j w i j 1 i j E i j 1 S i 1 j drection 4 2 令k取0 1 2 3之一 则试探位置为 g i direction k 0 h j direction k 1 算法设计 走一步 记一步 方向试探前进 push current 无法前进 current pop 求解迷宫中一条路径的方法 从入口开始 对每个当前位置沿 E S W N 四个方向逐一进行试探 当选定一个可通行的方向后 把当前所在位置及所选的方向记录下来 然后从下一个位置开始继续探索 若在当前位置探索不到可通行的方向 则沿原路一步一步退回来 每后退一步 接着在该点试尚未试过的一个方向 如此重复直到到达出口 用一个栈记录走过的位置 栈中每个元素包括三项 分别记录当前位置的行坐标 列坐标以及在该位置上所选的方向 即directon数组的下标值 广度优先搜索 Breadth firstSearch 搜索顺序 1 2 3 4 5 广度优先搜索 实现 队列空间开销 可扩展结点 已扩展结点标记 广度优先搜索的实现框架 voidBFS while 队列可扩展且尚未到达目标状态 从队首依次取出队列中未扩展的结点进行扩展 并将新结点加入队尾 农夫 狼 羊 菜过河 状态 0 1 0 1 0 1分别代表两岸操作 算符 4种 运farmer wolf运farmer sheep运farmer cabbage运farmer状态空间大小 24 16Map 2 2 2 2 可以转化为迷宫问题 状态 路口操作 通路限制条件 死胡同无形的迷宫 地毯式搜索 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 如何求得最优解 广度优先搜索 层层推进搜索的层数不超过答案所在的层数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 广度优先搜索 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 队列的特点 队列是一种特殊的线性表 只允许在表的一端有插入操作 而在另一端有删除操作 队头 允许删除的这一端叫队列的头 队尾 允许插入的这一端叫队列的尾 空队列 当队列中没有任何元素时 称为空队列 进队 出队 队列的插入操作通常称为进队列或入队列 队列的删除操作通常称为退队列或出队列 队列的基本概念 队列也称作先进先出表 FirstInFirstOut FIFO表 支持队尾插入 队头删除操作 a0a1a2an 1 入队列 队头 队尾 出队列 队列的示意图 队列ADT ADTQueueisoperationsQueuecreateEmptyQueue void 创建一个空队列 intisEmptyQueue Queuequ 判队列qu是否为空队列 voidenQueue Queuequ DataTypex 往队列qu尾部插入一个值为x的元素 voiddeQueue Queuequ 从队列qu头部删除一个元素 DataTypefrontQueue Queuequ 求队列qu头部元素的值 endADTQueue 基于环形存储结构的队列实现 front rear modMAXSIZE enQueue rear rear 1 MAXSIZEqBuffer rear inData deQueue outData qBuffer rear rear rear 1 MAXSIZE 基于环形存储结构的队列实现 把数组paqu q MAXNUM 从逻辑上看成一个环 这种队列称为环形队列 当表中已有MAXNUM 1个结点时 如果还要插入 paqu r和paqu f就会重合 而这与空队列的情形相混 为区分空队列与满队列两种情况的环形队列 一般是牺牲队列中的一个结点 当队列中已有MAXNUM 1个结点时就称满 再要插入就发生溢出 环形队列 顺序结构队列的类型定义 顺序结构队列的操作定义 ADT BitwiseXORIllustration k i j k i j k i j j k 深度与广度优先搜索比较 深度优先搜索栈式结构空间开销小最优解需遍历所有解才能确定广度优先搜索队列结构空间开销大最先找到最优解同学补充 状态表示及状态变换 生成 用一个整数表达一个状态 109用1 8表示8个数字 9表示空位相对于x所在位置 Up down left right四个位置的数字有可能移动 位置变换 3 3 1 1数值变化 d1 d2 ten p d2 ten p d1 广度优先搜索的变形 双向广度优先搜索 双向广度优先搜索 搜索顺序两个队列 分别来自初始结点和目标结点的扩展 交替扩展 每次都选择较小的一个队列进行扩展 优势扩展结点数明显减少存储需求降低条件初始状态和目标状态唯一只适用于最优解问题 完全二叉树 堆 优先队列 A 算法 F G H 搜索与博弈 经典游戏博弈树与极大极小过程alpha beta剪枝棋类游戏设计 概念与研究领域 什么是博弈 谷歌说 百度知道 人生是永不停息的博弈过程 博弈意味着通过选择合适策略达到合意结果 作为博弈者 最佳策略是最大程度地利用游戏规则 作为社会的最佳策略 是通过规则引导社会整体福利的增加 博弈 这个词听起来高深莫测 其实它就是 游戏 的意思 更准确点说 是可以分出胜负的游戏 博弈论如果直译就是 游戏理论 不妨说 博弈论是通过 玩游戏 获得人生竞争知识的 研究领域 博弈算法计算机的优势快速 内存大更严密人工智能领域主要研究领域挑战条件 两方 公平 博弈树 双方博弈背后隐式图 我们可以把所处的局面看作是一个状态 那么博弈的过程就可以看成是在状态空间中遍历 博弈树 由于双方博弈的过程具有明显的层次关系 我们可以依此构建一棵博弈树 图 象棋的4层博弈树 博弈树 博弈树上的搜索数量级极大中国象棋 平均一次40种走法 5层就有10 8个节点 只能向下搜索几层为几层后的状态给出估值自下而上依次对每个状态进行估值 极大极小过程 约定双方都用最好的策略把 甲方得分 乙方得分 作为一个局面的估值 MAX MIN节点甲方 在子节点中选择估值最大的节点 MAX 即Score A Max Ai Ai F A 乙方 在子节点中选择估值最小的节点 MIN 即Score B Min Bi Bi F B 图 一字棋极大极小过程 图 伪代码 极大极小算法 负极大值算法 极大极小算法的改进修改了返回估值的符号避免了极大极小的交替 图 伪代码 负极大值算法 剪枝 值MAX节点的 值 当前已经展开的几个后继节点中的最大值 它是该结点估值的下界 MIN节点的 值 当前已经展开的几个后继节点中的最小值 它是该结点估值的上界 易见规律 一个正在展开的MAX结点的 值永不下降 一个正在展开的MIN结点的 值永不上升 剪枝