位置：首页>> 网络编程>> JavaScript>> 蚁群算法js版（3）

蚁群算法js版（3）

作者：bjhaoyun　来源：蓝色理想　发布时间：2008-10-08 10:15:00　

标签：算法,蚂蚁,代码,js

这是无div的情形：初始化耗时28078ms（仅供参考）

运行代码框

<!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]){life[i]='<div class="point" style="left:'+xi0+';top:'+yi0+';"></div>';//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('无div生成耗时：'+((new Date()).getTime()-Time0)+'ms');Time0=(new Date()).getTime();}}//运动函数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]){life[i]='<div class="point" style="left:'+X+';top:'+Y+';"></div>';//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>

这是无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>

测试结果显示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>

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

第一页上一页 1 2

投稿

蚁群算法js版（3）

猜你喜欢