ACM专题搜索算法讲解.ppt

文档介绍：ACM专题讲座——,可以看作一个搜索过程。我们遇到的很多智力游戏问题,如传教士和野人问题。有3个传教士和3个野人来到河边准备渡河,河岸有一条船,每次最多可乘坐2个人。问传教士为安全起见,应如何规划摆渡方案,使得在任何时刻,在河的两岸以及船上传教士人数不能少于野人的人数?对这个问题,在每一次渡河后,都会有几种渡河方案供选择,究竟哪种方案最有利?这就是搜索问题。,一般我们都转换为状态空间的搜索问题。如传教士和野人问题,可用在河左岸的传教士人数、野人人数和船的情况来表示。即,初始时状态为(3,3,1),结束状态为(0,0,0),而中间状态可表示为(2,2,0)、(3,2,1)等等。,可以看出这类问题的解,就是一个合法状态的序列,其中序列中第一个状态是问题的初始状态,而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图:,属于盲目搜索的一种,它是这样一种策略:首先将规则给出一个固定的排序,在搜索时,对当前状态依次检测每一条规则,在当前状态未使用过的规则中找到第一条可应用规则,应用于当前状态,得到的新状态重新设置为当前状态,并重复以上搜索。如果当前状态无规则可用,或者所有规则已经被试探过仍未找到问题的解,则将当前状态的前一个状态(即直接生成该状态的状态)设置为当前状态。重复以上搜索,直到找到问题的解,或已试探过所有可能仍找不到问题的解为止。:()()()()((1,1))Q漓号贱道扑层契爵茶划鲤尿偶碍墨添患债乃茅乡浆诸衍囱变牢弥荒尧闸刑ACM专题搜索算法讲解ACM专题搜索算法讲解