蚁群算法js版--打印文章

打印本文

关闭窗口

蚁群算法js版

作者：武汉SEO闵涛文章来源：敏韬网点击数2024 更新时间：2009/4/23 14:10:12 文章录入：mintao 责任编辑：mintao

这是无move函数的情形，初始化耗时12437ms（仅供参考）

运行代码框
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"><HEAD> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> .point{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=500;Path=1; //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //生命体运动范围 x0=0;xM=document.documentElement.clientWidth; y0=0;yM=document.documentElement.clientHeight; //生命体出生地(蚁巢) xi0=(x0+xM)/2;yi0=(y0+yM)/2; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var x=new Array(); var y=new Array(); var life=new Array(); //单击暂停 window.status='pause'; var Time0; function document.onclick(){ if(window.status=='pause'){ window.status=0; Time0=(new Date()).getTime(); init(0); }else{ window.status='pause'; } } //边界随窗口大小调整 function window.onresize(){ xM=document.documentElement.clientWidth; yM=document.documentElement.clientHeight; xi0=(x0+xM)/2; yi0=(y0+yM)/2; } //初始化函数 function init(i){ if(window.status!='pause'&&i<Unit){ if(!life[i]){ str='<div class="point" style="left:'+xi0+';top:'+yi0+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); x[i]=xi0; y[i]=yi0; r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); } //Move(i); window.status=i+1; setTimeout('init('+(i+1)+')',0/*i*/); }else{ alert('无move函数生成耗时：'+((new Date()).getTime()-Time0)+'ms'); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(window.status!='pause'){ k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ str='<div class="point" style="left:'+X+';top:'+Y+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); obj.style.left=x[k]=X; obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',/*Unit*/45); } } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body scroll="no"> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

测试结果显示div并不是速度的瓶颈，最影响速度的是move函数本身，所以优化它才是解决问题的关键所在！
更新了下，原先测的时间还偏长了些，因为不是严格在调用init前起获取时间

思路2：用vml中的path指令做点

经过学习终于搞明白了怎么用vml做点，并试着生成2000~4000个点看看，结果显示生成时间和点的数量已成正比，基本达到优化的目的，接下来的工作就是用vml实现了。

以下代码生成随机4000个由蚁巢出发的线段，大家放心了，生成中基本速度不减慢（看状态栏），当然机器较慢的朋友还是请适当减小参数再浏览。

