第4章图搜索技术--41状态图搜索 (3)、如果有已存在于 CLOSED表中的节点,则作与(2)同样的 处理,并且再将其移出 CLOSED表,放入OPEN表重新扩展 (4)、对其余子节点,配上指向父节点n的指针后放入OPEN表, 对OPEN表按某种搜索策略排序后转步2。 线式搜索算法 不可回溯的线式搜索 步1把初始节点S0放入 CLOSED表中 步2令N 步3若N是目标节点,则搜索成功,结束; 步4若N不可扩展,则搜索失败,退出。 步5扩展N,选取一个未在 CLOSED表中出现的子节点N1放入 CLOSED表中,令N=N1,转步3
第4章 图搜索技术----4.1 状态图搜索 （3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的 处理，并且再将其移出CLOSED表，放入OPEN表重新扩展； （4）、对其余子节点，配上指向父节点n的指针后放入OPEN表， 对OPEN表按某种搜索策略排序后转步2。 线式搜索算法 不可回溯的线式搜索： 步1 把初始节点S0放入CLOSED表中； 步2 令N= S0 ； 步3 若N是目标节点，则搜索成功，结束; 步4 若N不可扩展，则搜索失败，退出。 步5 扩展N，选取一个未在CLOSED表中出现的子节点N1放入 CLOSED表中，令N=N1，转步3
第4章图搜索技术--41状态图搜索 可回溯的线式搜索: 步1把初始节点S。放入 CLOSED表中; 步2令N=S0 步3若N是目标节点,则搜索成功,结束; 步4若N不可扩展,则移出 CLOSED表的末端节点N, 若Na=S0,则搜索失败,退出。否则,以 CLOSED表 新的末端节点N作为N即令N=N,转步4 步5扩展N,选取一个未在 CLOSED表中出现的子节点 N1放入 CLOSED表中,令N=N1,转步3
第4章 图搜索技术----4.1 状态图搜索 可回溯的线式搜索： 步1 把初始节点S0放入CLOSED表中； 步2 令N= S0 ； 步3 若N是目标节点，则搜索成功，结束; 步4 若N不可扩展，则移出CLOSED表的末端节点Ne， 若Ne =S0 ，则搜索失败，退出。否则，以CLOSED表 新的末端节点Ne作为N,即令N=Ne，转步4 步5 扩展N，选取一个未在CLOSED表中出现的子节点 N1放入CLOSED表中，令N=N1，转步3
第4章图搜索技术--41状态图搜索 4.13穷举式搜索 1、广度优先搜索 又称宽度优先思索,优先在同一级节点中考察,只有当同一级节点扩展完 以后,才扩展下一级节点。 例、解八数码问题。初始状态:(2,8,3,4,5,6,7,1),目标状态 (1,2,3,4,5,6,7,8) 广度优先搜索算法 步1把初始节点S0放入OPEN表中; 步2若OPEN表为空,则搜索失败,退出:表中 一步3取OPEN表中前面第一个节点N放入 CLOSE 步4若目标节点Sg=N,则搜索成功,结束 步5若N不可扩展,则转步2。 步6扩展N,将其所有子节点配上指向N的指针依次放入OPEN表 的尾部,转步2
第4章 图搜索技术----4.1 状态图搜索 4.1.3 穷举式搜索 1、广度优先搜索 又称宽度优先思索，优先在同一级节点中考察，只有当同一级节点扩展完 以后，才扩展下一级节点。 例、解八数码问题。初始状态： （2，8，3，4，5，6，7，1），目标状态： （1，2，3，4，5，6，7，8） 广度优先搜索算法： 步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出； 步3 取OPEN表中前面第一个节点N放入CLOSED表中； 步4 若目标节点Sg =N，则搜索成功，结束; 步5 若N不可扩展，则转步2。 步6 扩展N，将其所有子节点配上指向N的指针依次放入OPEN表 的尾部，转步2
第4章图搜索技术--41状态图搜索 广度优先搜索的特点:完备、解是最优解、效率 低 2、深度优先搜索 在搜索的每一层,始终只扩展一个节点,不断地 向纵深前进,直到不能再前进时,才从当前节点 返回到上一级节点,延另一节点又继续前进 例、八数码问题的深度优先搜索
第4章 图搜索技术----4.1 状态图搜索 广度优先搜索的特点：完备、解是最优解、效率 低。 2、深度优先搜索 在搜索的每一层，始终只扩展一个节点，不断地 向纵深前进，直到不能再前进时，才从当前节点 返回到上一级节点，延另一节点又继续前进。 例、八数码问题的深度优先搜索
第4章图搜索技术--41状态图搜索 深度优先搜索算法 步1把初始节点S放入OPEN表中; 步2若OPEN表为空,则搜索失败,退出 步3取OPEN表中前面第一个节点N放入 CLOSED表中 步4若目标节点S。=N,则搜索成功,结束; 步5若N不可扩展,则转步2 步6扩展N,将其所有子节点配上指向N的返回指针依次放 入OPEN表的首部,转步2 深度优先搜索策略的特点:不完备、找到的解不一定是最优 解
第4章 图搜索技术----4.1 状态图搜索 深度优先搜索算法： 步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出； 步3 取OPEN表中前面第一个节点N放入CLOSED表中； 步4 若目标节点Sg =N，则搜索成功，结束; 步5 若N不可扩展，则转步2。 步6 扩展N，将其所有子节点配上指向N的返回指针依次放 入OPEN表的首部，转步2。 深度优先搜索策略的特点：不完备、找到的解不一定是最优 解