广度优先搜索使用Javascript

function BFS_search(data, start, ende){ 
    var queue = new Array(); 
    var steps = 0; 
    for(var x=0; x<data.Adjazenzen.length-1; x++){ //push start Element in Queue 
     if(data.Adjazenzen[x] == start){ 
      queue.push(data.Adjazenzen[x]); 
      steps++; 
      break; 
     } 
    } 

    while(queue.length != 0) { 
     var t = queue.pop(); 
     if(t.Von == ende) { 
      return t.Von; 
     } 
     if(t.Nach == ende){ 
      return t.Nach; 
     } 
     else{ 
      queue.push(data.Adjazenzen[0]); 
      data.Adjazenzen.shift(); 
      steps++; 
      break; 
     } 
    } 
    return "keine Ergebnis"; 
}

此代码段应该计算来自给定JSON对象的两点之间的最佳路线，并且还会在开始和结束节点之间添加所有点。基本上它应该是一个使用BFS的导航系统。广度优先搜索使用Javascript

JSON对象看起来是这样的：

{"Adjazenzen":[ 
{"Von":"A1.02","Nach":"G-A3-1","X":"5778","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.04","Nach":"G-A3-1","X":"5025","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.05","Nach":"G-A3-1","X":"4212","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.06","Nach":"G-A3-1","X":"3016","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.07","Nach":"G-A3-1","X":"2354","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.08","Nach":"G-A3-1","X":"1856","Y":"223","Z":"3","Treppe":"1","Gebaeude":"A","Level":"0"}, 
    {"Von":"A1.12","Nach":"G-A3-1","X":"1313","Y":"223","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"B1.01","Nach":"G-B3-1","X":"6572","Y":"223","Z":"3","Treppe":"1","Gebaeude":"B","Level":"0"}, 
    {"Von":"G-A3-1","Nach":"G-A3-2","X":"906","Y":"223","Z":"3","Treppe":{},"Gebaeude":{},"Level":{}}, 
    {"Von":"G-A3-1","Nach":"B1.01","X":"6572","Y":"223","Z":"3","Treppe":"1","Gebaeude":"B","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"A1.14","X":"1066","Y":"1333","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"G-A3-3","X":"1444","Y":"4016","Z":"3","Treppe":{},"Gebaeude":{},"Level":{}}, 
    {"Von":"G-A3-2","Nach":"A1.15","X":"1207","Y":"2340","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"A1.18","X":"1444","Y":"4016","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"A1.16","X":"1327","Y":"3188","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"A1.13","X":"933","Y":"383","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-2","Nach":"A1.17","X":"1425","Y":"3884","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-3","Nach":"A1.19","X":"2691","Y":"3977","Z":"3","Treppe":"1","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-3","Nach":"A1.22","X":"2946","Y":"3969","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-3","Nach":"A1.23","X":"2946","Y":"3969","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}, 
    {"Von":"G-A3-3","Nach":"A1.20","X":"1990","Y":"4002","Z":"3","Treppe":"0","Gebaeude":"A","Level":"0"}]}

可以忽略，除了冯（从）和胆碱（要）的一切。问题是，我的BFS不是100％的工作，我不知道如何解决它。

一个例子：如果你想从A1.04来计算A1.15应该加上： A1.04，G-A3-1，G-A3-2，A1.15

而且如果你想从A1.04到A1.20： A1.04，G-A3-1，G-A3-2，G-A3-3，A1.20

我希望你能帮我解决这个问题。

来源

2013-04-26 Daniel Schott

'Adjazenzen'是否应该是一个邻接表？ – 2013-04-26 20:41:37

是的。节点是导航点。 – 2013-04-26 20:53:37

@ user2325235不应该'data.Adjazenzen [x] == start'是'data.Adjazenzen [x] .Von === start'？ – 2013-04-26 20:58:58

我注意到的第一件事是，queue.push(...)和queue.pop()将无法正常工作了您的预期，因为你有那么什么是堆栈，这意味着你正在做一个深度负一搜索，而不是一个广度 - 第一次搜索。

回想一下队列是一个FIFO容器。因此，使用queue.push(...)（它将一个元素添加到数组的末尾）和queue.shift()（它从阵列的前面删除一个元素）。基本上，shift()类似于队列上的dequeue()操作。

来源

2013-04-26 20:47:17

广度优先搜索使用Javascript

回答

相关问题