3 
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 オブジェクトから 2 つのポイント間の最適なルートを計算し、開始ノードと終了ノードの間のすべてのポイントも追加する必要があります。基本的には、BFS を使用したナビゲーション システムである必要があります。

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"}]}

Von (From) と Nach (To) 以外はすべて無視できます。問題は、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

この問題の解決にご協力いただければ幸いです。

4

1 に答える 1

2

私が最初に気付くのは、queue.push(...)あなたqueue.pop()が期待しているように機能しないということです。なぜなら、あなたが持っているのはスタックであるためです。つまり、幅優先検索ではなく深さ優先検索を行っているからです。

キューは FIFO コンテナーであることを思い出してください。したがって、queue.push(...)(配列の末尾に要素を追加する) とqueue.shift()(配列の先頭から要素を削除する) を使用します。基本的に、キューshift()に対する操作に似ています。dequeue()

于 2013-04-26T20:47:17.843 に答える