javascript设计模式交流

核心提示： 按照广搜的算法extend返回一个数组，包含当前节点扩展出的所有子节点,beam是剪枝函数，javascript设计模式交流(8)，它返回true表示当前节点可被剪除，否则该节点将被扩展,finish检查是否已搜索到最终结果，下面是完整的数据结构Code:<script>fun

按照广搜的算法extend返回一个数组，包含当前节点扩展出的所有子节点,beam是剪枝函数，它返回true表示当前节点可被剪除，否则该节点将被扩展,finish检查是否已搜索到最终结果，如果是则返回true则结束整个搜索。

这个例子过于抽象，我自己看起来都有些不知所云，所以我决定免费赠送一个用此搜索算法解决八皇后问题的例子的例子。

首先定义八皇后问题的数据结构,用最传统的类和对象来解决：

Code:

functionQueen(n){
　　varret=newArray();
　　vardepth=0;
　　for(vary=0;y<n;y++)
　　{
　　　　ret.push([]);
　　　　for(varx=0;x<n;x++)
　　　　　　ret[ret.length-1].push(0);
　　}
}

广搜算法是一个泛型算法，所以我们还可以把它设计成一个Prototype Patten，通过定义clone方法来使它不依赖具体类型，这里算是补充一个Prototype Patten的例子，综合使用的clone函数将大大提高clone的速度，我把这种clone方式称为"深原型clone"，它的开销比创建深clone对象小得多，且对clone体的修改不会影响到母体和其他clone体，但母体的修改会影响到所有clone体,为了调试方便，我们还可以定义一个toString显示美观一点的棋盘结构，ok，下面是完整的数据结构

Code:

<script>
functionQueen(n){
　　varret=newArray();
　　ret.size=n;
　　ret.depth=0;//搜索的深度
　　ret.pos=0;//新皇后的水平位置
　　for(vary=0;y<n;y++)
　　{
　　　　ret.push([]);
　　　　for(varx=0;x<n;x++)
　　　　　　ret[ret.length-1].push(0);
　　}
　　functionobjectPrototypeClone()
　　{
　　　　vartmp=function(){};
　　　　tmp.prototype=this;
　　　　returnnewtmp;
　　}
　　ret.clone=function(){
　　　　varr=objectPrototypeClone.call(this);
　　　　for(vari=0;i<n;i++)
　　　　{
　　　　　　r[i]=objectPrototypeClone.call(this[i])
　　　　}
　　　　returnr;
　　}
　　ret.toString=function(){
　　　　varstr="";
　　　　for(vary=0;y<n;y++)
　　　　{
　　　　　　for(varx=0;x<n;x++)
　　　　　　　　str+=this[y][x]==0?"○":"★";
　　　　　　str+="n";
　　　　}
　　　　returnstr;
　　}
　　returnret;
}
</script>

接下来进入正题，写出八皇后问题的extend beam finish三个函数

extend函数非常容易，八皇后问题每层搜索一行，extend函数即扩展一个新行

Code:

functionextendQueen()
{
　　varret=newArray();
　　//alert(this.depth);
　　for(vari=0;i<this.size;i++)
　　{
　　　　varcurrent=this.clone();
　　　　//alert(current.depth);
　　　　current[current.depth][i]=1;
　　　　current.pos=i;
　　　　current.depth++;
　　　　ret.push(current);
　　}
　　returnret;
}

beam函数则是检查新的皇后能否吃到以前的皇后

Code:

functionbeamQueen()
{
　　varx,y;
　　if(this.depth==0)returnfalse;
　　if(this.depth==this.size)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--x>=0&&--y>=0)
　　　　if(this[y][x]!=0)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0)
　　　　if(this[y][x]!=0)returntrue;
　　x=this.pos;y=this.depth-1;
　　while(--y>=0&&++x<this.size)
　　{
　　　　if(this[y][x]!=0)returntrue;
　　}
　　returnfalse;
}

http://blog.csdn.net/onlyzhangqin/archive/2008