一道题理解穷举/贪心/爬山/遗传/退火/蚁群算法
一道题理解穷举/贪心/爬山/遗传/退火/蚁群算法，配代码
视频地址：B站https://www.bilibili.com/video/BV1Yk4y1q7b9/
问题描述：
给出矩阵，其中紫色为起点（0,0）和终点（5,5）
绿色（0）为可行走路径
红色（1）为墙壁，不能通过
黄色（2）为金币点，必须通过
求一条从起点到终点最小路径，且经过所有金币点
1、穷举法
就是回溯法，将每一步的选择（上下左右）作为choices来判断，符合要求（不超过矩阵大小限制且值不为1）则下一步
到达终点且金币数对就把解加入res并回溯
代码
1 import random 2 import math 3 nums=[[0,0,0,0,0,0,0], 4 [0,0,0,1,0,1,0], 5 [0,1,0,0,0,2,0], 6 [0,0,2,0,1,0,0], 7 [0,1,1,0,0,0,0], 8 [0,2,0,0,0,0,0], 9 [0,0,0,0,0,0,0]] 10 11 def path_que(nums,x,y,tx,ty,coin_is): 12 res=[] 13 choices=[[-1,0],[1,0],[0,-1],[0,1]] 14 n=len(nums) 15 def trace(path,choices,x,y,tx,ty,target): 16 if len(res)==500:return 17 if x==tx and y==ty and (target==3 or coin_is==False): 18 res.append(list(path)) 19 return 20 21 for choice in choices: 22 if x+choice[0]>=0 and x+choice[0]<n and y+choice[1]>=0 and y+choice[1]<n: 23 if nums[x+choice[0]][y+choice[1]]!=1: 24 if [x+choice[0],y+choice[1]] in path:continue 25 if nums[x+choice[0]][y+choice[1]]==2 and coin_is: 26 target+=1 27 path.append([x+choice[0],y+choice[1]]) 28 trace(path,choices,x+choice[0],y+choice[1],tx,ty,target) 29 path.pop() 30 if nums[x+choice[0]][y+choice[1]]==2 and coin_is: 31 target-=1 32 trace([[x,y]],choices,x,y,tx,ty,0) 33 return res 34 35 # result=path_que(nums,0,0,5,5,True) 36 # print(len(result)) 37 # mid=[len(i) for i in result] 38 # print(min(mid)) 39 # for item in result: 40 # if len(item)==min(mid): 41 # print(item) 42 # break
2、贪心法
对穷举法的改进
只需少数几次较小规模的路径搜索就能得到局部最优解
将3个金币点分解为a，b，c
计算起点s到a，b，c的最小距离
选最小的例如a，然后计算a到b，c的距离
选最小的例如b，然后计算b到c的距离，最后计算c到终点d的距离
这就是贪心法得出的最小路径，只需3+2+1+1次路径搜索，即n(n+1)/2+1次
代码同穷举法
3、爬山法
对贪心法的改进
只需比贪心法多、比穷举法少的几次较小规模的路径搜索就能得到局部最优解
将n=3个金币点分解为a，b，c
计算
s-a-b-c-d
s-a-c-b-d
s-b-a-c-d
s-b-c-a-d
s-c-a-b-d
s-c-b-a-d
的距离选择最小的
可以看出需要n!*(n+2-1)=(n+1)!=3*2*1*4=24
这就是贪心法得出的最小路径，只需24次路径搜索，即(n+1)!次
代码同穷举法
4、遗传法
遗传法的最重要两个概念：交叉（交换信息）和变异
遗传法把一个问题的解看做一个物种
物种之间会进行交换信息，这样产生的后代有可能性质会优于父代
同时物种会以极小的概率变异，即某段信息完全改变
对于数字例如1和2，他们可以以0001和0010的形式交换信息
在本问题中路径是一串，可以很轻松交换信息
但是需要注意的是
路径中的每个点是要连在一起的
因此选取两个点时要选取两段路径中的公共点
变异就是两个点之间的路径不用父代的而是用路径规划重新计算一个
这就是遗传法
代码如下
1 def life_que(results): 2 n=1000 3 rp1=0.5#交叉概率 4 rp2=0.05#变异概率 5 for i in range(n): 6 if random.random()>rp1:continue 7 random.shuffle(results) 8 a=results[0] 9 b=results[1] 10 mid=[] 11 for item in a: 12 if item in b:mid.append(item) 13 if len(mid)<2:continue 14 #print(a,b) 15 random.shuffle(mid) 16 k1=mid[0] 17 k2=mid[1] 18 #print(k1,k2) 19 n11=a.index(k1) 20 n12=a.index(k2) 21 n21=b.index(k1) 22 n22=b.index(k2) 23 # print(n11,n12) 24 # print(n21,n22) 25 if n11>n12: 26 n11,n12=n12,n11 27 if n21>n22: 28 n21,n22=n22,n21 29 if random.random()<rp2: 30 mid_content=path_que(nums,a[n11][0],a[n11][1],a[n12][0],a[n12][1],False) 31 mid_que=[len(t) for t in mid_content] 32 # print(n12-n11+1) 33 # print(min(mid_que)) 34 for item in mid_content: 35 if len(item)==min(mid_que): 36 bianyi=item 37 break 38 mida=a[:n11] 39 mida.extend(b[n21:n22]) 40 mida.extend(a[n12:]) 41 midb=b[:n21] 42 midb.extend(a[n11:n12]) 43 midb.extend(a[n22:]) 44 #print(mida,midb) 45 if len(a) < len(results[0]):results[0]=mida 46 if len(b) < len(results[1]):results[1]=midb 47 return results 48 49 # content=path_que(nums,0,0,5,5,True) 50 # print(len(content[0])) 51 # mid=[len(t) for t in content] 52 # print(min(mid)) 53 # content=life_que(content) 54 # mid=[len(t) for t in content] 55 # print(min(mid))
5、退火法
退火法也是找一个局部最优解的方法
退火法将一个问题设置一个迭代次数L，初始温度t和阈值T
每一次迭代会基于原解产生一个新解，这个过程会让温度t降温
当到达最大迭代次数L或者温度降到T时就会停止
此时的解作为结果
每一次迭代得到的新解如果长度小于原解就替换原解
或者长度大于原解，这时以exp(-t/T)的概率接受替换原解，这就是Metropolis准则
我这里设置如果替代原解就降温100度
否则降温10度
这样可以让替换多时尽可能快速结束
万一已经降到很小了，这是又因为准则替换个大的就亏了
代码如下
1 def hot_que(content): 2 L=1000 3 t=1000 4 T=100 5 for i in range(L): 6 mid=list(content) 7 random.shuffle(mid) 8 k1=mid[0] 9 k2=mid[1] 10 n1=content.index(k1) 11 n2=content.index(k2) 12 if n1>n2: 13 k1,k2=k2,k1 14 n1,n2=n2,n1 15 midcon=path_que(nums,k1[0],k1[1],k2[0],k2[1],False) 16 midcon=midcon[0] 17 res=content[:n1] 18 res.extend(midcon) 19 res.extend(content[n2:]) 20 if len(res)<len(content) or random.random()<math.exp(-t/T): 21 content=res 22 t-=90 23 t-=10 24 if t<=T:break 25 return content 26 27 #print(len(hot_que(content[0])))
6、蚁群法
蚁群法的核心就是信息素这个概念
在本问题中，每一个蚂蚁爬过的路径（需要到达终点）都会为信息素矩阵加1
下一只蚂蚁就可以根据周围信息素矩阵的值的大小来判断到底要走哪个方向
蚁群法通常用分布式计算，即多线程多进程，这样更新迭代信息素矩阵的速度快
本题采用改化版
例如蚁群法1：生成100个路径，这100个路径每个点都在信息素矩阵中加1，下一只蚂蚁就按着这个信息素矩阵判断
问题是我们给出的默认选择路径总有一个顺序，例如我这里用的默认是上下左右方向依次寻路
这样就会导致去某个方向的蚂蚁太多造成误判
这时蚁群法2：生成500个路径，100次随机抽取5个路径选择最小的路径，将该路径每个点加入信息素矩阵
这样的好处就是一定程度上避免了因默认寻路方向导致的误判
结果显示是很优化的
代码如下
1 content=path_que(nums,0,0,5,5,True) 2 def ant_que(content): 3 info=[[0 for i in range(len(nums))]for j in range(len(nums))] 4 #print(info) 5 for item in content: 6 for i in item: 7 info[i[0]][i[1]]+=1 8 return info 9 10 def ant_que_2(content): 11 info=[[0 for i in range(len(nums))]for j in range(len(nums))] 12 for i in range(len(content)//5): 13 random.shuffle(content) 14 mid=[len(t) for t in content[:5]] 15 k1=mid.index(min(mid)) 16 for i in content[k1]: 17 info[i[0]][i[1]]+=1 18 return info 19 for item in ant_que_2(content): 20 print(item)
END