李俊良
- 浏览: 142251 次
- 性别:
- 来自: 北京
-
文章分类
- 全部博客 (104)
- Javascript For XML (3)
- Ajax (4)
- JS 地图API 学习 (0)
- DIV+CSS (10)
- javascript兼容性 (6)
- javascript对象讨论 (3)
- 前端优化思考 (7)
- 遐想 (2)
- 一些小函数 (10)
- cheat sheets (0)
- YUI3分析 (3)
- nodejs (2)
- 数据恢复 (1)
- Javascript 等于号的研究 (1)
- Javascript操作符理解 (1)
- javascript原始数据类型 (1)
- javascript (2)
- erlang nitrogen (7)
- Erlang (6)
- yii (1)
最新评论
-
46311875：
SB。 搞得那么复杂。哈哈
html5单页面应用程序之历史记录控制 -
李俊良：
正准备处理移动版本的兼容，貌似移动端的用纯web做的比较少
瀑布流网站记录 -
wolf199103：
花瓣网：http://huaban.com/鼻祖Pintere ...
瀑布流网站记录 -
firstfall：
<div class="quote_title ...
前端js也能写算法 -
Sky_YiBai：
楼主，可不可以把帖子重新编辑下，别光写代码呢。。。写点思路之类 ...
前端js也能写算法
先简单的介绍下遗传算法
遗传算法说白了就是模拟遗传的方式来得到一个问题的答案
整个过程就是这样的
1.生成一个基因组群
2.针对基因组群中每一条基因计算它的适应性分数
3.判断是否有某一条基因的适应性分数已经跟需要的期望结果一直，如果是就停止算法
4.没有就开始下一个轮次的迭代
5.利用一种竞争算法，从上一个基因组群中随机找到一个父亲的基因和一个母亲的基因，按杂交率进行杂交，并将杂交后的两个基因放入到下代的基因组群中
6.利用一种竞争算法，从上一个基因组群中随机找到一个基因，按一定的变异率变异，并将变异后的基因放入到下代的基因组群中
重复5,6，直到下代的基因组群的长度和父代一直
7，再次计算下代的适应性分数，然后重复，4，5,6,7直到找到答案
<!doctype html>
<html>
<head>
<title>html5 迷宫算法</title>
<style>
body{background-color:green;}
#map{marign:100px auto;width:330px;font-family:"微软雅黑";font-size:12px;}
#map:after{content:"";clear:both;}
#map > div{width:60px;line-height:60px;height:60px;margin:2px 0 0 2px;background-color:#ccc;float:left;text-align:center;color:white;font-weight:bold;}
#map > div.box8{background-color:green;}
#map > div.box5{background-color:red;}
#map > div.box1{background-color:#f93;}
#map > div.step{background-color:green;}
#map > div.null{background-color:white;}
</style>
</head>
<body>
<div id="map">
</div>
<script>
Array.prototype.clone=function(){
return [].concat(this);
}
var game = function(element,options){
options = options || {number:9};
this.element = this.get(element);
this.width = Math.pow(options.number,0.5);
this.timer = 1000;
this.crossrate = 0.9;//杂交率
this.mutationrate = 0.1 //变异率
this.veclen =400;//基因组的长度
this.zero = null;
this.count = 0;
this.good = null;
this.inerterval = null;
this.finished = false;
this.map = (function(){
// 随即生成1到100的打乱的数组，这个算法是跟JK学习的，也算是一种洗牌算法，感觉不错，谢谢JK
var i,
len = 9,
oldsource = [1,2,3,4,5,6,7,8,0];
var cpos = 8,tmp;
for(i = 0 ; i < 1000 ; i++){
var random = Math.floor(Math.random()*5);
if(random == 0){//上
if(cpos < 3){
continue;
}else{
tmp = oldsource[cpos];
oldsource[cpos] = oldsource[cpos-3];
oldsource[cpos-3] = tmp;
cpos = cpos -3;
}
}else if(random == 1){
if(cpos >=6){
continue;
}else{
tmp = oldsource[cpos];
oldsource[cpos] = oldsource[cpos+3];
oldsource[cpos+3] = tmp;
cpos = cpos +3;
}
}else if(random == 2){
if(cpos % 3 ==0){
continue;
}else{
tmp = oldsource[cpos];
oldsource[cpos] = oldsource[cpos-1];
oldsource[cpos-1] = tmp;
cpos = cpos -1;
}
}else{
if((cpos+1) %3 ==0){
continue;
}else{
tmp = oldsource[cpos];
oldsource[cpos] = oldsource[cpos+1];
oldsource[cpos+1] = tmp;
cpos = cpos +1;
}
}
}
return oldsource;
}());
this.group = (function(){
var arr = [],
len = 160,
veclen = 400;
for(var i = 0 ; i < len ; i++){
var vec = [];
for(var j = 0 ; j < veclen ; j++){
vec.push(Math.floor(Math.random()*4));
}
arr.push(vec);
}
return arr;
})();
this.minscore = null;
this.max = "0|group";
this.cmap = null;
this.score = (function(){
var arr = [],
len = 160;
for(var i = 0 ; i < len; i++){
arr.push(0);
}
return arr;
})();
this.initmap();
}
game.prototype = {
initmap:function(){
var i = 0,
j = 0,
width = this.width ,
html = [],
map = this.map;
for(i = 0;i < width ; i++){
var tmp = [];
for(j=0;j < width ; j++){
var value = map[i*3+j];
tmp.push("<div class='box1 "+(value == 0 ? "null":"")+"' index='"+(i*3+j)+"'>"+value+"</div>");
}
html.push(tmp.join(""));
}
this.element.innerHTML = html.join("");
this.element.style.width = width * 64 + "px";
for(i = 0 ; i < width*width ; i++){
if(map[i] == 0){
this.zero = i;
break;
}
}
},
get:function(element){
return typeof element == "string" ? document.getElementById(element) : element;
},
slove:function(){
},
/**
*
*a,b为map中的index位置
*/
swap:function(a,b){
var map = this.map;
var el_a,el_b;
var els = this.element.getElementsByTagName("div");
for(var i = 0 ; i < els.length ; i++){
var el = els[i];
if(el.innerHTML == map[a]){
el_a = el;
}
if(el.innerHTML == map[b]){
el_b = el;
}
}
var tmp = map[a];
map[a] = map[b];
map[b] = tmp;
// 交换内容
tmp = el_a.innerHTML;
el_a.innerHTML = el_b.innerHTML;
el_b.innerHTML = tmp;
//交换index
tmp = el_a.getAttribute("index");
el_a.setAttribute("index",el_b.getAttribute("index"));
el_b.setAttribute("index",tmp);
//交换class
tmp = el_a.className;
el_a.className = el_b.className;
el_b.className = tmp;
},
/**
*杂交
*/
cross:function(mum,dad,crossrate){
var child1 = mum,child2 = dad;
crossrate = crossrate || this.crossrate;
var crate = Math.random();
if(crate < crossrate)
return [mum,dad];
var crosspos = Math.floor(Math.random()*this.veclen);
for(var i = 0 ; i < crosspos ; i ++){
child1[i] = mum[i];
child2[i] = dad[i];
}
for(i = crosspos ; i < this.veclen ; i++){
child2[i] = mum[i];
child1[i] = dad[i];
}
return [child1,child2];
},
draw:function(good){
var good = good || this.good,
index = this.goodindex;
var i = 0 ;
var me = this;
var tmppos = me.zero;
me.inerterval = setInterval(function(){
if(me.map.join("") == [1,2,3,4,5,6,7,8,0].join("") || i > index){
window.clearInterval(me.inerterval);
}
var dot = good[i];
if(dot == 0){//上
if(me.zero >= 3){
me.swap(me.zero,me.zero-3);
me.zero = me.zero-3;
}
}else if(dot==1){//下
if(me.zero < 6){
me.swap(me.zero,me.zero+3);
me.zero = me.zero+3;
}
}else if(dot==2){//左
if(me.zero%3 != 0){
me.swap(me.zero,me.zero-1);
me.zero = me.zero-1;
}
}else if(dot==3){//右
if((me.zero+1)%3 != 0){
me.swap(me.zero,me.zero+1);
me.zero = me.zero+1;
}
}
i++;
},50);
},
/**
*变异
*/
mutation:function(data,crate){
crate = crate == true ? 0: Math.random();
if(crate > this.mutationrate){
return data;
}
var crosspos;
for(var i = 0 ; i < 8;i++){
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
}
return data;
},
/**
*变异所有
*/
mutationall:function(){
for(var i = 0 ; i < this.group.length ; i++){
var data = this.group[i];
var crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
crosspos = Math.floor(Math.random()*this.veclen);
data[crosspos] = Math.floor(Math.random()*4);
}
},
/**
*赌轮算法
*/
wheel:function(){
var group = this.group,
score = this.score,
len = group.length,
totalscore = this.getTotalScore(),
plusscore = 0,
r = null,
random = Math.random()*totalscore;
for(var i = 0 ; i < len ; i++){
if(plusscore >= random){
return group[i];
break;
}else{
plusscore+=parseInt(score[i]);
}
}
return group[0];
},
/**
*获取分数综合
*/
getTotalScore:function(){
var sum = 0;
for(var i = 0 ; i < this.score.length ; i++){
sum += parseInt(this.score[i]);
}
return sum;
},
/**
*根据当前的group来计算适应性分数
*/
updateScore:function(){
var group = this.group,
score = this.score,
len = group.length;
for(var i = 0 ; i < len ; i++){
score[i] = this.getScore(group[i]);
if(this.minscore == null){
this.minscore = group[i];
}else{
if(score[i] < this.minscore){
this.minscore = group[i];
}
}
if(score[i] == 9){
this.good = group[i];
this.finished = true;
break;
}
}
},
getScore:function(vec){
var tmpgroup = this.map.clone(),
tmppos = this.zero;
var anim = [];
var ans = [1,2,3,4,5,6,7,8,0];
//console.log(tmpgroup);
for(var i = 0 ; i < vec.length ; i++){
var dot = parseInt(vec[i]);
if(dot == 0){//上
if(tmppos < 3){
continue;
}
anim.push(dot);
var temp = tmpgroup[tmppos-3];
if(temp == undefined) console.log("un")
tmpgroup[tmppos-3] = tmpgroup[tmppos];
tmpgroup[tmppos] = temp;
tmppos = tmppos-3;
if(this.check(tmpgroup,i)){
console.log("finished,路径为:"+anim.join(""));
this.goodindex= i;
this.draw(anim)
return 9;
break;
}
}else if(dot==1){//下
if(tmppos >= 6){
continue;
}
anim.push(dot);
var temp = tmpgroup[tmppos+3];
if(temp == undefined) console.log("un")
tmpgroup[tmppos+3] = tmpgroup[tmppos];
tmpgroup[tmppos] = temp;
tmppos = tmppos+3;
if(this.check(tmpgroup,i)){
console.log("finished,路径为:"+anim.join(""));
this.goodindex= i;
this.draw(anim)
return 9;
break;
}
}else if(dot==2){//左
if(tmppos%3 == 0){
continue;
}
anim.push(dot);
var temp = tmpgroup[tmppos-1];
if(temp == undefined) console.log("un")
tmpgroup[tmppos-1] = tmpgroup[tmppos];
tmpgroup[tmppos] = temp;
tmppos = tmppos-1;
if(this.check(tmpgroup,i)){
console.log("finished,路径为:"+anim.join(""));
this.goodindex= i;
this.draw(anim)
return 9;
break;
}
}else if(dot==3){//右
if((tmppos+1)%3 == 0){
continue;
}
anim.push(dot);
var temp = tmpgroup[tmppos+1];
if(temp == undefined) console.log("un")
tmpgroup[tmppos+1] = tmpgroup[tmppos];
tmpgroup[tmppos] = temp;
tmppos = tmppos+1;
if(this.check(tmpgroup,i)){
console.log("finished,路径为:"+anim.join(""));
this.goodindex= i;
this.draw(anim)
return 9;
break;
}
}
}
var nowscore = 0;
for(var i = 0 ; i < 9 ; i++){
if(ans[i]== tmpgroup[i]){
nowscore ++;
}
}
var a = this.max.split("|");
if(nowscore > parseInt(a)){
this.max = nowscore + "|" + tmpgroup.join("");
}
this.cmap = tmpgroup;
return nowscore;
},
check:function(group,index){
var ans = [1,2,3,4,5,6,7,8,0],nowscore = 0;
for(var i = 0 ; i < 9 ; i++){
//for(var j = 0 ; j < 9 ; j++){
if(ans[i]== group[i]){
nowscore ++;
}
}
return nowscore == 9;
},
/**
*生成下一个子代的基因族群
*/
nextGroup:function(){
var group = this.group,
len = group.length,
newgroup = [],
greatChild = 0;
for(var i = 1 ; i < len ; i++){
if(this.score[i] > this.score[greatChild]){
greatChild = i;
}
}
while(newgroup.length < len){
if(this.count > 1000){
this.mutationall();
}
var mum = this.wheel();
var dad = this.wheel();
//console.log(mum,dad);
//console.log(this.cross(mum,dad));
if(mum == dad){
newgroup.push(this.mutation(mum));
}else{
//console.log(childs);
var childs = this.cross(mum,dad,this.crossrate);
if(newgroup.length < len){
newgroup.push(childs[0])
}
if(newgroup.length < len){
newgroup.push(childs[1])
}
}
var child = this.wheel();
if(newgroup.length < len){
newgroup.push(this.mutation(child));
}
}
for(var i = 0 ; i < len ; i++){
this.group[i] = newgroup[i];
}
//console.log(this.group,newgroup);
},
epoch:function(){
var me = this;
me.count++;
me.updateScore();
me.nextGroup();
//console.log(me.getTotalScore());
if(!me.finished && me.timer > 0){
me.timer--;
me.epoch();
}else{
this.timer = 1000;
console.log("stoped");
}
}
}
var g = new game("map");
</script>
</body>
</html>
0
顶
顶
3
踩
踩
分享到：
评论
4 楼
firstfall
2012-11-22
BuN_Ny 写道
最近很不喜欢这种只贴代码的帖子。总觉得是想表达：我写的很牛逼的，你们看去吧！
同感
3 楼
Sky_YiBai
2012-11-22
楼主，可不可以把帖子重新编辑下，别光写代码呢。。。写点思路之类的，你题目起得很好，内容我觉得更像是自己在备份代码
2 楼
java_frog
2012-11-22
晕，不好玩
1 楼
BuN_Ny
2012-11-22
最近很不喜欢这种只贴代码的帖子。总觉得是想表达：我写的很牛逼的，你们看去吧！
发表评论
-
js回溯算法解决数独问题
2018-09-17 17:34 2031直接上代码 代码里面注释很清晰 传说中的最难数组大概是在 ... -
利用闭包重写document.createElement函数
2011-11-11 10:08 1322document.createElement = (funct ... -
简单的迷宫算法学习
2011-10-24 21:48 864<!DOCTYPE html> <h ... -
纯js版本网页连连看原理分析和实现
2011-01-18 22:07 1933html页面部分matching.html <! ... -
Firefox addon开发小介绍
2010-12-17 16:24 2327这算是个交流贴吧，对新手比较有用 firefox ad ... -
百度贴吧里面的打豆豆游戏的打200分辅助程序-更新了程序，源码不贴了
2010-10-29 16:42 1268写的比较烂 有兴趣的可以去改一下，做不到太 ... -
sina web前端js工程师的一道面试题
2010-03-22 11:33 3762统计从1至400亿之间的自然数中含有多少个1？比如1-11中， ... -
连连看游戏JavaScript版本
2010-02-03 10:44 1152方法就不多了，见附件里面自己看吧，其实不是很难，代码还没有优化 ... -
根据id或者obj返回对象
2010-01-30 21:15 1003/** 根据id或者对象返回对象或者对象数组 */ ...
相关推荐
前端学习 html css js 算法前端学习 html css js 算法前端学习 html css js 算法 前端学习 html css js 算法前端学习 html css js 算法前端学习 html css js 算法 前端学习 html css js 算法前端学习 html css js ...
虽然说在前端很少有机会接触到算法，大多都交互性的操作，然而从各大公司面试来看，算法依旧是考察的一...下面这篇文章就给大家总结了在前端JS面试中常见的算法问题，有需要的朋友们可以参考借鉴，下面来一起看看吧。
前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip前端JavaScript算法集源码.zip
需要微信公众号签名算法的可以在这里下载下来，sign.js，使用方法已经在我博客里面提及到，敬请下载
校招社招前端面试题合集JS源码JS代码（260题）JS算法题数据结构算法等，详情预览见：https://www.uu2id.com/34939.html，JS手写代码算法题
本算法利用原生的javascript完成了径向树状图（完成了两组）
css、js常见手写题、js继承相关、js数组相关、排序算法、设计模式、树场景题、异步相关、正则相关、组件设计
JavaScript版数据结构与算法 轻松解决前端算法面试【完整版15章】，2020新课，不要因为做前端，就忽略算法的重要性！本课程带你用JS语言解决LeetCode上的经典算法题，对每一道题都进行线上测试，每题都有时间/空间...
md5.js下载 MD5信息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。MD5由美国密码学家罗纳德·...
国密算法SM2公私钥加解密及签名验签以及前端js sm-crypto，附件说明及参考及测试方法； 国密算法SM2公私钥加解密及签名验签以及前端js sm-crypto，附件说明及参考及测试方法
RSA非对称加密，前端加解密算法代码。公钥明文，私钥各自保存，公钥加密，私钥解密。 RSA分段加密 适用于加密长度超标，可用于图片base64等大长度内容加密。
前端 RSA 加密算法 JS 库。公钥加密算法，非对称加密算法。
对应该文章 https://blog.csdn.net/qq_41970599/article/details/131134770?spm=1001.2014.3001.5501 C# 实现对称加密算法（AES）与非对称加密算法（RSA），实现前后端敏感数据的加密传输
2019js数组前端经典算法面试题.docx2019js数组前端经典算法面试题.docx
前端js 算法题目实例解析；包括数组小于0放左大对于0放右；买与卖获取最大利润；字符串压缩；求无重复字符的最长子串；获取会问字符串
前端人专属面试宝典，包括经典面试题、手写题、JavaScript版数据结构与算法和场景题等等，代码中包含清晰的注释。如果你是前端小白，建议先熟悉HTML、CSS、JavaScript。如果你是前端老兵，建议从基础开始复习起来，...
前端开发 opencvjs 该文件是编译好的opencv JavaScript版本，直接下载就可以使用。
前端实现国密4,JavaScript代码
前端纯js加密、以及后端java解密代码。...常用的主要有SM2，SM3，...最近公司也是要求使用国密加密算法， 折腾了半天，也没有找到合适的资源，所以我这里统一提供了sm2\sm3\sm4 js 前端解解密的demo.需要的小伙伴自行下载