java - 所有可能的路径

Question

我目前正在开发用于玩 Dots (link) 游戏的 AI。目标是通过用一条线连接颜色相似的点来移除尽可能多的点。我浏览了棋盘并将每组相邻的点用相同的颜色分组。这些组目前都共享相同的突出显示颜色(黑色)。因此，例如，左上角的四个红点形成一个单独的组，右上角的三个黄点也是如此。

我需要计算通过这些组之一的每条可能路径。谁能想出一个好的算法？如何避免创建重复路径？

我听说在这种情况下稍微修改一下 DFS 会很好。但是，允许路径在节点处交叉，但不能重用边。如何相应地修改 DFS？

Answer 1

这里有一些伪代码可以帮助您入门。这就是我可能会做的。使用边而不是节点可以巧妙地解决交叉路径的情况，但检索边比节点更困难。您需要将边索引映射到节点索引。

您将获得每条路径两次，因为一条路径可以从两个方向遍历。 如果点组变大，请考虑修剪最不感兴趣的路径。内存需求呈指数增长 4^n，其中 n 是组中的点数。我想不出在不允许重复的情况下添加不完整路径的好方法，但也许您对提早结束的路径不感兴趣？

private LinkedList<Edge> recurse(LinkedList<Edge> path) {
    Edge last = path.getLast();
    Edge right = <get Edge to the right of last>;
    Edge bottom = <get Edge below last>;
    Edge left = <get Edge to the left of last>;
    Edge top = <get Edge above last>;
    if( right && !path.contains(right) ) {
        LinkedList<Edge> ps = path.clone();  // NOTE: check if the built-in clone() function does a shallow copy
        ps.addLast( right );
        paths.add( recurse(ps) );
    }
    if( bottom && !path.contains(bottom) ) {
        ...
    }
    if( left && !path.contains(left) ) {
        ...
    }
    if( top && !path.contains(top) ) {
        ...
    }
    return path;
}