会计学图3-2迷宫(mígōng)的有向图表示图3-3八数码问题(wèntí)示例3.1.2状态图搜索1.搜索方式●树式搜索●线式搜索2.搜索策略(cèlüè)●盲目搜索●启发式(heuristic)搜索图3-4OPEN表与CLOSED表示(biǎoshì)例树式搜索算法：(1)删除N的先辈节点(如果有的话)。(2)对已存在于OPEN表的节点(如果有的话)也删除之；但删除之前要比较(bǐjiào)其返回初始节点的新路径与原路径,如果新路径“短”,则修改这些节点在OPEN表中的原返回指针,使其沿新路返回(如图3-5所示)。(3)对已存在于CLOSED表的节点(如果有的话),做与(2)同样的处理,并且再将其移出CLOSED表,放入OPEN表重新扩展(为了重新计算代价)。(4)对其余子节点配上指向N的返回指针后放入OPEN表中某处,或对OPEN表进行重新排序,转步2。图3-5修改返回(fǎnhuí)指针示例说明：(1)这里的返回指针(zhǐzhēn)也就是父节点在CLOSED表中的编号。(2)步6中修改返回指针(zhǐzhēn)的原因是,因为这些节点又被第二次生成,所以它们返回初始节点的路径已有两条,但这两条路径的“长度”可能不同。那么,当新路短时自然要走新路。(3)这里对路径的长短是按路径上的节点数来衡量的,后面我们将会看到路径的长短也可以其“代价”(如距离、费用、时间等)衡量。若按其代价衡量,则在需修改返回指针(zhǐzhēn)的同时还要修改相应的代价值,或者不修改返回指针(zhǐzhēn)也要修改代价值(为了实现代价小者优先扩展)。线式搜索算法：·不回溯(huísù)的线式搜索·可回溯的线式搜索(sōusuǒ)步1把初始节点So放入CLOSED表中。步2令N＝So。步3若N是目标节点,则搜索(sōusuǒ)成功,结束。步4若N不可扩展,则移出CLOSED表的末端节点Ne,若Ne＝So,则搜索(sōusuǒ)失败,退出。否则,以CLOSED表新的末端节点Ne作为N,即令N＝Ne,转步4。步5扩展N,选取其一个未在CLOSED表用出现过的子节点N1放入CLOSED表中,令N＝N1,转步3。3.1.3穷举式搜索1.广度(guǎngdù)优先搜索广度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的指针依次(yīcì)放入OPEN表尾部,转步2。2.深度(shēndù)优先搜索深度优先搜索算法：步1把初始节点So放入OPEN表中。步2若OPEN表为空,则搜索失败(shībài),退出。步3取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的返回指针依次放入OPEN表的首部,转步2。3.有界深度优先搜索步1把So放入OPEN表中,置So的深度d(So)=0。步2若OPEN表为空,则失败,退出。步3取OPEN表中前面第一个节点N,放入CLOSED表中,并冠以顺序编号(biānhào)n。步4若目标节点Sg=N,则成功,结束。步5若N的深度d(N)=dm(深度限制值),或者若N无子节点,则转步2。步6扩展N,将其所有子节点Ni配上指向N的返回指针后依次放入OPEN表中前部,置d(Ni)=d(N)+1,转步2。3.1.4启发式搜索1.问题的提出2.启发性信息按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成(shēnɡchénɡ)节点的选择,即用于决定应生成(shēnɡchénɡ)哪些后续节点,以免盲目地生成(shēnɡchénɡ)过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。3.启发(qǐfā)函数启发(qǐfā)函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数,通常记为h(x)。4.启发(qǐfā)式搜索算法1)全局择优搜索2)局部择优搜索全局(quánjú)择优搜索算法：图3-8八数码问题的全局(quánjú)择优搜索例3.5用全局择优搜索法解八数码难题。初始棋局和目标棋局同例3。解设启发函数h(x)为节点x的格局与目标格局相比(xiānɡbǐ)数码不同的位置个数。以这个函数制导的搜索树如图3