⑤扩展节点，生成一组子节点。把其中不是节点n先辈的 那些子节点记作集合M,并把这些节点作为节点的子节 点加入G中。 EXPAND(n)-M(mi),G:=ADD (mi,G) ⑥针对M中子节点的不同情况，分别进行如下处理 ·对于那些未曾在G中出现过的M成员设置一个指向父 节点(n)的指针，并把它放入OPEN表 ·对于那些先前已在G中出现过的M成员，确定是否要 修改指向父节点的指针 ·对于那些先前已在G中出现，并且已经扩展了的M成 员，确定是否需要修改其后继结点指向父节点的指 针 ⑦按某种搜索策略对OPEN表中的节点进行排序 ⑧转第②步 GO LOOP
扩展节点n,生成一组子节点。把其中不是节点n先辈的 那些子节点记作集合M,并把这些节点作为节点n的子节 点加入G中。 EXPAND(n)M(mi),G:=ADD(mi,G) 针对M中子节点的不同情况，分别进行如下处理 • 对于那些未曾在G中出现过的M成员设置一个指向父 节点（n)的指针，并把它放入OPEN表 • 对于那些先前已在G中出现过的M成员，确定是否要 修改指向父节点的指针 • 对于那些先前已在G中出现，并且已经扩展了的M成 员，确定是否需要修改其后继结点指向父节点的指 针 按某种搜索策略对OPEN表中的节点进行排序 转第步 GO LOOP
● 扩展节点1，生成 ●代表已扩展节点，位于CL0SE表上 单一后继节点2， O代表未扩展节点，位于OPEN表上 2已有父节点3， →有向边旁的箭头是指向父节点的 从S0-2的代价为4， 指针，每边代价为1 从S02的代价为2， 后者代价小，修 0 改节点2指向父节 点的指针 。扩展节点4，节点 4是节点6的后继 节点，S0-4的代 价为4，S0-4代价 为3，修改4的父 节点指针
• 扩展节点1，生成 单一后继节点2， 2已有父节点3， 从S0-2的代价为4， 从S0-2的代价为2， 后者代价小，修 改节点2指向父节 点的指针 • 扩展节点4，节点 4是节点6的后继 节点，S0-4的代 价为4，S0-4代价 为3，修改4的父 节点指针 代表已扩展节点，位于CLOSE表上 代表未扩展节点，位于OPEN表上 →有向边旁的箭头是指向父节点的 指针，每边代价为1 S0 1 2 3 5 4 6
2广度优先搜索—宽度优先搜索 (1)基本思想：从S0开始，逐层地对节点进行扩展，考 寨它是否为目标节点，在第层的节点没有全部扩展 并考察之前，不对第n+1层的节点进行扩展。open表 中的节点总是按进入的先后顺序排列，先进入的节 点排在前面，后进入的排在后面。 (2)搜索过程 ①OPEN:=S0 LOOP:IF (OPEN)=()THEN EXIT(FAIL) 3n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE) IF GOAL(n)THEN EXIT (SUCCESS) IF EXPAND(n)=()GO LOOP ⑥EXPAND(n)-→M(m),ADD(m1,OPEN),m↑→n; GO LOOP
2 广度优先搜索—宽度优先搜索 (1)基本思想：从S0开始，逐层地对节点进行扩展，考 察它是否为目标节点，在第n层的节点没有全部扩展 并考察之前，不对第n+1层的节点进行扩展。open表 中的节点总是按进入的先后顺序排列，先进入的节 点排在前面，后进入的排在后面。 (2)搜索过程 OPEN:=S0 LOOP:IF (OPEN)=( ) THEN EXIT(FAIL) n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE) IF GOAL(n) THEN EXIT (SUCCESS) IF EXPAND(n)=( ) GO LOOP EXPAND(n)→M(mi),ADD(mi,OPEN ),mi→n; GO LOOP
例重排九宫问题 2 83 (1)初始状态S0 76 1 2 3 目标状态Sg 8 65 (2)算符有：空格左移、上移、右移、下移 (③)优点：只要有解，用广度优先搜索总可以得 到，而且得到的是路径最短的解 (4)缺点：搜索效率低，特别是目标节点距离初 始节点较远时
例 重排九宫问题 (1)初始状态S0 目标状态Sg (2)算符有：空格左移、上移、右移、下移 (3)优点：只要有解，用广度优先搜索总可以得 到，而且得到的是路径最短的解 (4)缺点：搜索效率低，特别是目标节点距离初 始节点较远时。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5
脚脚翻 翻 脚园 翻 鄜 脚 膻 765 765
2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 3 1 4 5 7 6 2 8 1 4 3 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 s0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26