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

Question

我是一个相当 beginner/novice JavaScript 的编码员，没有太多 CS/math 经验，试图编写一个基于网络的游戏的一部分来检查 "longest road"跨越所有可能的路径，例如卡坦岛最长的道路得分。

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

不过，我的代码不太行得通；在遇到十字路口或其他变化时，它似乎实际上并没有 walk/check 所有可能的路径。

我对 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

我居然弄明白是怎么回事了！我仍然相当肯定这根本不是最佳解决方案，但它现在完全按照它应该做的 - 走所有有效路径，然后 return 一个包含它走过的最长路径的数组。这是最终代码：

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;
}

感谢提供thoughts/suggestions的人！

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

Iterative depth-first search to find longest path in JavaScript?

javascript

iteration

stack

maze

depth-first-search