8.4 经典算法

关注
发布于: 2020 年 11 月 16 日
1.常用算法      穷举算法
      递归算法
      贪心算法
      动态规划
2.递归算法（快速排序算法）     def  quicksort(array) :
             if len(array)<2 :
                     return array; <----------------基线条件：为空或者只包含一个元素的数组是“有序”的
             else:
                  pivot=array[0];<----------------递归条件：设置基准值
                  less=[i for i in array[l:]  if  i<=pivot ]<--------------------------有所有小于基准值的元素组成的子数组
                  greater=[ i for i in array[l:] if i>pivot]<-------------------------有所有大于基准值的元素组成的子数组
                  return quicksort(less)+[pivot]+quicksort(greater);
     print quicksort(10,5,3,2);
     解析： 时间复杂度：   随机： n*log(n)     有序：n^2
     特点：递归就是自己调用自己。如果没有退出条件，自己一直调用自己，最终堆栈溢出----StackOverFlow
               结合线程栈分析：每调用一次，一个栈帧入栈。一直自己调用自己，不断有栈帧继续入栈，直至超过线程栈的最大深度，
                                         线程栈内存被耗尽----栈溢出----stackoverflow。
               设置退出条件-->递归退出。
     快排特点：以基准值为分界点，数组分为三部分:[左侧小| 基准值|右侧大].
﻿
3.贪心算法      贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。不考虑整体最优解，算法考虑的是某种意义上的局部最优解。
﻿
      背包问题：4磅背包，价值最大化。（音响/3000元/4磅）（笔记本电脑/2000元/3磅）（吉他/1500元/1磅）
                       1.4磅背包==4磅音响====>3000元-------------------------------------局部最优解
                       2.4磅背包==3磅笔记本电脑+1磅吉他====>3500元--------------------整体最优解
﻿
4.改进贪心算法----迪杰斯特拉算法（最快路径）
    1.找出“最便宜”的节点，即可在最短时间内到达的节点。
     2.更新该节点的邻居的开销，检查是否有前往他们的更短路径，如果有，就更新其开销。
     3.重复这个过程，直到对图中的所有节点都这样做了。
     4.计算最终路径。
  
迪杰斯特拉算法的核心：找到起点到每个节点的最快路径。
解析： 
  1.找出“最便宜”的节点，即可在最短时间内到达的节点。==>起点到达A，B，终点的最短时间。
    起点到达其他节点（局部最优解
﻿
2.更新该节点的邻居的开销，检查是否有前往他们的更短路径，如果有，就更新其开销。==>起点的邻居节点是A，B。首先检查起点经过B到达其他节点的最短路径（局部最优解）。
    ==>起点经过B点到达A点的时间=（2+3=5分钟<6分钟），更新起点到达A点的最短时间=5分钟
    ==>起点经过B点到达B点的时间=2分钟，保持当前最短时间=2分钟
    ==>起点经过B点到达终点需要2+5=7分钟<无穷大，更新起点到终点的耗时=7分钟
﻿
3.更新该节点的邻居的开销，检查是否有前往他们的更短路径，如果有，就更新其开销。==>起点的邻居节点是A，B。再检查起点经过A到达其他节点的最短路径（局部最优解）。
    ==>起点经过A点到达A点=6分钟<5分钟，保持当前记录=5分钟
    ==>起点经过A点到达B点=无穷大>2分钟，保持当前记录=2分钟
    ==>起点已经A点到达终点时间：(6+1=7分钟)>（2+3+1=6分钟）
﻿
4.结算结果展示：起点到达终点的最短时间为6分钟。反查最短路径：终点<----A<-----B<----起点
﻿
﻿
5.动态规划算法解决背包问题      通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干小问题，从小问题的最优解，寻找大问题的最优解----全局最优解。
     （吉他/1500元/1磅），（音响/3000元/4磅），（笔记本电脑/2000元/3磅）
1.横向找最优解=1磅最优解（1500）+3磅最优解（2000）=4磅最优解（3500），
2.纵向找最优解=4磅最优解（3000）
3.3000<3500
====>3500为最优解===>1磅最优解（1500）+3磅最优解（2000）
﻿
6.遗传算法解决背包问题遗传算法（Genetic Algorithm,GA）模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
﻿
遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择，交叉变异构成了遗传算法的遗传操作；
参数编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数设定五个要素组成了遗传算法的核心内容。
﻿
80公斤背包装那些物品价值最大？
﻿
7.基因编码与染色体
基因组合：染色体
选择初始染色体：随机产生（也可以人为或者算法选择）                                                                                                                                                                      
100100：物品1，物品4存在
101010：物品1，物品3，物品5存在
010101：物品2，物品4，物品6存在
101011：物品1，物品3，物品5，物品6存在
8.适应函数与控制参数选择适应度函数，这里为商品总价值
100100=15+45=60
101010=15+35+55=105
010101=25+45+70=140
101011=15+35+55+70=175
选择控制参数，这里为总重量
100100=10+25=35
101010=10+20+30=60
010101=15+25+35=75
101011=10+20+30+35=95
染色体101011超重，淘汰。
9.选择算法在剩下的染色体中选择可以被遗传下去的染色体以及繁殖次数。
100100=15+45=60（适应度函数为60）
101010=15+35+55=105（适应度函数为105）
010101=25+45+70=140（适应度函数为140）
选择算法：找到更有价值的染色体。低适应度函数可能含有高价值的基因片段。
轮盘赌选择（Routette Wheel Selection）：是一种回放式随机采样方法。每个染色体进入下一代的概率等于它的适应度值与整体适应度值和的比例。
随机竞争选择（Stochastic Tournament）:每次按照轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。
均匀排序：对群体中的所有个体按其适应度大小排序，基于这个排序来分配各个个体被选中的概率。
10.交叉遗传选择结果：101010和010101，各繁殖两次。
生产下一代：染色体交叉遗传
﻿
使用适应度函数和选择控制参数，筛选基因。
循环迭代，如果连续几代都没有出现更强的染色体（价值总和更大），那么算法收敛，当前最大价值的染色体为最终解。
﻿
有时候会在遗传过程中基因突变，得到基因突变染色体。
﻿
11.遗传算法得到的不是最优解遗传算法过程：
﻿
﻿
即使不是最优解，也是一个比较好的结果，现实中可接受的。
场景：试卷生成。难度系数，试卷分数，生成难度适中，总分100分的试卷。
﻿