大数据与智能算法（一基础技术）SMU在线学习笔记

【课程来源】感谢B站Up主leonding1018的分享&＃xff0c;老师的课程内容非常精彩。
本文是观看网络视频课程后的笔记&＃xff0c;如涉及版权问题&＃xff0c;请及时留言或私信与我联系。

1.旅行商问题&＃xff08;TSP问题&＃xff09;

TSP问题是一个NP hard问题&＃xff0c;在一个多项式时间内不能找到一个最优解。

单个车辆遍历路径&＃xff08;TSP问题&＃xff09;可以扩展为&＃xff1a;多车辆遍历路径&＃xff08;VRP&＃xff09;&＃xff0c;车辆实时路径规划&＃xff0c;订单分配给不同车辆&＃xff08;调度优化&＃xff09;&＃xff0c;零部件排产等。

2.启发式搜索算法

2.1.全局搜索算法

2.1.1.贪婪最佳优先搜索

2.1.2.A*&＃xff08;A Star&＃xff09;搜索

举了即时战略游戏中目标对象选择路径找过障碍物到达目的地的例子&＃xff0c;目标是让英雄从地图左上角A点运动到右下角B点。如图所示&＃xff0c;黑色部分为障碍物&＃xff0c;“黄橙红”颜色标记了每一个坐标被遍历访问的此处。上方为枚举法对地图各坐标的访问频次&＃xff0c;下方为A Star搜索方法对地图各坐标的访问频次。可以看出A Star方法只访问了较少的坐标&＃xff0c;提高了搜索效率。

(1)从当前点(x&＃61;1,y&＃61;2)开始遍历相邻点&＃xff08;算出g&＃61;当前点到新点单步距离&＃xff0c;h&＃61;新点到终点不考虑障碍物的剩余距离&＃xff0c;f&＃61;g&＃43;h&＃xff09;&＃xff1b;

(2)选取f最小的点作为新的当前点(x&＃61;2,y&＃61;3)&＃xff1b;

(3)重复步骤1&＃xff1b;
(x,y)从(2,3)到(3,3)

(x,y)从(3,3)到(4,3)

(4)注意所有已探索未步入的点&＃xff0c;都是候选点&＃xff0c;这是便于选错路的回头纠正&＃xff1b;
(x,y)从(4,3)回头到(1,3)&＃xff0c;再回头到(2,2)

(5)当重新选取了当前节点&＃xff08;即回头&＃xff09;后&＃xff0c;相关已探索节点的g/h/f值也应更新。
注意当前点改为(2,2)后&＃xff0c;点(3,2)、(4,2)的g/h/f值都进行了更新。

(6)注意每个新点都记录着其对应的父节点&＃xff0c;便于最后一步回溯&＃xff1b;
留意之前每一幅图上的箭头&＃xff0c;当前点变化后&＃xff0c;箭头也发生了变化。

(7)当前点移动到终点后&＃xff0c;从终点开始&＃xff0c;根据父节点可反推出最优路径。
上图中绿色标记的路径。

2.1.3.限制存储的启发式搜索

2.1.4.启发函数h(n)的设计

2.2.局部搜索和群算法

2.2.1.贪婪局部搜索

2.2.2.模拟退火搜索

2.2.3.禁忌搜索

2.2.4.局部剪枝搜索

2.2.5.遗传算法&＃xff08;基因算法&＃xff09;

(1)先随机生成一定数量&＃xff08;例如1000条&＃xff09;的解&＃xff1b;
(2)然后按一定比例&＃xff08;例如10%&＃xff09;选出其中较好的100个保留&＃xff0c;其余的900条再变异&＃xff1b;
(3)在第上一步新生成的1000条中选100个保留&＃xff0c;其余的变异&＃xff1b;
(4)重复步骤3若干次&＃xff1b;
(5)选1000条中最好的一个&＃xff0c;作为最优解。

2.3.对抗搜索

2.3.1.极小极大值算法

2.3.2.α-β剪枝搜索

3.混合机器学习算法的优化求解

应留意图片中一些城建概念的关系&＃xff0c;包括&＃xff1a;数据库、指示发现、数据挖掘、统计、图形识别、神经计算、人工智能、机器学习、深度学习。比如&＃xff0c;机器学习的范围大于深度学习&＃xff0c;人工智能的范围大于机器学习。

《终极算法》&＃xff08;推荐书&＃xff09;中将算法分为5大类&＃xff1a;
(1)符号主义&＃xff1a;通过规则和决策树进行推理&＃xff1b;
(2)贝叶斯方法&＃xff1a;通过统计学中的贝叶斯&＃xff08;先验后验&＃xff09;概率&＃xff1b;
(3)联接主义&＃xff1a;模拟人脑&＃xff0c;创建节点和连接网络进行非线性关联&＃xff0c;代表性有神经网络&＃xff1b;
(4)进化方法&＃xff1a;模拟生物进化&＃xff0c;迭代创建新的节点&＃xff0c;代表性有遗传算法&＃xff1b;
(5)类比学派&＃xff1a;利用样本特征相似性&＃xff0c;代表性有KNN聚类分析&＃xff08;商品推荐&＃xff09;和支持向量机。

实例&＃xff1a;在滴滴打车应用中。早期使用A Star方法进行路径规划和时间估计&＃xff1b;在后期取得了更多大数据后&＃xff0c;利用这些数据采用RNN&＃xff08;循环神经网络&＃xff09;算法进行路径规划和时间估计。能够比初期的A-Star方法考虑到了更多的复杂因素&＃xff08;例如车辆类型、拥堵、修路、时间、司机驾龄等&＃xff09;&＃xff0c;所以预估时间更准确。

4.Hadoop生态