400-050-6600
当前位置:首页 - Q&A问答

Q&AQ&A问答

数据分析师最喜欢的11种动画算法?

来源:CPDA数据分析师网 / 作者:数据君 / 时间:2020-11-19

1、贪婪算法
贪婪算法是试图在每次迭代中增加最低成本的算法的总称,即使它们导致次优组合,在此示例中,所有可能的边按距离(最短到最长)排序,然后添加最短边,该最短边既不会创建具有多于2条边的顶点,也不会创建少于城市总数的循环,重复此过程,直到我们拥有一个包含所有城市的周期,尽管这里所有的启发式方法都不能保证最优解,但是众所周知,贪婪算法对于TSP而言并不是特别理想。

2、最近的邻居
最近的邻居启发式算法是另一种贪婪算法,或者有些人称之为天真算法,它从一个城市开始,并与最近的未访问城市连接,重复直到访问了每个城市,然后返回起始城市,首先应从凝视点到最近的点,然后再到最靠近该点的点,依此类推,这样的规则通常不会产生最短的路线,最近邻算法的时间复杂度为O(n^2)。所需的计算数量增长不会快于n ^ 2。

3、最近插入
插入算法会随着游览的发展在现有点之间添加新点,最近插入的一种实现方式是从两个城市开始,然后它反复查找尚未在游览中的城市,该城市与该游览中的任何城市最接近,并将其放置在两个城市之间,这将导致最终的游览尽可能短,当不再有剩余插入时,它将停止,最近的插入算法是 O(n^2)。

4、最便宜的插入
像最近插入一样,最便宜插入也从两个城市开始,然后,它会发现游览中尚未存在的城市,将其放置在子游览中两个相连的城市之间时,可能会导致游览最短,它将在两个相连的城市之间插入城市,然后重复进行直到没有剩余的插入,最便宜的插入算法是 O(n^2 log2(n))

5、随机插入
随机插入也从两个城市开始。然后,它会随机选择一个尚未在游览中的城市,并将其插入游览中的两个城市之间。冲洗,清洗,重复,时间复杂度: O(n^2)。

6、最远的插入
与其他插入不同,“最远插入”从一个城市开始,并将其与离它最远的城市连接起来,然后它反复查找游览中距离该游览中任何城市最远的城市,并将其放置在两个城市之间,这将导致最终的游览尽可能短,时间复杂度: O(n^2)。

7、Christofides算法
Christofides算法是一种具有3/2近似保证的启发式算法。在最坏的情况下,行程不超过最佳行程的3/2,由于其速度和3/2近似保证,Christofides算法通常用于构造上限,作为初始巡回路线(将使用巡回改进启发式算法进一步优化该初始巡回路线),或者用作帮助限制分支和分支的搜索空间的上限。寻找最佳路线时所用的切割技术,为了使其正常工作,它要求城市之间的距离对称并且服从三角形不等式,这就是在典型的x,y坐标平面(度量空间)中可以找到的,它于1976年发布,继续保持着公制空间最佳逼近率的记录,该算法复杂[2]。它的时间复杂度是O(n^4)。

8、2-Opt
如果我们不能通过切换k个边来改善行程,则称为k-最佳问题,每次k-Opt迭代都需要O(n^k)时间,2-Opt是Croes在1958年提出的一种局部搜索改进算法[3]。它起源于这样的想法,即边缘交叉的巡回路线不是最佳的。2-opt将考虑所有可能的2边交换,当2边交换以改善巡视时,2次选择O(n^2)每次迭代花费时间。

9、3选项
3-opt是2-opt的概括,其中一次交换3个边。移除3个边缘时,有7种不同的方式重新连接它们,因此将它们全部考虑在内,3-opt的时间复杂度O(n^3)适用于每个3-opt迭代。

10、Lin-Kernighan启发式
诸如Keld Helsgaun的LKH之类的Lin-Kernighan启发式实现可能会使用2-opt,3-Opt,4-Opt,5-Opt,“踢”的“行走”序列来逃避局部最小值,通过敏感性分析来指导和限制搜索以及其他方法。

LKH有2个版本;原始版本和LKH-2稍后发布。尽管这是一种启发式算法,而不是精确的算法,但它经常会产生最佳解决方案。它以已知的最佳长度收敛于每次旅行的最佳路线。在某个时间点或另一个时间点,它还为每个未知最佳问题设置了记录,例如World TSP,该位置有1,900,000个位置。

11、链接林-Kernighan
链式Lin-Kernighan是一种基于Lin-Kernighan启发式方法的旅游改进方法,它采用由Lin-Kernighan启发式方法产生的现有导览,通过“踢”修改它,然后再次将Lin-Kernighan启发式方法应用于它,根据其实现方式,当没有更多的改进,达到时间限制或达到最大长度等时,它可能会停止。

作为一种启发式方法,它不能将TSP解决到最佳状态。但是,它是子例程,用作最新的Concorde TSP求解器[5]的精确求解过程的一部分。


CPDA企业内训

https://www.cpda.cn/trainning/

 

CPDA项目数据分析师为什么要更名?

https://www.chinacpda.com/question/4504.html

 

海南智企数据分析师事务所

https://www.chinacpda.com/shiwusuo/14202.html

 

王兴海老师 高级经济师

https://www.chinacpda.com/shizi/9433.html

 

用数据改变人生,百万年薪不是梦,获得CPDA证书仅是一个开始

https://www.chinacpda.com/shouquanzhongxin/14854.html

 

大数据专业就业前景及就业方向如何?

https://www.chinacpda.com/wenti/11706.html

 

CPDA数据分析师学习方式和课程体系

https://www.chinacpda.com/xuexiarea/18089.html

 

数据分析师的职业进阶之路

https://www.chinacpda.com/zixun/4048.html

 

首个《中国大数据人才培养体系标准》正式发布!

https://www.chinacpda.com/dongtai/9669.html

 

CPDA数据说给你带来精彩的视频案例讲解

https://www.chinacpda.com/videocenter/

 

数据分析师职业考核

https://www.chinacpda.com/examine/

 

数据分析师职业规划

https://www.chinacpda.com/career/

 

CPDA数据分析师授权中心

https://www.chinacpda.com/train/

 

数据分析相关动态

https://www.chinacpda.com/data/?page=45

 

数据分析师为您解答更多问题

https://www.chinacpda.com/qa/

 

数据分析案例展示

https://www.chinacpda.com/case/

 

查找您周边省份授权培训中心:

https://www.chinacpda.com/train/

 

2020年CPDA数据分析师线上报名:

https://www.chinacpda.com/baoming.php

 

CPDA数据分析明星导师:

https://www.chinacpda.com/startutor/

 

CPDA数据分析师培训优秀学员:

https://www.chinacpda.com/student/

 

全国免费客服热线:400-050-6600

中国商业联合会数据分析专业委员会



Prev article

如何在数据驱动的企业中避免效率低下和增强信任度?

Next article

人工智能会杀死数据科学家吗?

课程服务

认证服务

在线咨询