B2C电子商务的“集成式”物流解决方案.

5.1搜索的概念及种类搜索是人工智能的一个基本问题，是推理不可分割的一部分。一个问题的求解过程其实就是搜索过程，所以搜索实际上就是求解问题的一种方法。与搜索技术相对应的知识表示法一般有两种：状态空间表示法、另一种是与/或树表示法。第五章状态空间搜索策略一．搜索的概念现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步的搜索着前进。在这一过程中，所要解决的问题是如何寻找可利用的知识，即如西南科技大学信息工程学院2何确定推理路线，才能使在付出尽量少的代价的前提下把问题圆满解决。如果存在多条路线可实现对问题求解，那就又存在这样的问题，即如何从这多条求解路线中，选出求解代价最小的一条，以提高求解程序的运行效率。概念：根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，称为搜索。两层含义：1)要找到从初始事实到问题最终答案的一条推理路线；2)找到的这条路线是时间和空间复杂度最小的求解路线。西南科技大学信息工程学院3二．搜索的种类：1．盲目搜索（无信息搜索）在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略，即问题本身的特性对搜索控制策略没有如何影响，使得搜索带有盲目性，效率不高。缺点：如果碰到比较复杂的问题时，求解的效率可能相当低。所以盲目搜索只用于解决比较简单得问题。2．启发式搜索（有信息搜索）在搜索过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。西南科技大学信息工程学院4启发式搜索由于考虑到问题本身的特性并利用这些特性，从而使搜索求解的效率更高，更易于求解复杂的问题。但并不是对所有的问题都能方便地抽取出问题的相关特性和信息，因此尽管启发式搜索好于盲目搜索，但盲目搜索也会在很多问题的求解中得到应用。在状态空间表示法中，可以采用图示的方式表示，即状态空间图。状态空间图是一个有向图。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。5.2盲目搜索策略如果从状态空间图的角度来看，则对问题的求解就相当于在有向图上寻找一条从某一节点（初始状态节点）到另一节点（目标状态节点）的路径。西南科技大学信息工程学院5但是，若要把表示问题的整个状态空间都存入计算机，往往需要占据巨大的存储空间，尤其对比较复杂的问题，这几乎是不可能实现的，并且一般也无这种必要。因为对于一个具体的问题，其解往往只与状态空间的一部分相关，只要计算机生成并存储与问题有关的解状态空间部分，即可将问题解决。但如何来生成并存储与问题有关的部分状态空间呢？这就是人工智能中所研究的搜索技术问题。一．状态空间图的搜索策略搜索法求解问题的基本思想：首先将问题的初始状态（即状态空间图中的初始节点）当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态（或称后继节点），然后检查这组后继状态中有没有目标状态。如果有，则说明西南科技大学信息工程学院6搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。几个概念：扩展：用合适的算符对某个节点进行操作生成一组后继节点的过程。扩展过程实际上就是求后继节点的过程。已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则称此节点为已扩展节点。未扩展节点：对状态空间图中那些尚未求出其后继节点的节点称为未扩展节点。西南科技大学信息工程学院7OPEN和CLOSED表：为了记录搜索过程，建立两个名字分别为OPEN和CLOSED的表，用于分别存放未扩展节点和已扩展节点。它们的数据结构如下：表1OPEN表结构状态节点父节点表2CLOSED表结构编号状态节点父节点西南科技大学信息工程学院8状态空间图的搜索算法如下：Step1：建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中。Step2：建立CLOSED表，且置为空表。Step3：判断OPEN表是否为空表。若为空，则问题无解，结束。Step5：考察节点n是否为目标节点。若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。Step4：选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n。Step6：扩展节点n生成一组不是n的祖先的后继节点，西南科技大学信息工程学院9并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。Step7：对那些未曾在G中出现过的（即未曾在OPEN表上或CLOSED表上出现过的）M中的节点，设置一个指向父节点（即节点n）的指针，并把这些节点加入OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点（即节点n）的指针；对于那些先前已在G中出现并已在CLOSED表中的那些M中的节点，确定是否需要修改通向它们后继节点的指针。Step8：按某一任意方式或按某种策略重排OPEN表中节点的顺序。Step9：转Step3。搜索过程的流程图如图1所示。西南科技大学信息工程学院10YNNY开始初始化：把S0放入OPEN中，CLOSED表置空把OPEN表中的第一个节点(n)移至CLOSED表中若n的后继节点未曾在搜索图G中出现，则将其放入OPEN表的末端，并提供返回节点n的指针中。根据后继节点在搜索图G中的出现情况修改指针方向重排OPEN表失败，退出成功，退出OPEN为空表？n为目标节点吗？图1状态空间的搜索过程框图西南科技大学信息工程学院11这一搜索算法具有通用性。以后讨论的各种搜索策略都可以看作是它的一个特例。各种策略的主要区别就在于Step8对OPEN表中的节点排序的算法不同。在Step8中，对OPEN表中的节点排序时，主要希望从未扩展节点中选出一个最有希望的节点作为Step4扩展来用。若这时的排序是任意的或者是盲目的，则搜索即为盲目搜索；如果是按某种启发信息或准则进行排序，则其就是启发式搜索。搜索图：在搜索过程中，生成了一个图G，它是问题状态空间图的一部分，称为搜索图。搜索树：由搜索图G中的所有节点及Step7设置的指向父节点的反向指针，所构成的集合T称为搜索树。西南科技大学信息工程学院12搜索图G中，除初始节点S0外的每个节点，都有一个指向G中一个父辈节点的指针，该父辈节点就定为搜索树中对应节点的唯一父辈节点。搜索解：在搜索过程中，当某个被选作扩展的节点，是目标节点时（在Step5），则就找到了问题的一个解。所找到的解就是从初始节点S0到目标节点路径上的算符所构成的序列。而路径则是通过目标节点按Step7设置的指针指向初始节点回溯而得到的。如果在搜索中一直找不到目标节点，而且OPEN表中又不再具有可供扩展的节点，则搜索失败，在Step3退出结束。这样的搜索过程实际上就是问题的求解过程。在利用状态空间搜索法求解问题时，并不是将整个问题的状态空间图全部输入计算机，而是只存入与问题解有关的西南科技大学信息工程学院13部分状态空间图。这种部分状态空间图是在搜索过程中生成的，并且每前进一部，都要检查是否到达目标节点，这样就可以尽量地少生成与问题无关地状态，从而提高了解题效率，节省了存储空间。二．宽度优先搜索策略宽度优先搜索又称为广度优先搜索，是一种盲目搜索。其基本思想如下：从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展（或搜索）之前，必须完成对当前层的所有节点的扩展（或搜索）。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：西南科技大学信息工程学院14先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图2所示。SLOMFPQNFFF图2宽度优先搜索过程起始节点西南科技大学信息工程学院15Step6：对节点n进行扩展，将它的所有后继节点放入OPEN表的末端，并为这些后继节点设置一个指向父节点n的指针，然后转Step2。算法2：状态空间图的宽度优先搜索算法Step1：把初始节点S0放入OPEN表中。Step2：如果OPEN表是空表，则没有解，失败退出。否则继续。Step3：把OPEN表中的第一个节点（记为节点n）移出，并放入CLOSED表中。Step4：判断节点n是否为目标节点。若是，则求解结束，并用回溯法找出解的路径，退出；否则继续执行Step5。Step5：若节点n不可扩展，转Step2；否则继续执行Step6。西南科技大学信息工程学院16宽度优先算法的流程图如图3所示。YYNNY开始把S0放入OPEN把OPEN表中的第一个节点(n)移出放入CLOSED表扩展节点n，将其后继节点放入OPEN表的末端为每个后继节点配置指向n的指针失败，退出回溯求解路径OPEN空表？n为目标节点吗？节点n可扩展吗？N成功，退出图3宽度优先算法框图西南科技大学信息工程学院17例1八数码难题：设在3*3的一个方格棋盘上，摆放着8个数码1、2、3、4、5、6、7、8，有一个方格是空格，其初始状态如图4(a)所示，要求对空格执行下列的操作（或算符）：空格左移，空格上移，空格右移，空格下移使八个数据最终按图4(b)的格式摆放，如图4(b)称为目标状态Sg。要求寻找从初始状态到目标状态的路径。28314765S0(a)初始状态12384765Sg(b)目标状态图4八数码难题西南科技大学信息工程学院18解：应用宽度优先搜索，可以得到如图5的搜索树。搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按逆时针方向移动空格）。从图5中可以看出，其解的路径为：S0→3→8→16→27。缺点：宽度优先搜索的盲目性较大，当目标节点距离初始节点较远时，将会产生大量的无用节点。搜索效率低。优点：深度优先搜索策略是完备的，即只要问题有解，用宽度优先搜索总可以找到它的解，而且是搜索树中，从初始节点到目标节点的路径最短的解。西南科技大学信息工程学院19图5八数码难题的宽度优先搜索树Sg83214765813247652837461528371465123784651238476528371465832147652341876528364175283167542814376528314576123847652837146583214765231847652831647528316475281437652831457623184765S02831476512831476523184765283164752831476523456789101113121415161718192021222324252627西南科技大学信息工程学院20首先扩展最新产生的（即最深的）节点，即从初始节点S0开始，在其后继节点中任选择一个节点，对其进行考察。若它不是目标节点，则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依此类推，一直搜索下去，当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。搜索过程如图6所示，其搜索算法见算法3。三．深度优先搜索深度优先搜索也是一种盲目搜索策略，其基本思想为：西南科技大学信息工程学院21算法3：状态空间图的深度优先搜索算法Step1：把初始节点S0放入OPEN表中。Step2：如果OPEN表为空，则问题无解，失败退出。Step3：从OPEN表中将其第一个节点（节点n）移出，并放入已扩展节点表CLOSED表中。Step4：考察节点n是否为目标节点。若是，则找到问题的解，用回溯法求解的路径，退出；否则继续执行Step5。Step5：若节点n不可扩展，转Step2。Step6：扩展节点n，将其后继节点放到OPEN表的前端，并为其设置指向节点n的指针，然后转Step2。深度优先搜索算法的流程图如图7所示。西南科技大学信息工程学院22YYNNY开始把S0放入OPEN把OPEN表中的第一个节点(n)移