算法的实际应用

‘壹’ 遗传算法具体应用

1、函数优化

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。

2、组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。

此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。

3、车间调度

车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。

从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

(1)算法的实际应用扩展阅读：

遗传算法的缺点

1、编码不规范及编码存在表示的不准确性。

2、单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3、遗传算法通常的效率比其他传统的优化方法低。

4、遗传算法容易过早收敛。

5、遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

‘贰’ 算法在前端开发的中实际应用有哪些

如果是游戏前端，算法很重要。。。比如角色寻路，主要就是使用A*算法，怪物的AI，通常需要使用树相关的算法，比如二叉树，行为树等。。。如果是APP或网页前端，实际工作中，需要使用算法的概率几乎是零。。

‘叁’ 计算机算法在实际生活中的应用

在这一周的《吴军的谷歌方法论》中，老师讲了地址（addressing）的重要性，并在此基础上介绍了地址的查找，数据的访问。对于地址的查找，在数据量较小时，可以采用顺序查找法和字典查找法；当数据量达到一定程度后，则需要为数据建立索引。而对于已经建立的索引进行查找，老师又详细介绍了具体方法的演进过程，引出随机性在索引查找中的应用。

通过上一周的学习，有如下几点收获：

1.理清问题，确定算法，选择语言

在这周的文章中读到，以前的人把计算当作目的，图灵是把计算当作手段，实现一些功能才是他的目的，回想起自己做研究生课题时遇到的一个问题。当时自己做的是机油滤芯过滤阻力和过滤精度的模拟计算，开始阶段采用二维模型来模拟圆筒状的滤芯。实际生产的滤芯是用木屑做的，填充率为31.8%，自己模拟计算也希望达到这个数值，但是初步的计算达不到这个数值，就向博士毕业的堂姐请教了这个问题：

堂姐的回复如下：

当时并没有非常理解她说的话，现在回过头来看，能更加明白她的意思了。对于一个具体的问题，可以采用的算法其实是非常多的，对于每一种算法又可以选择很多种实现的语言。但是我们解决问题的时候，一定要从问题这个根本出发，对于问题本身有足够深入的思考。在此基础上，明白解决这个问题采用怎样的算法最简洁高效，这是关键。至于选择那种语言或者工具，会对算法的实现效率产生一定影响，但不是最核心的。

2.从多个维度建立索引

对于算法的介绍中，老师强调了索引的重要性。关于建立索引，想到的两个应用的例子，一个是微信好友的标签，一个是印象笔记的标签。

对于我们在工作场合或者意外状况下认识的朋友，也许后期的联系会很少，那么建立细致的备注信息就很有必要。通过对聊天记录的梳理，在标签中注明行业，公司，家乡，甚至爱好，并且备注一些印象深的细节。这样不仅可以通过标签很快找到对应的人，而且在以后再次约见的时候，能通过这些标签信息，谈一些对方熟悉的话题，迅速拉近彼此的距离，对于我们的社交会有很大的帮助。

另外一个就是在印象笔记中建立新笔记时，可以建立尽量详细的标签。这在当时可能费事一点，但是后面随着笔记数量的增多，在海量笔记中通过标签来进行筛选，将是一件非常提升效率的事情。说到印象笔记，就像多说两句，因为真的很好用。建立标签就点击F3就可以开始建立新标签。

3.问题规模的增大会导致性质的变化

读到这句话时，想到之前脱不花和罗振宇两位老师在周二例会时讲得到的发展。当时得到总共的人数是157个人，刚刚超过邓巴数（人类智力允许人类拥有稳定社交网络的人数，为148）。

在邓巴数以内，公司里面的人可以彼此认识并且维持稳定的关系，不需要太明确的部门和上下级关系。但是两位老师讲到，随着公司里的人数超过邓巴数，那么部门化和层级化是不可避免的趋势，因为这样可以提高效率。但部门和层级的建立，会导致利益变形，之前大家是向市场要收益，更关注如何把自己的工作做好；之后是向上级要收益，更容易出现溜须拍马的现象。

不过正如老师所说，本着遇到问题解决问题的态度，即便问题转化了，只要大家发挥主动性，认真去面对问题，总会有解决方法。而且Google，苹果这样的公司树立了很好的榜样，现在已经非常大了，依然保持很好的运作和增长。

而作为个人，我们应该更多关注自己如何在企业不断扩大的过程中，保持自己本身的不断成长，为公司解决新的更复杂的问题，让自己一直拥有竞争力。这也是《领导梯队》中想要告诉我们的，在领导梯队的上升过程中，面对的不是更多同类的问题，而是全新的问题。我们要让自己学会转化思维模式，这样在旧问题已经转变成新问题时，可以更好去应对。

