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

Question

我正在尝试解决 javascript 中 day 9 of the advent of code 的问题。

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

我习惯用 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 = 129\nFaerun to Tristram = 58\nFaerun to AlphaCentauri = 13\nFaerun to Arbre = 24\nFaerun to Snowdin = 60\nFaerun to Tambi = 71\nFaerun to Straylight = 67\nNorrath to Tristram = 142\nNorrath to AlphaCentauri = 15\nNorrath to Arbre = 135\nNorrath to Snowdin = 75\nNorrath to Tambi = 82\nNorrath to Straylight = 54\nTristram to AlphaCentauri = 118\nTristram to Arbre = 122\nTristram to Snowdin = 103\nTristram to Tambi = 49\nTristram to Straylight = 97\nAlphaCentauri to Arbre = 116\nAlphaCentauri to Snowdin = 12\nAlphaCentauri to Tambi = 18\nAlphaCentauri to Straylight = 91\nArbre to Snowdin = 129\nArbre to Tambi = 53\nArbre to Straylight = 40\nSnowdin to Tambi = 15\nSnowdin to Straylight = 99\nTambi to Straylight = 70";
// var myInput = "a to b = 1\na to c = 2\nb to d = 7\nc to d = 1\nc to e = 3\nd to f = 2\ne to f = 5";

var graphArray = generateGraphAsArray(input);
generateAllRoutes(graphArray.length, graphArray);

Answer 1

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