八数码（五种搜索策略）

各种搜索策略的搜索法： 1.广度优先搜索 步1 把初始结点S0放入OPEN表中 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步2 2.深度优先搜索 步1 把初始结点S0放入OPEN表中 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的首部，转步2 3.有界深度优先搜索 步1 把初始结点S0放入OPEN表中，置S0的深度d(S0)=0 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N的深度d(N)==dm(深度限制值)，则转步2 步6 若N无子结点，则转步2 步7 扩展结点N，将其所有子结点Ni配上指向N的放回指针，并置d(Ni)=d(N)+1，再依次放入OPEN表的首部，转步2 4.最好优先搜索（应该就是指全局择优搜索） 步1 把初始结点S0放入OPEN表中 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，并计算f(Ni),依次放入OPEN表中，然后对OPEN表重新排序 （小的在前），转步2 5.局部择优搜索 步1 把初始结点S0放入OPEN表中 步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，并计算f(Ni)。对生成的结点按f(Ni)排序(小的在前)，然 后将排序后的结点依次放入OPEN表的首部（f(Ni)小的先放入），转步2 启发式搜索法使用的估计函数 在启发式搜索中，我采用的估计函数是f(n)=d(n)+h(n)，d(n)是结点的深度，h(n)由以下计算得到： h(n)=p(n)+3s(n) 其中p(n)的定义是，它是n格局中每个将牌离家的最短距离之和。 s(n)是这样来计算的：沿着周围那些非中心方格上依顺时针方向检查n格局中的每一个将牌，如果其后紧跟着的将牌正好是目标格局中该将牌的后继者，则该将牌得0分，否则得2分；在正中方格上有将牌得1分，否则得0分。所有将牌得分之和即为s(n)。