运行代码框
<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office"> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>蚁群算法js版</title> <style> v\:*{behavior:url(#default#VML);}o\:*{behavior:url(#default#VML);} .ant{ position:absolute; background-color:#000000; overflow:hidden; width:2px; height:2px; } .food{ position:absolute; background-color:#0000ff; overflow:hidden; width:2px; height:2px; } .nest{ position:absolute; background-color:#ff0000; overflow:hidden; width:2px; height:2px; } </style> <script type="text/JavaScript"> //============================ //系统参数初始化 //---------------------------- //生命体数量与轨迹长度 Unit=4000;Path=1; //生命体运动范围 x0=0;xM=500; y0=0;yM=500; //生命体出生地(巢穴) var xi0=x0+(xM-x0)*Math.random(); var yi0=y0+(yM-y0)*Math.random(); //var str0='<div class="ant" style="left:'+xi0+';top:'+yi0+';"></div>'; var str0=Math.floor(xi0)+','+Math.floor(yi0); //食物所在地 xf=x0+(xM-x0)*Math.random(); yf=y0+(yM-y0)*Math.random(); /*---------------------------------- //生命体速度上下限 v0=2;vM=10; //生命体加速度变化范围 Kr=0.1;Kv=0.1*(vM-v0); //气味感知范围 R_2=5*5; //============================ var r=new Array(); var v=new Array(); var dr=new Array(); var dv=new Array(); var life=new Array(); /*================================*/ //单击暂停 var xi0,yi0,xf,yf; var Time0,clicked; window.status='pause'; function document.onclick(){ if(clicked){ window.status='pause'; return clicked=false; } window.status=0; nest.style.left=xi0; nest.style.top=yi0; food.style.left=xf; food.style.top=yf; clicked=true; //测试初始化时间用 Time0=(new Date()).getTime(); init(0); } //窗口大小调整后刷新页面以调整系统参数 function window.onresize(){ // window.location.href=document.location; } //初始化函数 var point=new Array(); function init(i){ if(!clicked) return false; if(i<Unit){ xi0=x0+(xM-x0)*Math.random(); yi0=y0+(yM-y0)*Math.random(); point[i]=Math.floor(xi0)+','+Math.floor(yi0); /*---------------------------------- r[i]=Math.random(); v[i]=1/Math.random(); dr[i]=Kr*Math.random(); dv[i]=Kv*Math.random(); /*================================*/ //Move(i); setTimeout('init('+(window.status=++i)+')',0); }else{ shape1.outerHTML=shape1.outerHTML.replace(/ path = \".*?\"/,' path = \"m'+str0+'l'+point.join('m'+str0+'l')+' e\"'); alert('生成耗时：'+((new Date()).getTime()-Time0)+'ms'); } } //运动函数 Total=Unit*Path; P2=2*Math.PI; function Move(i){ if(!clicked) return false; k=i%Unit; X=x[k]; Y=y[k]; R=r[k]; V=v[k]; if(!life[i]){ str='<div class="ant" style="left:'+X+';top:'+Y+';"></div>'; document.body.appendChild(life[i]=document.createElement(str)); } obj=life[i]; R+=dr[k]*(2*Math.random()-1); V+=dv[k]*(2*Math.random()-1); X+=Math.sin(P2*R)*V; Y+=Math.cos(P2*R)*V; //遇到食物原路返回并减小角度变化 distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0); if(distance<R_2){ R+=0.5; r[i]/=2; v[i]*=2; } /*---------------------------------- /*================================*/ //碰撞边界反弹 R=(X<x0||X>xM)?-R:R; R=(Y<y0||Y>yM)?0.5-R:R; X=x[k]+Math.sin(P2*R)*V; Y=y[k]+Math.cos(P2*R)*V; /*================================*/ //溢出边界重生(类似流星效果) if(X<x0||X>xM||Y<y0||Y>yM){ X=xi0; Y=yi0; } /*---------------------------------- /*================================*/ //边界限制 x[k]=X=(X<x0)?x0:(X>xM)?xM-2:X; y[k]=Y=(Y<y0)?y0:(Y>yM)?yM-2:Y; r[k]=R>1?R-1:R<0?R+1:R; v[k]=V=(V<v0)?v0:((V<vM)?V:vM); /*================================*/ obj.style.left=x[k]=X; obj.style.top=y[k]=Y; setTimeout('Move('+(i+Unit)%Total+')',Unit); } //根据浏览器自动加载动画 switch(navigator.appName.toLowerCase()){ case "netscape": window.addEventListener("load",document.onclick,false); break; case "microsoft internet explorer": default: window.attachEvent("onload",document.onclick); break; } </script> </head> <body style="margin:0px;"> <v:group ID="group1" style="position:relative; left:0px; top:0px;WIDTH:500px;HEIGHT:500px;" coordsize = "500,500"> <v:rect filled="f" style="width:100%;height:100%" /> <v:PolyLine filled="f" Points="0 0" /> <v:shape id=shape1 name=shape1 filled="f" style="width:100%;height:100%" path="m 0,0 e" /> </v:group> <div id="food" class="food"></div> <div id="nest" class="nest"></div> </body> </html>
[Ctrl+A 全部选择提示：你可先修改部分代码，再按运行]

顺便说下这里用到了join函数来连接坐标字符串数组从而达到降低时间复杂度的目的。

经典论坛讨论帖：
http://www.blueidea.com/bbs/NewsDetail.asp?id=2539054

上一页 [1] [2]

打印本文

关闭窗口