我目前正在开发一个用于玩游戏Dots的人工智能（链接）。游戏的目标是通过用线连接颜色相同的点来移除尽可能多的点。我已经遍历了棋盘，并将每组相邻且颜色相同的点进行了分组。目前所有组都使用相同的突出显示颜色（黑色）。例如，左上角的四个红色点形成了一个组，右上角的三个黄色点也形成了一个组。

我需要计算通过这些组中的每一个的所有可能路径。谁能想到一个好的算法？我怎样才能避免创建重复的路径？

我听说在这种情况下稍微修改后的深度优先搜索（DFS）会很好。然而，路径允许在节点处交叉，但不能重复使用边。我该如何相应地修改DFS？

回答：

这里有一些伪代码来帮助你开始。这是我可能会采用的方法。使用边而不是节点可以巧妙地解决路径交叉的问题，但获取边比获取节点更困难。你需要将边的索引映射到节点的索引上。

你会得到每条路径两次，因为一条路径可以从两个方向遍历。如果点组变得很大，考虑修剪最不重要的路径。内存需求随着组中点的数量n的增加以4^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();  // 注意：检查内置的clone()函数是否进行浅拷贝        ps.addLast( right );        paths.add( recurse(ps) );    }    if( bottom && !path.contains(bottom) ) {        ...    }    if( left && !path.contains(left) ) {        ...    }    if( top && !path.contains(top) ) {        ...    }    return path;}