第五章搜索技术第五章搜索技术第五章 1第五章搜索技术01图搜索策略图搜索策略02盲目搜索盲目搜索03启发式搜索启发式搜索04博弈搜索博弈搜索01图搜索策略02盲目搜索03启发式搜索04博弈搜索2第五章搜索技术01图搜索策略图搜索策略02盲目搜索盲目搜索03启发式搜索启发式搜索04博弈搜索博弈搜索01图搜索策略02盲目搜索03启发式搜索04博弈搜索3第五章搜索技术如何求解问题如何求解问题？1、明晰问题如何表示、明晰问题如何表示2、选择相对合适的求解方、选择相对合适的求解方法法搜索法、归纳法、归结法、推理法、产生式、etc搜索法如何求解问题？1、明晰问题如何表示2、选择相对合适的求解方法4第五章搜索技术搜索中需要解决的基本问题：搜索中需要解决的基本问题：01020304找找到到的的解解是是否否是是最最佳解佳解是是否否会会终终止止 运运 行行/陷陷入入一一个个死循环死循环是是否否一一定定能能找找到到一一个解个解时时间间与与空空间间复复杂杂性性如何如何搜索过程：搜索过程：当前状态当前状态扫描算子集扫描算子集建立新状态建立新状态建立指针建立指针是否是否满足满足?给出解给出解答路径答路径NY搜索中需要解决的基本问题：01020304找到的解是否是最佳5第五章搜索技术(1)数据驱动：从初始状态（数据驱动：从初始状态（问题给出的条件）问题给出的条件）出发的正向搜索出发的正向搜索 (2)目的驱动：从目的目的驱动：从目的状态出发的逆向搜索状态出发的逆向搜索从从开开始始状状态态出出发发作作正正向向搜搜索索，同同时时又又从从目目的的状状态态出出发发作作逆逆向向搜搜索，直到两条路径在中间的某处汇合为止。
索，直到两条路径在中间的某处汇合为止3)双向搜索双向搜索搜索策略（按方向）搜索策略（按方向）6(1)数据驱动：从初始状态（问题给出的条件）出发的正向搜第五章搜索技术搜索策略（按信息运用度搜索策略（按信息运用度）（1）盲目搜索：）盲目搜索：在不具有对特定问题的任何有关信息的在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索2）启启发发式式搜搜索索：考考虑虑特特定定问问题题领领域域可可应应用用的的知知识识，动动态态地地确确定定调调用用操操作作算算子子的的步步骤骤，优优先先选选择择较较适适合合的的操操作作算算子子，尽量减少不必要的搜索，以求尽快地到达结束状态尽量减少不必要的搜索，以求尽快地到达结束状态搜索策略（按信息运用度）（1）盲目搜索：在不具有对特定问题的7第五章搜索技术状态状态：表示系统状态、事实等叙述型知识的一组变量或数组：表示系统状态、事实等叙述型知识的一组变量或数组：操作：操作：表示引起状态变化的过程型知识的一组关系或函数：表示引起状态变化的过程型知识的一组关系或函数：T图搜索策略图搜索策略状态空间：状态空间：利用状态变量和操作符号，表示系统或问题的有利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空间是一个四元组：关知识的符号体系，状态空间是一个四元组：状态集合状态集合 操作算子的集合操作算子的集合若干具体状态或满足某若干具体状态或满足某些性质的路径信息描述些性质的路径信息描述包含问题的初始状态是包含问题的初始状态是 的非空子集的非空子集8状态：表示系统状态、事实等叙述型知识的一组变量或数组：操第五章搜索技术求解路径求解路径：从 结点到 结点的路径。
状态空间的一个解：状态空间的一个解 状态空间的一个解状态空间的一个解：一个有限的操作算子序列图搜索策略图搜索策略9求解路径：从 结点到 结点的路径第五章搜索技术例例5.1 八数码问题的状态空间八数码问题的状态空间状态集状态集 ：所有摆法：所有摆法操作算子：操作算子：将空格向上移Up将空格向左移Left将空格向下移Down将空格向右移Right图搜索策略图搜索策略10例5.1 八数码问题的状态空间状态集 第五章搜索技术八数码八数码状态空间图状态空间图 图搜索策略图搜索策略11八数码状态空间图 图搜索策略11第五章搜索技术（状态）（操作算子）状态空间的有向图描述状态空间的有向图描述图搜索策略图搜索策略12（状态）（操作算子）状态空间的有向图描述图搜索策略12第五章搜索技术 例例5.2 旅旅行行商商问问题题（traveling salesman problem,TSP）或邮递员路径问题或邮递员路径问题家）（单位：km）可能路径：可能路径：费用为费用为375的路径的路径（A，B，C，D，E，A）图搜索策略图搜索策略13 例5.2 旅行商问题（traveling salesm第五章搜索技术 旅行推销员状态空间图（部分）旅行推销员状态空间图（部分）ABCDEA 375 A A A A B B C C C C D D D D A E E E E E E E D 路径路径:路径:路径:路径:ABCEDA ABDCE ABDECA 费用:费用:费用:费用:425 525 475 525 475 375 325 400 400 300 275 275 250 225 150 100 75 125 175 225 250 100 175 225 425.图搜索策略图搜索策略14 旅行推销员状态空间图（部分）ABCDEA 375 A第五章搜索技术02盲目搜索盲目搜索01图搜索策略图搜索策略03启发式搜索启发式搜索04博弈搜索博弈搜索02盲目搜索01图搜索策略03启发式搜索04博弈搜索15第五章搜索技术U U 1.回溯策略回溯策略UU 2.宽度优先搜索策略宽度优先搜索策略UU 3.深度优先搜索策略深度优先搜索策略盲目搜索盲目搜索16U 1.回溯策略盲目搜索16第五章搜索技术 带回溯策略的搜索带回溯策略的搜索：从初始状态出发，不停地、试探性地寻找路径，直到它到到达达目的目的或“不可解结点不可解结点”，即“死胡同”为止。
若它遇到不不可可解解结结点点就回回溯溯到路径中最近的父父结结点点上，查看该结点是否还有其他的子子结结点点未被扩展若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径盲目搜索（回溯策略）盲目搜索（回溯策略）17 带回溯策略的搜索：盲目搜索（回溯策略）17第五章搜索技术回溯搜索示意图回溯搜索示意图盲目搜索（回溯策略）盲目搜索（回溯策略）18回溯搜索示意图盲目搜索（回溯策略）18第五章搜索技术回溯搜索的算法回溯搜索的算法(1)PS（path states）表表：保保存存当当前前搜搜索索路路径径上上的的状状态态如果找到了目的，PS就是解路径上的状态有序集2)NPS（new path states）表表：新新的的路路径径状状态态表表它包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展3)NSS（no solvable states）表表：不不可可解解状状态态集集，列列出出了了找找不不到到解解题题路路径径的的状状态态如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索盲目搜索（回溯策略）盲目搜索（回溯策略）19回溯搜索的算法盲目搜索（回溯策略）19第五章搜索技术图搜索算法的回溯思想：图搜索算法的回溯思想：（1）用未处理状态表（未处理状态表（NPS）使算法能返回（回溯）到其 中任一状态。
2）用一张“死胡同死胡同”状态表（状态表（NSS）来避免算法重新搜索 无解的路径3）在PS 表表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回4）为避免陷入死循环必须对新生成的子状态进行检查对新生成的子状态进行检查，看它是否在该三张表中盲目搜索（回溯策略）盲目搜索（回溯策略）20图搜索算法的回溯思想：（1）用未处理状态表（NPS）使算法能第五章搜索技术FFopen表（表（NPS表）表）：已经生成出来但其子状态未被搜索的状态FFclosed表表（PS表和表和NSS表的合并）表的合并）：记录了已被生成扩展过的状态0S12345678910宽度优先搜索法中状态的搜索次序宽度优先搜索法中状态的搜索次序盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）21Fopen表（NPS表）：0S12345678910宽度优先第五章搜索技术例例5.3 通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起BCAABC(a)初始状态(b)目的状态 积木问题积木问题盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）22例5.3 通过搬动积木块，希望从初始状态达到一个目的状态，即第五章搜索技术操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上面。
MOVE（A，Table）：“搬搬动动积积木木A到到桌桌面上面上”操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空2）如果 Y 是积木，则积木 Y 的顶部也必须为空3）同一状态下，运用操作算子的次数不得多于一次盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）23操作算子为MOVE（X，Y）：把积木X搬到Y（积木或桌面）上第五章搜索技术ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(A,TABLE)MOVE(C,A)MOVE(C,A)MOVE(A,C)MOVE(A,C)MOVE(B,A)MOVE(B,A)MOVE(B,C)MOVE(B,C)MOVE(C,A)MOVE(C,A)MOVE(C,B)MOVE(C,B)MOVE(C,B)MOVE(C,B)MOVE(A,B)MOVE(A,B)0S1S2S3S4S5S6S7S8S9S10S没有后裔，没有后裔，失败退出失败退出积木问题的宽度优先搜索树积木问题的宽度优先搜索树盲目搜索（宽度优先策略）盲目搜索（宽度优先策略）BCAABC24ABABACCBACCCBABCABACBAABCBCBCC第五章搜索技术0S12345678910111213KK 深度优先搜索法中状态的搜索次序深度优先搜索法中状态的搜索次序0S12345678910111213KK盲目搜索（深度优先策略）盲目搜索（深度优先策略）250S12345678910111213KK 深度优先搜索法中第五章搜索技术Q Q 在深度优先搜索中，当搜索到某一个状态时，它在深度优先搜索中，当搜索到某一个状态时，它所有的子状所有的子状态以及子状态的后裔状态都必须先于该状态的兄弟状态态以及子状态的后裔状态都必须先于该状态的兄弟状态被搜索。
被搜索Q Q 为了保证找到解，应为了保证找到解，应选择合适的深度限制值选择合适的深度限制值，或采取不断加，或采取不断加大深度限制值的办法，反复搜索，直到找到解大深度限制值的办法，反复搜索，直到找到解盲目搜索（深度优先策略）盲目搜索（深度优先策略）Q Q 深度优先搜索深度优先搜索并不能保证第一次并不能保证第一次搜索到的某个状态时的路径搜索到的某个状态时的路径是是到这个状态的到这个状态的最短路径最短路径Q Q 对任何状态而言，以后的搜索有可能找到另一条通向它的路对任何状态而言，以后的搜索有可能找到另一条通向它的路径如果路径的长度对解题很关键的话，当算法多次搜索到同一径如果路径的长度对解题很关键的话，当算法多次搜索到同一个状态时，它个状态时，它应该保留最短路径应该保留最短路径26Q 在深度优先搜索中，当搜索到某一个状态时，它所有的子状态以第五章搜索技术例例5.4 卒子穿阵问题卒子穿阵问题，要求一卒子从顶部通过下图所示的阵列到达底部卒子行进中不可进入到代表敌兵驻守的区域（标注1），并不准后退假定深度限制值为5阵列图阵列图 盲目搜索（深度优先策略）盲目搜索（深度优先策略）27例5.4 卒子穿阵问题，要求一卒子从顶部通过下图所示的阵第五章搜索技术,解解死死死死死死深度限制深度限制解S0S1(1,1)S2(1,2)S3(2,2)S4(2,1)S5(3,1)S6(3,2)S7(2,3)S8(2,1)S9(3,1)S10(1,3)S18(1,4)S11(1,2)S14(1,4)S12(2,2)S15(2,4)S13(2,3)S16(3,4)S17(4,4)open表：S17、S18closed表：S0S16 卒子穿阵的深度优先搜索树28,解死死死深度限制解S0S1(1,1)S2(1,2)S3第五章搜索技术01图搜索策略图搜索策略02盲目搜索盲目搜索03启发式搜索启发式搜索04博弈搜索博弈搜索01图搜索策略02盲目搜索03启发式搜索04博弈搜索29第五章搜索技术N N“启发启发”（heuristic）：关于发现发现和发明发明操作算子操作算子及搜索搜索方法方法的研究研究。
三、启发式搜索三、启发式搜索 启发式策略：启发式策略：利用利用与问题有关的启发信息启发信息进行搜索搜索O O 启发式启发式:在状态空间搜索中，启发式启发式被定义成一系列操作操作算子算子，并能从状态空间中选择选择最有希望到达问题解的路径路径30N“启发”（heuristic）：关于发现和发明操作算子及第五章搜索技术（1）一个问题由于在问题陈述和数据获取方面固有的模糊性，模糊性，导致它没有一个确定的解导致它没有一个确定的解三、启发式搜索三、启发式搜索（2）虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长适用范围：适用范围：局限性：局限性：启发（猜猜想想）根据经验和直觉判断，可可能能得得到到的的是是次次优优解解，也可能一无所获也可能一无所获31（1）一个问题由于在问题陈述和数据获取方面固有的模糊性，导第五章搜索技术 例例5.5 5.5 一一字字棋棋在在九九宫宫棋棋盘盘上上，从从空空棋棋盘盘开开始始，双双方方轮轮流流在在棋棋盘盘上上摆摆各各自自的的棋棋子子或或（每每次次一一枚枚），谁谁先先取取得得三三子子一线（一行、一列或一条对角线）的结果就取胜。
一线（一行、一列或一条对角线）的结果就取胜和 在棋盘中不同位置对应的棋局就是问题空间中的不同状态9个位置上摆放空，空，有 39 种棋局可能的走法：三、启发式搜索三、启发式搜索 32 例5.5 一字棋在九宫棋盘上，从空棋盘开始，双方轮流在第五章搜索技术三、启发式搜索三、启发式搜索O赢的概率：赢的概率：8-5=3O赢的概率：赢的概率：8-6=2O赢的概率：赢的概率：8-4=4一字棋：9！，西洋跳棋：1078，国际象棋：10120，围棋：10761假设每步可以搜索一个棋局，用极限并行速度（10-104年/步）来处理，搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完！33三、启发式搜索O赢的概率：O赢的概率：O赢的概率：一字第五章搜索技术启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间三、启发式搜索三、启发式搜索最佳走步最佳走步34启发式搜索下缩减的状态空间三、启发式搜索最佳走步34第五章搜索技术更准确精炼描述状态更准确精炼描述状态启发信息分类陈述性过程性用于构造操作算子少而精用于构造操作算子少而精表示控制策略知识表示控制策略知识控制性没有任何控制性知识作为搜索的依据，没有任何控制性知识作为搜索的依据，搜索是随意的搜索是随意的有充分的控制知识作为依据，因而搜索的每一有充分的控制知识作为依据，因而搜索的每一步选择都是正确的，但这步选择都是正确的，但这是不现实的是不现实的35更准确精炼描述状态启发信息陈述性过程性用于构造操作算子少而精第五章搜索技术 评估函数评估函数：估计待搜索结点的“有希望”程度，并依次给它们排定次序（在open表中）。
从初始结点经过初始结点经过 结点到达目的结点结点到达目的结点的路径的最小代最小代 价估计值价估计值 一一般般地地，在在 中中，的的比比重重越越大大，越越倾倾向向于于宽宽度度优优先搜索方式，而先搜索方式，而 的比重越大，表示启发性能越强的比重越大，表示启发性能越强三、启发式搜索三、启发式搜索 ：从初始结点到初始结点到 结点结点的实际代价实际代价估计值 ：从 结点到目的结点结点到目的结点的最佳路径最佳路径估计代价值估计代价值36 评估函数：估计待搜索结点的“有希望”程度，并依次给它们排第五章搜索技术 open表：保留所有已生成而未扩展的状态closed表：记录已扩展过的状态进入open表的状态是根据其估值的大小插入到表中合适的位置，每次从表中优先取出启发估价函数值最小的状态加以扩展三、启发式搜索三、启发式搜索设计评估函数的目标：设计评估函数的目标：利用有限的信息作出一个较精确的评估函数利用有限的信息作出一个较精确的评估函数启启发发式式图图搜搜索索法法的的基基本本特特点点：寻找并设计一个与问题有关的 及构出 ，然后以 的大小来排列待扩展状态的次序，每次选择 值最小者进行扩展37 open表：保留所有已生成而未扩展的状态。
三、启发式搜第五章搜索技术A算法（基于评估函数的算法（基于评估函数的加权启发式图搜索算法加权启发式图搜索算法）实现步骤实现步骤2 2、若、若open表为空，则搜索失败，退出表为空，则搜索失败，退出3 3、移出、移出openopen表中第一个节点表中第一个节点N N放入放入closed表中，并顺序编号表中，并顺序编号n n4 4、若目标结点把附有、若目标结点把附有 的初始的初始 ,则搜索成功，结束则搜索成功，结束5 5、若、若N N不可扩展，则转步骤不可扩展，则转步骤2 26 6、扩展、扩展N N，生成一组附有，生成一组附有 的子结点，对这组子结点进行处理：的子结点，对这组子结点进行处理：考察是否有已在考察是否有已在open或或closed表中存在的结点若有则再考察表中存在的结点若有则再考察其中有无其中有无N N的先辈结点，有则删除，同时考虑是否修改表中结点的先辈结点，有则删除，同时考虑是否修改表中结点及其后裔指针和及其后裔指针和 的值的值 为其余子结点配上指向为其余子结点配上指向N N的返回指针后放入的返回指针后放入open表中，并排序，表中，并排序，转步骤转步骤2 21 1、把附有、把附有 放入放入openopen表表A算法（基于评估函数的加权启发式图搜索算法）实现步骤2、若o38第五章搜索技术A算法描述算法描述procedure heuristic_searchopen：=start；closed：=；f(s)：=g(s)+h(s)；*初始化while open dobegin从open表中删除第一个状态，称之为n；if n=目的状态then return(success)；生成n的所有子状态；if n没有任何子状态then continue；for n的每个子状态docase子状态is not already on open表or closed表；begin计算该子状态的估价函数值；将该子状态加到open表中；end；39A算法描述procedure heuristic_searc第五章搜索技术5.4.3 A搜索算法case子状态is already on open表：if该子状态是沿着一条比在open表已有的更短路径而到达then 记录更短路径走向及其估价函数值；case子状态is already on closed表：if该子状态是沿着一条比在closed表已有的更短路径而到达thenbegin将该子状态从closed表移到open表中；记录更短路径走向及其估价函数值；end；case end；将n放入closed表中；根据估价函数值，从小到大重新排列open表；end；*open表中结点已耗尽return(failure)；end.405.4.3 A搜索算法case子状态is already 第五章搜索技术每每次次重重复复时时，A搜搜索索算算法法从从open表表中中取取出出第第一一个个状状态态，如如果果该状态满足目的条件，则算法返回到该状态的搜索路径。
该状态满足目的条件，则算法返回到该状态的搜索路径如如果果open表表的的第第一一个个状状态态不不是是目目的的状状态态，则则算算法法利利用用与与之之相相匹匹配配的的一一系系列列操操作作算算子子进进行行相相应应的的操操作作来来产产生生它它的的子子状状态态如如果果某某个个子子状状态态已已在在open表表（或或closed表表）中中出出现现过过，即即该该状状态态再再一一次次被被发发现现时时，则则通通过过刷刷新新它它的的祖祖先先状状态态的的历历史史记记录录，使算法极有可能找到到达目的状态的更短的路径使算法极有可能找到到达目的状态的更短的路径接接着着，A搜搜索索算算法法open表表中中每每个个状状态态的的估估价价函函数数值值，按按照照值值的的大大小小重重新新排排序序，将将值值最最小小的的状状态态放放在在表表头头，使使其其第第一一个个被被扩展三、启发式搜索三、启发式搜索41每次重复时，A搜索算法从open表中取出第一个状态，如果该状第五章搜索技术三、启发式搜索三、启发式搜索42三、启发式搜索42第五章搜索技术例例5.7 利用A搜索算法求解八数码问题的搜索树，其评估函数定义为 ：状态的深度，每步为单位代价。
以“不在位”的数码数作为启发信息的度量三、启发式搜索三、启发式搜索-A算法算法43例5.7 利用A搜索算法求解八数码问题的搜索树，其评估函第五章搜索技术4444第五章搜索技术open表和closed表内状态排列的变化情况 三、启发式搜索三、启发式搜索45open表和closed表内状态排列的变化情况 三、启发式搜第五章搜索技术如果某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定能搜索到解，并且一定能搜索到最优的解而结束三、启发式搜索三、启发式搜索-A*算法算法定义：h*(n)为状态n到目的状态的最优路径的代价，则当A算法的启发函数h(n)小于等于h*(n)，即满足h(n)h*(n)，对所有结点n46如果某一问题有解，那么利用A*搜索算法对该问题进行搜索则一定第五章搜索技术1.可采纳性可采纳性 当一个搜索算法在最短路径存在时能保证在有限步内找到它，就称它是可采纳的A*搜索算法的特性搜索算法的特性所有的所有的A*A*算法都是可采纳的算法都是可采纳的最优评估函数：最优评估函数：f*(n)f*(n)：起点出发通过：起点出发通过n n状态而到达目的状态的状态而到达目的状态的最佳路径最佳路径的的总代价总代价值值g*(n)g*(n)：起点到：起点到n n状态的状态的最短路径最短路径代价值代价值h*(n)h*(n)：n n状态到目的状态的状态到目的状态的最短路径最短路径的代价值的代价值471.可采纳性A*搜索算法的特性所有的A*算法都是可采纳的。
第五章搜索技术2.2.单调性单调性 在整个搜索空间都是局部可采纳局部可采纳的一个状态和任一个子状态之间的差由差由该状态与其子状态之间之间的实际代价所限定的实际代价所限定A*搜索算法的特性搜索算法的特性如果某一启发函数满足：如果某一启发函数满足：对所有状态对所有状态ni和和nj，其中，其中nj是是ni的后裔，满足的后裔，满足 ，其中，其中cost(ni,nj)是从是从ni到到nj的实际代价的实际代价目的状态的启发函数值为目的状态的启发函数值为0 0或或则称该启发函数则称该启发函数h(n)h(n)是单调的是单调的482.单调性 A*搜索算法的特性如果某一启发函数满足：48第五章搜索技术3.信息性信息性 在两个A*启发策略的 中，如果对搜索空间中的任一状态n都有 ，就称策略 具有更多的信息性A*搜索算法的特性搜索算法的特性信息性越多，所搜索的状态数就越少，但所需要的计算时间越信息性越多，所搜索的状态数就越少，但所需要的计算时间越多493.信息性A*搜索算法的特性信息性越多，所搜索的状态数就越第五章搜索技术04博弈搜索博弈搜索03启发式搜索启发式搜索01图搜索策略图搜索策略02盲目搜索盲目搜索04博弈搜索03启发式搜索01图搜索策略02盲目搜索50第五章搜索技术1914世上第一个计算机游戏1952世界上第一个跳棋程序1979西洋双陆棋程序1997“深蓝”PK卡斯帕罗夫2006浪潮天梭PK许银川2011Watson上场危险边缘四、博弈搜索四、博弈搜索2016AlhoGoPK李世石2017Master、Zero-剪枝算法蒙特卡洛树搜索+信心上限决策深度学习+增强学习+=1914世上第一个计算机游戏1952世界上第一个跳棋程序1951第五章搜索技术1.蒙特卡洛树搜索过程蒙特卡洛树搜索过程选择：选择：以当前棋局为根节点，自上而下地选择一个落子点；扩展：扩展：向选定的节点添加一个或多个子节点；模拟：模拟：对扩展出的节点用蒙特卡罗方法进行模拟；回传：回传：根据模拟结果依次向上更新祖先节点的估计值。
存在不足：存在不足：1、选择范围是全体可下子点；2、每次模拟必须一下到底，完成整局模拟直到知道分出胜负为止1.蒙特卡洛树搜索过程存在不足：52第五章搜索技术信心上限决策信心上限决策1、优先选择到目前为止胜率最大的节点；2、优先选择到目前为止模you拟次数较少的节点 ：节点j目前的收益（比如获胜概率）；n：是目前为止的总的模拟次数；：是节点j目前的模拟次数；c：是加权系数信心上限决策 ：节点j目前的收益（比如获胜概率）；53p经常不断地学习,你就什么都知道你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后经常不断地学习,你就什么都知道你知道得越多,你就越有力量写54感谢聆听不足之处请大家批评指导Please Criticize And Guide The Shortcomings结束语讲师：XXXXXX XX年XX月XX日 感谢聆听结束语讲师：XXXXXX 55。