迭代深度优先搜索以在JavaScript中找到最长路径？

Question

我是一位相当初学者/新手的JavaScript编码人员，没有太多的CS /数学经验，他试图对基于网络的游戏的一部分进行编程，以检查所有可能路径上的“最长的道路”，例如卡坦岛最长的公路得分。

我已经尝试过使用堆栈进行深度优先迭代搜索的可能错误的实现方式来执行此操作。它应该走每条可能的路径，然后在到达死胡同时，检查当前路径是否比先前的最长​​路径更长，如果覆盖，则将其覆盖。

不过，我的代码不太有效；碰到交叉路口或其他变化时，似乎并没有实际走过/检查所有可能的路径。

我已经对DFS和这些算法进行了各种各样的研究，并且花了非常艰苦的时间来试图解决它；这是我最接近可行的方法。我确信可以通过递归或类似方法使代码更优雅，但是现在我只想了解为什么我在这里编写的代码不起作用。

下面的相关代码。我确信它在很多方面都是一团糟，但希望至少函数名称之类的东西足够清楚，以至于足以弄清最终出了什么问题：

function walkAllPaths(node, network, t) {
    var stack = [ node ];
    var path = new Array();
    var visited = new Array();

    while (stack.length) {
        var curr = stack.pop();
        visited.push(curr);

        var moveNorth = myNeighbor(curr, "north");
        var moveSouth = myNeighbor(curr, "south");
        var moveWest = myNeighbor(curr, "west");
        var moveEast = myNeighbor(curr, "east");

        if (isValidMove(network, visited, t, moveNorth)) { stack.push(moveNorth); }
        else if (isValidMove(network, visited, t, moveWest)) { stack.push(moveWest); }
        else if (isValidMove(network, visited, t, moveSouth)) { stack.push(moveSouth); }
        else if (isValidMove(network, visited, t, moveEast)) { stack.push(moveEast); }

        else {
            if (visited.length > path.length) {
                path.length = 0;
                for (var i = 0; i < visited.length; i++) {
                    path.push(visited[i]);
                }
            }
            visited.pop();
        }
        console.log(visited);
    }

    return path;
}

Answer 1

我实际上设法弄清楚发生了什么！我仍然很肯定这不是一个最佳解决方案，但是它现在可以按照预期的方式运行-遍历所有有效路径，然后返回包含其所走最长路径的数组。这是最终的代码：

function walkAllPaths(node, network, t) {
    var stack = [ node ];
    var path = [];
    var visited = [];
    var longPath = [];

    while (stack.length) {
        var curr = stack.pop();

        visited.push(curr);
        if (curr !== path[path.length - 1]) { path.push(curr); }

        var moveNorth = myNeighbor(curr, "north");
        var moveSouth = myNeighbor(curr, "south");
        var moveWest = myNeighbor(curr, "west");
        var moveEast = myNeighbor(curr, "east");

        if (isValidMove(network, visited, t, moveNorth)) { stack.push(moveNorth); }
        else if (isValidMove(network, visited, t, moveWest)) { stack.push(moveWest); }
        else if (isValidMove(network, visited, t, moveSouth)) { stack.push(moveSouth); }
        else if (isValidMove(network, visited, t, moveEast)) { stack.push(moveEast); }
        else {
            if (path.length > longPath.length) {
                longPath.length = 0;
                for (var i = 0; i < path.length; i++) {
                    longPath.push(path[i]);
                }
            }
            path.pop();
            if (path.length) { stack.push(path[path.length - 1]); }
        }
    }

    return longPath;
}

感谢那些提供想法/建议的人！