‘肆’ 有哪些计算思维内容得以实际运用，它们是如何改变人们身边的现状

1、预置和缓存：当你早晨去学校时，把当天需要的东西放进背包，这就是预置和缓存。

2、回推：当你朋友弄丢他的手套时，你建议他沿走过的路寻找，这就是回推。

3、在线算法：在什么时候停止租用滑雪板而为自己买一付呢，这就是在线算法。

4、多服务器系统的性能模型：在超市付帐时，你应当去排哪个队呢？这就是多服务器系统的性能模型。

5、失败的无关性和设计的冗余性：为什么停电时你的电话仍然可用？这就是失败的无关性和设计的冗余性。

(4)算法的实际应用扩展阅读：

有些问题是一次性的，但解决这些问题的方案，则可以不断发展。在同类问题一再出现时，算法思维就可以介入。没有必要重新每次从头思考，而是采用每次都行之有效的解决方案。

算法思维在许多“策略性“棋盘游戏中非常重要。理想情况下需要有保证胜利，或者至少不会输的策略。

所有这种策略都是一套规则，告诉你无需思索即怎么做每一步：也就是计算机科学家称之为算法的东西。如果你能建立这样的一套规则，这不仅可以成为完好游戏的基础，也成为一个设计优秀的计算机程序的基础。

‘伍’ 如何将数据结构和算法应用到实际之中

写一些程序，尤其是比较底层的程序。就明白它们的用处了。
列举下我们当初的作业（其实是老师从UC Santa Barbara\UC Berkley CS作业直接来题目）
（1）实现一个简单的 TCP 传输层的协议机制
自己去设计协议，不用照搬 RFC 的标准，其实就是数据结构的用场。
需要考虑到数据包丢失（Loss）、损坏（Corruption）、乱序（Disorder）这样的情况。
（2）实现操作系统的虚拟内存机制（基于Nachos系统）
如何去设计页表。如何使用置换算法。以及应用程序请求页的时候，发生缺页，从而导致的中断如何处理。
（3）实现一个简单的编译器（MiniJava）
词法：字符串匹配，表达式求值 等算法；
语法：生成抽象语法树；
语义：采用适当的设计模式（Visitor）来生成语义表、字典、然后转化为目标代码（可以是汇编、或者是类似的 Three-Address Code）
如果以上三个任务都完成并搞懂了，那么恭喜：你不仅掌握了数据结构、算法，而且也学习了计算机网络、操作系统、编译原理中大部分的知识。

‘陆’ A*算法的实际运用

