N数码问题的启发式搜索算法

Wesley13
• 阅读 483
  • 一、启发式搜索:A算法

1)评价函数的一般形式 : f(n) = g(n) + h(n)

g(n):从S0到Sn的实际代价(搜索的横向因子)

h(n):从N到目标节点的估计代价,称为启发函数(搜索的纵向因子);

特点: 效率高, 无回溯,  

搜索算法

OPEN表 : 存放待扩展的节点.

CLOSED表 : 存放已被扩展过的节点.

2)评价函数  f(x) = g(x) + h(x)   

当f(x) = g(x)   时,为宽度优先搜索

当f(x) = 1/g(x)时,为深度优先搜索

当f(x) = h(x)   时,为全局优先搜索

比较f(x)大小,决定节点搜索顺序,即在OPEN表中的顺序

3)Step1:   把初始节点S0放入OPEN表中;

Step2:   若OPEN表为空,则搜索失败,退出.

Step3:   移出OPEN中第一个节点N放入CLOSED表中, 并标以顺序号n;

Step4:   若目标节点Sg=N, 则搜索成功,结束.

Step5:   若N不可扩展, 则转Step2;

Step6:   扩展N, 生成一组子节点, 对这组子节点作如下处理后, 放入  OPEN表, 按f值重新排序OPEN表, 转 Step2;

删除重复节点和修改返回指针处理.

  • 二、启发式搜索:A*算法

1)评价函数的一般形式:

f(n) = g(n) + h(n)  且  h(n) <= h*(n)

g(n),h(n):定义同A算法;

h*(n):从N到目标节点的最短路径; 称此时的A算法为A*算法.

2)程序关键点

