深度优先搜索广度优先搜索 A*搜索的算法封装

yiyiyicz 2012-11-09

展开全文

http://www./html/jsjc/20080425/1906.html

封装了搜索算法包括一个通用的搜索模板和三种搜索：深度优先搜索广度优先搜索 A*搜索

function Currying(func)//将一个函数转换为Currying形式参考51js月影的旧帖
{
return function()
{
var args = Array.prototype.slice.call(arguments,0);
if(args.length<func.length)
{
return function(){
var _args = args.concat(Array.prototype.slice.call(arguments,0));
return Currying(func).apply(this,_args);
}
}
else return func.apply(this,args);
}
}

复制代码

//搜索算法的通用模板
//Collection是保存open节点的数据结构不同的搜索算法需要不同的Collection结构如果是自己写的数据结构需要用一个Adapter使它实现 put get和empty三个方法
//Extend 是一个函数它描述问题中如何从一个节点扩展子节点它接受一个参数表示访问一个已经搜索到的节点返回一个表示新节点数组
//Beam 是一个函数它决定已知节点是否应该被剪枝它接受一个参数表示要检查节点返回true或者false 如果不需要剪枝它可以总是返回false
//Finish是一个函数它决定搜索到当前节点是否应该结束搜索。它接受一个参数表示要检查节点返回true或者false 如果要搜索所有可行解它可以总是返回false

function Search(Collection,Extend,Beam,Finish)
{
return function(node){
var openlist=new Collection();
openlist.put(node);
while(!openlist.empty()){
var current=openlist.get();
if(!Beam(current)){
var extended=Extend(current);
for(var i=0;i<extended.length;i++) {
if(Finish(extended[i]))
return extended[i];
openlist.put(extended[i]);
}
}
}
return null;
}
}
Search=Currying(Search);//将Search科里化。
function Stack()//实现了Collection接口的栈容器
{
var buf=new Array();
this.empty=function(){
return !buf.length;
}
this.get=function(){
return buf.pop.apply(buf,arguments);
}
this.put=function(){
return buf.push.apply(buf,arguments);
}
}
function Queue()//实现了Collection接口的队列容器
{
var buf=new Array();
this.empty=function(){
return !buf.length;
}
this.get=function(){
return buf.pop.apply(buf,arguments);
}
this.put=function(){
return buf.unshift.apply(buf,arguments);
}
}
function SortCollection(compare)//实现了Collection接口的排序结构
{
return function(){
var buf=new OrderArray(compare);
this.empty=function(){
return !buf.length;
}
this.get=function(){
return buf.pop.apply(buf,arguments);
}
this.put=function(){
return buf.insert.apply(buf,arguments);
}
}
}
var DepthFirstSearch=Search(Stack);//用栈做为openlist 深度优先搜索
var BreadFirstSearch=Search(Queue);//用队列做为openlist 广度优先搜索
var AStarSearch=Currying(function(compare,Extend,Beam,Finish)//使用估值函数的A*搜索。
{
return Search(new SortCollection(compare),Extend,Beam,Finish);
})

复制代码

链接中有两个附件

1，8皇后问题适用深度优先搜索和广度优先搜索
2，寻路使用AStar搜索和广度优先搜索

JavaScript二叉树
在JavaScript中使用数组对象实现二叉树的深度与广度搜索。

<script type="text/javascript">
var t = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19];

//下面这段深度优先搜索方法出自Aimingoo的【JavaScript语言精髓与编程实践】
var deepView = function(aTree,iNode){
(iNode in aTree) && (document.write(aTree[iNode]+'<br/>'),arguments.callee(aTree,2*iNode+1),arguments.callee(aTree,2*iNode+2))
}

//广度优先
var wideView = function(aTree,iNode){
var aRTree = aTree.slice(0),iRNode = iNode,iLevel = 1;
(iRNode in aRTree) && document.write(aRTree[iRNode]+'<br/>');
(function(){
      var iStart = iRNode*2+1,iEnd = iStart+Math.pow(2,iLevel);
      document.write(aRTree.slice(iStart,iEnd).join(',')+'<br/>');
      if(iEnd>=aRTree.length) return;
      iRNode = iStart,iLevel++,arguments.callee();
})()
}

document.write('<h3>二叉树深度优先</h3>');
//深度优先
deepView(t,0);

document.write('<h3>二叉树广度优先</h3>');
//广度优先
wideView(t,0);
</script>

javascript实现的二分查找法

[摘要]: 一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上，或者用到拼音...或者用到...... 不过值得深思的一个问题是，如果为了实现对拼音之类的二分查找.而经过如下流程是否值得： 1。对拼音排序，貌似代码量不小吧。 2。然后再二分查找。这又需要识别拼音的大小

一般二分都用到int[]型上.....在js中可能会更灵活的用到a-z上，或者用到拼音...或者用到......
不过值得深思的一个问题是，如果为了实现对拼音之类的二分查找.而经过如下流程是否值得：
1。对拼音排序，貌似代码量不小吧。
2。然后再二分查找。这又需要识别拼音的大小，貌似也不算太小吧。
找到结果的速度快了，可是别人下你的js文件速度慢多了，呵呵，到底舍弃谁。
下面的代码甚至可以10亿条，一样会很快找到，可是用遍例的模式创建那个数组。。。所以还是别尝试了。只是给个思路，下次我再来发个js的八皇后问题解决方案，呵呵算法很奇妙哦

var array = [];
var key = 482;
var number = 1000;

for(i=0;i<number;i++){
array.push(i);
}
//-->>
var time = new Date();
var a;
var left = 0;
var right= array.length;
while(left<=right){
var center=Math.floor((left+right)/2);
if(array[center] == key) a = center;
if(key < array[center]){
right = center - 1;
}else{
left = center + 1;
}
}
alert("二分查找法搜索的结果:"+a);
alert((new Date() - time)/1000);