李俊良
- 浏览: 145408 次
- 性别:
- 来自: 北京
-
文章分类
- 全部博客 (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 2091直接上代码 代码里面注释很清晰 传说中的最难数组大概是在 ... -
利用闭包重写document.createElement函数
2011-11-11 10:08 1393document.createElement = (funct ... -
简单的迷宫算法学习
2011-10-24 21:48 888<!DOCTYPE html> <h ... -
纯js版本网页连连看原理分析和实现
2011-01-18 22:07 1953html页面部分matching.html <! ... -
Firefox addon开发小介绍
2010-12-17 16:24 2351这算是个交流贴吧，对新手比较有用 firefox ad ... -
百度贴吧里面的打豆豆游戏的打200分辅助程序-更新了程序，源码不贴了
2010-10-29 16:42 1299写的比较烂 有兴趣的可以去改一下，做不到太 ... -
sina web前端js工程师的一道面试题
2010-03-22 11:33 3787统计从1至400亿之间的自然数中含有多少个1？比如1-11中， ... -
连连看游戏JavaScript版本
2010-02-03 10:44 1194方法就不多了，见附件里面自己看吧，其实不是很难，代码还没有优化 ... -
根据id或者obj返回对象
2010-01-30 21:15 1051/** 根据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
政采云前端所用到的算法是IT行业中的一个关键知识点，尤其是对前端工程师而言，理解并运用各种算法不仅能够优化代码性能，提升解决复杂问题的能力，而且在应聘面试中也是一大加分项。本小册子将重点介绍前端开发中...
需要微信公众号签名算法的可以在这里下载下来，sign.js，使用方法已经在我博客里面提及到，敬请下载
前端纯js加密、以及后端java解密代码。...常用的主要有SM2，SM3，...最近公司也是要求使用国密加密算法， 折腾了半天，也没有找到合适的资源，所以我这里统一提供了sm2\sm3\sm4 js 前端解解密的demo.需要的小伙伴自行下载
总结来说，"前端 RSA 分段加密算法"是一种确保前端数据安全的策略，它利用RSA非对称加密的特性，结合分段加密的方法，处理大长度的数据，使得在前端环境中也能实现高效且安全的数据加密。"jsencrypt.min.js"库为...
通过前端技术实现算法可视化，不仅可以提升学习体验，也体现了IT技术在教育领域的创新应用。 总的来说，这个资源包提供了一个很好的实例，让我们了解如何利用前端技术将枯燥的算法转变为生动的动画，这对于提升编程...
通过学习和实践这些JavaScript算法，开发者可以提升解决问题的能力，更好地应对前端开发中的性能挑战。同时，这些基础知识也是面试中常考的点，对于准备面试或提高自身技能都有极大的帮助。在实际工作中，理解并熟练...
在前端开发领域，掌握一定的手写题和算法是至关重要的，这不仅能提升代码质量和效率，还能在面试中展现出扎实的技术基础。以下是对标题、描述中提及的知识点的详细阐述： 1. CSS（层叠样式表）： - 布局技术：包括...
这个压缩包文件名为“校招社招前端面试题合集JS源码JS代码（260题）”，包含了260个JavaScript相关的面试题目，涵盖了从基础到高级的各种问题，旨在帮助应聘者全面准备面试。 首先，我们要理解JavaScript的基础知识...
本文将详细探讨SM2算法的原理、使用场景，以及在前端js中实现加解密和签名验签的方法，同时参考sm-crypto库的使用。 首先，SM2算法的核心是椭圆曲线加密，它利用椭圆曲线上的数学性质来构建公钥和私钥。公钥是可以...
径向树布局算法是一种在图形可视化领域常用的布局方式，它以根节点为中心，将树状结构的数据以辐射状展示出来，使得整个结构清晰且...理解其核心原理并能实现这一算法，将有助于你在图形编程和数据可视化领域更进一步。
前端手写题集锦 记录大厂笔试，面试常考手写题，2022 年前端面试中常见的 leetcode 算法题, 致力打造最全的前端 JavaScript 手写题题库和答案的最优解
md5.js下载 MD5信息摘要算法（英语：MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128位（16字节）的散列值（hash value），用于确保信息传输完整一致。MD5由美国密码学家罗纳德·...
【冒泡排序】 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。...了解并熟练掌握这些基础算法对于提升前端开发者的技能水平至关重要。
总结来说，准备这些面试题时，前端开发者需要熟悉JavaScript语言的核心特性，掌握常见算法和数据结构，理解DOM操作和事件处理，还要有一定的性能优化和工程化实践经验。同时，了解和应用前端框架、了解前端最新趋势...
JavaScript版数据结构与算法 轻松解决前端算法面试【完整版15章】，2020新课，不要因为做前端，就忽略算法的重要性！本课程带你用JS语言解决LeetCode上的经典算法题，对每一道题都进行线上测试，每题都有时间/空间...
前端面试刷题必备，阮一峰ES6教程、JavaScript笔记、html、css、JavaScript、Vue、React、算法、前端日记Blog
在本项目中，“纯JS象棋 AI算法”指的是一个完全基于JavaScript编程语言实现的在线象棋游戏，其中包含了人工智能（AI）的算法来模拟对手的智能行为。这种类型的项目不仅展示了JavaScript在前端开发中的强大能力，还...