估价值与实际值越接近，估价函数取得就越好
例如对于几何路网来说，可以取两节点间曼哈顿距离做为估价值，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijkstra算法的毫无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
详细内容：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表; while(OPEN!=NULL){从OPEN表中取估价值f(n)最小的节点n;if(n节点==目标节点)break;for(当前节点n的每个子节点X){算X的估价值;if(XinOPEN)if(X的估价值小于OPEN表的估价值){把n设置为X的父亲;更新OPEN表中的估价值;//取最小路径的估价值}if(XinCLOSE)continue;if(Xnotinboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中;//还没有排序}}//endfor将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。}//endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
用C语言实现A*最短路径搜索算法 ，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100//用于优先队列（Open表）的数组#defineHeight15//地图高度#defineWidth20//地图宽度#defineReachable0//可以到达的结点#defineBar1//障碍物#definePass2//需要走的步数#defineSource3//起点#defineDestination4//终点#defineSequential0//顺序遍历#defineNoSolution2//无解决方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{signedcharx,y;}Point;constPointdir[8]={{0,1},//East{1,1},//South_East{1,0},//South{1,-1},//South_West{0,-1},//West{-1,-1},//North_West{-1,0},//North{-1,1}//North_East};unsignedcharwithin(intx,inty){return(x>=0&&y>=0&&x<Height&&y<Width);}typedefstruct{intx,y;unsignedcharreachable,sur,value;}MapNode;typedefstructClose{MapNode*cur;charvis;structClose*from;floatF,G;intH;}Close;typedefstruct//优先队列（Open表）{intlength;//当前队列的长度Close*Array[MaxLength];//评价结点的指针}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY;//起始点、终点staticCloseclose[Height][Width];//优先队列基本操作voidinitOpen(Open*q)//优先队列初始化{q->length=0;//队内元素数初始为0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){//向优先队列（Open表）中添加元素Close*t;inti,mintag;cls[x][y].G=g;//所添加节点的坐标cls[x][y].F=cls[x][y].G+cls[x][y].H;q->Array[q->length++]=&(cls[x][y]);mintag=q->length-1;for(i=0;i<q->length-1;i++){if(q->Array[i]->F<q->Array[mintag]->F){mintag=i;}}t=q->Array[q->length-1];q->Array[q->length-1]=q->Array[mintag];q->Array[mintag]=t;//将评价函数值最小节点置于队头}Close*shift(Open*q){returnq->Array[--q->length];}//地图初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){//地图Close表初始化配置inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){cls[i][j].cur=&graph[i][j];//Close表所指节点cls[i][j].vis=!graph[i][j].reachable;//是否被访问cls[i][j].from=NULL;//所来节点cls[i][j].G=cls[i][j].F=0;cls[i][j].H=abs(dx-i)+abs(dy-j);//评价函数值}}cls[sx][sy].F=cls[sx][sy].H;//起始点评价初始值//cls[sy][sy].G=0;//移步花费代价值cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){//地图发生变化时重新构造地inti,j;srcX=sx;//起点X坐标srcY=sy;//起点Y坐标dstX=dx;//终点X坐标dstY=dy;//终点Y坐标for(i=0;i<Height;i++){for(j=0;j<Width;j++){graph[i][j].x=i;//地图坐标Xgraph[i][j].y=j;//地图坐标Ygraph[i][j].value=map[i][j];graph[i][j].reachable=(graph[i][j].value==Reachable);//节点可到达性graph[i][j].sur=0;//邻接节点个数if(!graph[i][j].reachable){continue;}if(j>0){if(graph[i][j-1].reachable)//left节点可以到达{graph[i][j].sur|=West;graph[i][j-1].sur|=East;}if(i>0){if(graph[i-1][j-1].reachable&&graph[i-1][j].reachable&&graph[i][j-1].reachable)//up-left节点可以到达{graph[i][j].sur|=North_West;graph[i-1][j-1].sur|=South_East;}}}if(i>0){if(graph[i-1][j].reachable)//up节点可以到达{graph[i][j].sur|=North;graph[i-1][j].sur|=South;}if(j<Width-1){if(graph[i-1][j+1].reachable&&graph[i-1][j].reachable&&map[i][j+1]==Reachable)//up-right节点可以到达{graph[i][j].sur|=North_East;graph[i-1][j+1].sur|=South_West;}}}}}}intbfs(){inttimes=0;inti,curX,curY,surX,surY;unsignedcharf=0,r=1;Close*p;Close*q[MaxLength]={&close[srcX][srcY]};initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;while(r!=f){p=q[f];f=(f+1)%MaxLength;curX=p->cur->x;curY=p->cur->y;for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].from=p;close[surX][surY].vis=1;close[surX][surY].G=p->G+1;q[r]=&close[surX][surY];r=(r+1)%MaxLength;}}times++;}returntimes;}intastar(){//A*算法遍历//inttimes=0;inti,curX,curY,surX,surY;floatsurG;Openq;//Open表Close*p;initOpen(&q);initClose(close,srcX,srcY,dstX,dstY);close[srcX][srcY].vis=1;push(&q,close,srcX,srcY,0);while(q.length){//times++;p=shift(&q);curX=p->cur->x;curY=p->cur->y;if(!p->H){returnSequential;}for(i=0;i<8;i++){if(!(p->cur->sur&(1<<i))){continue;}surX=curX+dir[i].x;surY=curY+dir[i].y;if(!close[surX][surY].vis){close[surX][surY].vis=1;close[surX][surY].from=p;surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY));push(&q,close,surX,surY,surG);}}}//printf(times:%d ,times);returnNoSolution;//无结果}constintmap[Height][Width]={{0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1},{0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1},{0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1},{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0},{0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1},{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={□,▓,▽,☆,◎};voidprintMap(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%s,Symbol[graph[i][j].value]);}puts();}puts();}Close*getShortest(){//获取最短路径intresult=astar();Close*p,*t,*q=NULL;switch(result){caseSequential://顺序最近p=&(close[dstX][dstY]);while(p)//转置路径{t=p->from;p->from=q;q=p;p=t;}close[srcX][srcY].from=q->from;return&(close[srcX][srcY]);caseNoSolution:returnNULL;}returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){Close*p;intstep=0;p=getShortest();start=p;if(!p){return0;}else{while(p->from){graph[p->cur->x][p->cur->y].value=Pass;printf(（%d，%d）→ ,p->cur->x,p->cur->y);p=p->from;step++;}printf(（%d，%d） ,p->cur->x,p->cur->y);graph[srcX][srcY].value=Source;graph[dstX][dstY].value=Destination;returnstep;}}voidclearMap(){//ClearMapMarksofStepsClose*p=start;while(p){graph[p->cur->x][p->cur->y].value=Reachable;p=p->from;}graph[srcX][srcY].value=map[srcX][srcY];graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){if(map[i][j]){printf(%s,Symbol[graph[i][j].value]);}else{printf(%2.0lf,close[i][j].G);}}puts();}puts();}voidprintSur(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02x,graph[i][j].sur);}puts();}puts();}voidprintH(){inti,j;for(i=0;i<Height;i++){for(j=0;j<Width;j++){printf(%02d,close[i][j].H);}puts();}puts();}intmain(intargc,constchar**argv){initGraph(map,0,0,0,0);printMap();while(scanf(%d%d%d%d,&srcX,&srcY,&dstX,&dstY)!=EOF){if(within(srcX,srcY)&&within(dstX,dstY)){if(shortestep=printShortest()){printf(从（%d，%d）到（%d，%d）的最短步数是:%d ,srcX,srcY,dstX,dstY,shortestep);printMap();clearMap();bfs();//printDepth();puts((shortestep==close[dstX][dstY].G)?正确:错误);clearMap();}else{printf(从（%d，%d）不可到达（%d，%d） ,srcX,srcY,dstX,dstY);}}else{puts(输入错误！);}}return(0);}

‘柒’ 算法在实际生活中的应用

求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。算法的这种特性，使得计算不仅可以由人，而且可以由计算机来完成。用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。
中国古代的筹算口决与珠算口决及其执行规则就是算法的雏形,这里,所解决的问题类是算术运算。古希腊数学家欧几里得在公元前3世纪就提出了一个算法,来寻求两个正整数的最大公约数，这就是有名的欧几里得算法,亦称辗转相除法。中国早已有“算术“、“算法”等词汇，但是它们的含义是指当时的全部数学知识和计算技能,与现代算法的含义不尽相同。英文algorithm(算法)一词也经历了一个演变过程，最初的拼法为algorism或algoritmi,原意为用阿拉伯数字进行计算的过程。这个词源于公元 9世纪波斯数字家阿尔·花拉子米的名字的最后一部分。
在古代，计算通常是指数值计算。现代计算已经远远地突破了数值计算的范围,包括大量的非数值计算,例如检索、表格处理、判断、决策、形式逻辑演绎等。
在20世纪以前，人们普遍地认为，所有的问题类都是有算法的。20世纪初，数字家们发现有的问题类是不存在算法的,遂开始进行能行性研究。在这一研究中,现代算法的概念逐步明确起来。30年代，数字家们提出了递归函数、图灵机等计算模型，并提出了丘奇－图灵论题（见可计算性理论），这才有可能把算法概念形式化。按照丘奇-图灵论题,任意一个算法都可以用一个图灵机来实现，反之，任意一个图灵机都表示一个算法。
按照上述理解，算法是由有限多个步骤组成的，它有下述两个基本特征：每个步骤都明确地规定要执行何种操作；每个步骤都可以被人或机器在有限的时间内完成。人们对于算法还有另一种不同的理解，它要求算法除了上述两个基本特征外,还要具有第三个基本特征:虽然有些步骤可能被反复执行多次，但是在执行有限多次之后，就一定能够得到问题的解答。也就是说，一个处处停机（即对任意输入都停机）的图灵机才表示一个算法，而每个算法都可以被一个处处停机的图灵机来实现
算法分类
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。
算法可以宏泛的分为三类：
有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。
有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。
无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。算法特征一个算法应该具有以下五个方面的重要特征：1、输入。一个算法有零个或多个输入，以刻画运算对象的初始情况。例如，在欧几里得算法中，有两个输入，即m和n。2、确定性。算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。例如，欧几里得算法中，步骤1中明确规定“以m除以n，而不能有类似以m除n以或n除以m这类有两种可能做法的规定。3、有穷性，一个算法在执行有穷步滞后必须结束。也就是说，一个算法，它所包含的计算步骤是有限的。例如，在欧几里得算法中，m和n均为正整数，在步骤1之后，r必小于n，若r不等于0，下一次进行步骤1时，n的值已经减小，而正整数的递降序列最后必然要终止。因此，无论给定m和n的原始值有多大，步骤1的执行都是有穷次。4、输出。算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。例如，在欧几里得算法中只有一个输出，即步骤2中的n。5、能行性。算法中有待执行的运算和操作必须是相当基本的，换言之，他们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。算法的描述1、用自然语言描述算法前面关于欧几里得算法以及算法实例的描述，使用的都是自然语言。自然语言是人们日常所用的语言，如汉语、英语、德语等。使用这些语言不用专门训练，所描述的算法也通俗易懂。2、用流程图描述算法在数学课程里，我们学习了用程序框图来描述算法。在程序框图中流程图是描述算法的常用工具由一些图形符号来表示算法。3、用伪代码描述算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号，因此，书写方便、格式紧凑，易于理解，便于向计算机程序设计语言过度。