廣度優先搜索使用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

回答

相關問題