所有可能的路径

Question

我目前正在为玩游戏点(链接)的人工智能工作。其目的是通过将颜色相似的点与一条线连接起来，以尽可能多地去除点。我已经翻过黑板，把每一组颜色相同的相邻点分组起来。这些组当前共享相同的高亮颜色(黑色)。例如，左上角的四个红色点形成一个单一的组，右上角的三个黄色点也是这样。

我需要计算每一个可能的路径通过这些团体之一。有人能想到一个好的算法吗？如何避免创建重复路径？

我听说在这种情况下稍微修改一下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;
}