节点的扩展:close表存放已经扩展后的状态,open表存放未扩展的状态。首先获取节点能扩展的方向,扩展后将父节点放入close表中,如果转移之后的节点,既不在close表也不再open表,表明该节点还未被扩展,则插入open表,如果在close表中表明之前已经扩展过该状态,为了避免无限扩展应将该状态从open表舍弃,如果在open表则比较这两个矩阵的f值(选取最优解),留小的在open表,之后对open表中的节点根据f值进行排序,pop出f值最小的节点进行扩展,依次进行该过程,直至该节点为目标状态。
解的路径的输出:通过目标状态节点向上回溯找其父节点,直至开始状态。

  • 三、python代码实现

    1 # -- coding: utf-8 -- 2 """ 3 Created on Sun Sep 16 14:31:40 2018 4 A*算法解决N数码问题 5 运行程序后如下是输入格式: 6 请输入矩阵的行数 7
    8 3 输入对应的N 9 请输入初始矩阵A
    10
    11 1 0 2 一行行输入,每行数字空格隔开,每行最后一个数字输入完成后直接回车开始输入第二行 12
    13 4 5 6 14
    15 3 7 8 16 请输入目标矩阵B 17
    18 1 2 3 19
    20 8 0 4 21
    22 7 6 5 23
    24 """ 25 import numpy as np 26 import copy 27 import time 28 from operator import itemgetter 29 30 goal = {} 31 32 def get_location(vec, num): #根据num元素获取num在矩阵中的位置 33 row_num = vec.shape[0] #numpy-shape函数获得矩阵的维数 34 line_num = vec.shape[1] 35
    36 for i in range(row_num): 37 for j in range(line_num): 38 if num == vec[i][j]: 39 return i, j 40 41 def get_actions(vec): #获取当前位置可以移动的下一个位置,返回移动列表 42 row_num = vec.shape[0] 43 line_num = vec.shape[1] 44
    45 (x, y) = get_location(vec, 0) #获取0元素的位置 46 action = [(0, 1), (0, -1), (1, 0), (-1, 0)] 47
    48 if x == 0: #如果0在边缘则依据位置情况,减少0的可移动位置 49 action.remove((-1, 0)) 50 if y == 0: 51 action.remove((0, -1)) 52 if x == row_num - 1: 53 action.remove((1, 0)) 54 if y == line_num - 1: 55 action.remove((0, 1)) 56
    57 return list(action) 58 59 def result(vec, action): #移动元素,进行矩阵转化 60 (x, y) = get_location(vec, 0) #获取0元素的位置 61 (a, b) = action #获取可移动位置 62
    63 n = vec[x+a][y+b] #位置移动,交换元素 64 s = copy.deepcopy(vec) 65 s[x+a][y+b] = 0 66 s[x][y] = n 67
    68 return s 69
    70 def get_ManhattanDis(vec1, vec2): #计算两个矩阵的曼哈顿距离,vec1为目标矩阵,vec2为当前矩阵 71 row_num = vec1.shape[0] 72 line_num = vec1.shape[1] 73 dis = 0 74
    75 for i in range(row_num): 76 for j in range(line_num): 77 if vec1[i][j] != vec2[i][j] and vec2[i][j] != 0: 78 k, m = get_location(vec1, vec2[i][j]) 79 d = abs(i - k) + abs(j - m) 80 dis += d 81
    82 return dis 83 84 def expand(p, actions, step): #actions为当前矩阵的可扩展状态列表,p为当前矩阵,step为已走的步数 85 children = [] #children用来保存当前状态的扩展节点 86 for action in actions: 87 child = {} 88 child['parent'] = p 89 child['vec'] = (result(p['vec'], action)) 90 child['dis'] = get_ManhattanDis(goal['vec'], child['vec']) 91 child['step'] = step + 1 #每扩展一次当前已走距离加1 92 child['dis'] = child['dis'] + child['step'] #更新该节点的f值 f=g+h(step+child[dis])
    93 child['action'] = get_actions(child['vec']) 94 children.append(child) 95
    96 return children 97 98 def node_sort(nodelist): #按照节点中字典的距离字段对列表进行排序,从大到小 99 return sorted(nodelist, key = itemgetter('dis'), reverse=True) 100 101 def get_input(num): 102 A = [] 103 for i in range(num): 104 temp = [] 105 p = [] 106 s = input() 107 temp = s.split(' ') 108 for t in temp: 109 t = int(t) 110 p.append(t) 111 A.append(p) 112
    113 return A
    114 115 def get_parent(node): 116 q = {} 117 q = node['parent']
    118 return q 119
    120 def test(): 121 openlist = [] #open表 122 close = [] #存储扩展的父节点 123
    124 print('请输入矩阵的行数') 125 num = int(input())
    126
    127 print("请输入初始矩阵A") 128 A = get_input(num) 129
    130 print("请输入目标矩阵B") 131 B = get_input(num) 132
    133 print("请输入结果文件名") 134 resultfile = input() 135
    136 goal['vec'] = np.array(B) #建立矩阵 137
    138 p = {} 139 p['vec'] = np.array(A) 140 p['dis'] = get_ManhattanDis(goal['vec'], p['vec']) 141 p['step'] = 0 142 p['action'] = get_actions(p['vec']) 143 p['parent'] = {} 144 145 if (p['vec'] == goal['vec']).all(): 146 return 147
    148 openlist.append(p) 149
    150 start_CPU = time.clock() #开始扩展时CPU开始计算 151
    152 while openlist: 153
    154 children = [] 155
    156 node = openlist.pop() #node为字典类型,pop出open表的最后一个元素 157 close.append(node) #将该元素放入close表 158
    159 if (node['vec'] == goal['vec']).all(): #比较当前矩阵和目标矩阵是否相同 160 end_CPU = time.clock() #CPU结束计算 161
    162 h = open(resultfile,'w',encoding='utf-8',) #将结果写入文件 并在控制台输出 163 h.write('搜索树规模:' + str(len(openlist)+len(close)) + '\n') 164 h.write('close:' + str(len(close)) + '\n') 165 h.write('openlist:' + str(len(openlist)) + '\n') 166 h.write('cpu运行时间:' + str(end_CPU - start_CPU) + '\n') 167 h.write('路径长:' + str(node['dis']) + '\n') 168
    169 h.write('解的路径:' + '\n') 170 i = 0 171 way = [] 172 while close: 173 way.append(node['vec']) #从最终状态开始依次向上回溯将其父节点存入way列表中 174 node = get_parent(node) 175 if(node['vec'] == p['vec']).all(): 176 way.append(node['vec']) 177 break 178 while way: 179 i += 1 180 h.write(str(i) + '\n') 181 h.write(str(way.pop()) + '\n') 182 h.close() 183 f = open(resultfile,'r',encoding='utf-8',) 184 print(f.read()) 185
    186 return 187
    188 children = expand(node, node['action'], node['step']) #如果不是目标矩阵,对当前节点进行扩展,取矩阵的可能转移情况 189
    190 for child in children: #如果转移之后的节点,既不在close表也不再open表则插入open表,如果在close表中则舍弃,如果在open表则比较这两个矩阵的f值,留小的在open表 191 f = False 192 flag = False 193 j = 0 194 for i in range(len(openlist)): 195 if (child['vec'] == openlist[i]['vec']).all(): 196 j = i 197 flag = True 198 break 199 for i in range(len(close)): 200 if(child['vec'] == close[i]).all(): 201 f = True 202 break 203 if f == False and flag == False : 204 openlist.append(child) 205
    206 elif flag == True: 207 if child['dis'] < openlist[j]['dis']: 208 del openlist[j] 209 openlist.append(child) 210
    211
    212 openlist = node_sort(openlist) #对open表进行从大到小排序 213
    214 test()

  • 四、程序运行结果如下图所示

 N数码问题的启发式搜索算法

图 1

N数码问题的启发式搜索算法

图 2

 N数码问题的启发式搜索算法

图 3

  • 五、总结

通过这次编程了解到了搜索具有探索性,要提高搜索效率(尽快地找到目标节点),或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索,已经提出了许多策略,它们大体可分为盲目搜索(bland search)和启发式搜索(heuristic search)两大类。其中盲目搜索是无向导搜索。启发式搜索是有向导搜索,即利用启发信息(函数)引导去寻找问题解。通过A*算法解决N数码问题实验过程中也遇到很多问题,比如节点扩展的方向问题等,通过这次实验不仅锻炼了自己python编程能力,也让自己对N数码求解最优路径问题有了更清晰的认识,希望自己能在老师和同学的帮助下,能不断进步,当然最重要的是自己得付出,只会幻想而不行动的人,永远也体会不到收获果实时的喜悦。加油!!

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Easter79 Easter79
2年前
swap空间的增减方法
(1)增大swap空间去激活swap交换区:swapoff v /dev/vg00/lvswap扩展交换lv:lvextend L 10G /dev/vg00/lvswap重新生成swap交换区:mkswap /dev/vg00/lvswap激活新生成的交换区:swapon v /dev/vg00/lvswap
Jacquelyn38 Jacquelyn38
2年前
这些JS工具函数够你用到2020年底了
前言活不多说,自己平时搜集的干货函数奉上。干货函数找出数字在数组中下一个相邻的元素let i  "";let rr  ;const name  (n, arr1)    let num  Number(n);    for (let i  0; i < arr1.length; i)         const elemen
Stella981 Stella981
2年前
HIVE 时间操作函数
日期函数UNIX时间戳转日期函数: from\_unixtime语法:   from\_unixtime(bigint unixtime\, string format\)返回值: string说明: 转化UNIX时间戳(从19700101 00:00:00 UTC到指定时间的秒数)到当前时区的时间格式举例:hive   selec
Wesley13 Wesley13
2年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Stella981 Stella981
2年前
LeetCode 5561. 获取生成数组中的最大值
文章目录1\.题目2\.解题1\.题目给你一个整数n。按下述规则生成一个长度为n1的数组nums:nums00nums11当2<2i<n时,nums2inumsi
Stella981 Stella981
2年前
AStar寻路1
A星算法是一种启发式的搜索方法,通过一个路径评估函数,来动态确定最佳路径。这点和广度搜索不同。基本思想是有2个列表,open和close,open列表里面的节点表示待搜索周围点的节点,close列表里面记录着不需要搜索的节点。启发式函数fgh;f表示该路径的代价,g表示起点到搜索的点的该条路径的实际值,h表示该搜索的点到终点的估计值。h的
Wesley13 Wesley13
2年前
3 OneToMany ManyToMany MappedBy Cascade
1双向1N关联对于1N关联,Hibernate推荐使用双向关联,而且不要让1的一方控制关联关系,而使用多的一方控制关联关系。a.一的一方 表示班级@Entity@Table(name"team_1")publicclassTeam{@Id@Gen
Stella981 Stella981
2年前
Bzoj4899 记忆的轮廓
B.记忆的轮廓题目描述通往贤者之塔的路上,有许多的危机。我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1n的简单路径上,编号依次递增,在\1,n\中,一共有n个节点。我们把编号在\1,n\的叫做正确节点,\n1,m\的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称
菜园前端 菜园前端
10个月前
什么是顺序搜索?
原文链接:什么是顺序搜索?顺序搜索是一种比较低效的搜索算法,但是实现起来相对简单。主要步骤如下:1.遍历数组2.找到跟目标值相等的元素,就返回它的下标3.遍历结束后,如果没有搜索到目标值,则返回1基础案例时间复杂度:O(n)空间复杂度:O(1)javasc