JavaScript 中的回溯，无法更新全局变量

Question

我正在尝试解决JavaScript中代码出现的第9天的问题。

我正在使用回溯来获取所有可能的路线，然后计算每条路线的成本。

我习惯于在PHP和C++等语言中进行回溯，但在JS中从未这样做过，因此我发现感谢google，您无法在PHP和C++中传递像&参数这样的可变参数。

我的目的是将 bestRoute 变量分配给最佳路由，因为这是问题的解决方案。

但是当我这样做时，在某些站点中使用 return，我得到一个未定义的变量错误，如下所示：

for (var i = 0 ; i < neighborsArray.length ; i++) {
                                           ^
TypeError: Cannot read property 'length' of undefined at getCostInNeighbors (/home/freinn/librosjavascript/advent_of_code/day9.js:117:40)
        at calculateCost (/home/freinn/librosjavascript/advent_of_code/day9.js:110:17)

这是我当前的代码，它不起作用，并且像第一个定义的那样打印 bestRoute。

"use strict";
function clone(obj) {
    // Handle the 3 simple types, and null or undefined
    if (null == obj || "object" != typeof obj) return obj;
    // Handle Date
    if (obj instanceof Date) {
        var copy = new Date();
        copy.setTime(obj.getTime());
        return copy;
    }
    // Handle Array
    if (obj instanceof Array) {
        var copy = [];
        for (var i = 0, len = obj.length; i < len; i++) {
            copy[i] = clone(obj[i]);
        }
        return copy;
    }
    // Handle Object
    if (obj instanceof Object) {
        var copy = {};
        for (var attr in obj) {
            if (obj.hasOwnProperty(attr)) {
                copy[attr] = clone(obj[attr]);
            }
        }
        return copy;
    }
    throw new Error("Unable to copy obj! Its type isn't supported.");
}
function generateGraphAsArray(input) {
    var lines = input.split("n");
    var getFromTo = /(.*?) to (.*?) = (d+)/;
    var graph = {};
    var matches = [];
    for (var i = 0 ; i < lines.length ; i++) {
        matches = getFromTo.exec(lines[i]);
        // console.log(matches[1], matches[2], matches[3]);
        var obj = {};
        obj['to'] = matches[2];
        obj['cost'] = matches[3];
        var clonated = clone(obj);
        if (!(matches[1] in graph)) {
            graph[matches[1]] = [];
        }
        graph[matches[1]].push(clonated);
        if (!(matches[2] in graph)) {
            graph[matches[2]] = [];
        }
        obj['to'] = matches[1];
        clonated = clone(obj);
        graph[matches[2]].push(clonated);
    }
    var keys = Object.keys(graph);
    var graphArray = [];
    var nodeList;
    // recuerda: en JS la funcion que no devuelve nada, devuelve algo, undefined
    // si no ponemos return en la funcion del map, dara undefined
    for (var prop in graph) {
        // esto es una clausura sana para poder usar keys
        nodeList = graph[prop].map(function(obj) {
            return nodeObjectToArray(keys, obj);
        });
        graphArray.push(nodeList);
    }
    return graphArray;
}
function nodeObjectToArray(keys, obj) {
    var array = new Array(keys.indexOf(obj.to), Number(obj.cost));
    return array;
}
function generateAllRoutes(numberOfNodes, graphArray) {
    var routes = [];
    for (var i = 0 ; i < numberOfNodes; i++) {
        var array = [i]
        routes.push(array);
    }
    var bestRoute = generateRangeWithoutUsed([], numberOfNodes);
    for (var i = 0 ; i < routes.length; i++) {
        bestRoute = generateRoutes(routes[i], numberOfNodes, bestRoute, graphArray);
    }
    console.log(bestRoute, calculateCost(bestRoute, graphArray));
}
function calculateCost(route, graphArray) {
    var limit = graphArray.length - 1;
    var cost = 0;
    for (var i = 0 ; i < limit ; i++) {
        cost += getCostInNeighbors(graphArray[route[i]], route[i+1]);
    }
    return cost;
}
function getCostInNeighbors(neighborsArray, neighbour) {
    for (var i = 0 ; i < neighborsArray.length ; i++) {
        if (neighborsArray[i][0] == neighbour) {
            return neighborsArray[i][1];
        }
    }
}
function generateRoutes(currentRoute, numberOfNodes, bestRoute, graphArray) {
    if (currentRoute.length == numberOfNodes) {
        var currentRouteCost = calculateCost(currentRoute, graphArray);
        console.log(currentRouteCost);
        if (currentRouteCost < calculateCost(bestRoute, graphArray)) {
            return currentRoute;
        } else {
            return bestRoute;
        }
    } else {
        var possibleNextNodes = generateRangeWithoutUsed(currentRoute, numberOfNodes);
        for (var i = 0 ; i < possibleNextNodes.length ; i++) {
            currentRoute.push(possibleNextNodes[i]);
            generateRoutes(currentRoute, numberOfNodes, bestRoute, graphArray);
            currentRoute.splice(-1, 1); // remove the last element
        }
    }
}
function generateRangeWithoutUsed(used, numberOfNodes) {
    var rangeWithoutUsed = [];
    for (var i = 0 ; i < numberOfNodes ; i++) {
        if (!existInArray(i, used)) {
            rangeWithoutUsed.push(i);
        }
    }
    return rangeWithoutUsed;
}
function existInArray(element, array) {
    for (var i = 0 ; i < array.length ; i++) {
        if (array[i] == element) {
            return true;
        }
    }
    return false;
}
var input = "Faerun to Norrath = 129nFaerun to Tristram = 58nFaerun to AlphaCentauri = 13nFaerun to Arbre = 24nFaerun to Snowdin = 60nFaerun to Tambi = 71nFaerun to Straylight = 67nNorrath to Tristram = 142nNorrath to AlphaCentauri = 15nNorrath to Arbre = 135nNorrath to Snowdin = 75nNorrath to Tambi = 82nNorrath to Straylight = 54nTristram to AlphaCentauri = 118nTristram to Arbre = 122nTristram to Snowdin = 103nTristram to Tambi = 49nTristram to Straylight = 97nAlphaCentauri to Arbre = 116nAlphaCentauri to Snowdin = 12nAlphaCentauri to Tambi = 18nAlphaCentauri to Straylight = 91nArbre to Snowdin = 129nArbre to Tambi = 53nArbre to Straylight = 40nSnowdin to Tambi = 15nSnowdin to Straylight = 99nTambi to Straylight = 70";
// var myInput = "a to b = 1na to c = 2nb to d = 7nc to d = 1nc to e = 3nd to f = 2ne to f = 5";
var graphArray = generateGraphAsArray(input);
generateAllRoutes(graphArray.length, graphArray);

Answer 1

在 generateRoutes 中，如果你的 else 情况发生，函数返回 null（因为没有 return 语句），wicht 将 bestRoute 设置为 null，下次调用 calculateCost 时会导致错误