0

我有一个学校作业，我的方法需要找到从给定节点开始的每条可能的路径。现在的问题是，我的方法只找到最长的路径，然后停止创建新路径，我似乎无法弄清楚它为什么这样做（可能在 Java 中太缺乏经验）。我正在使用char[3][3]该方法需要遍历的数组。基本的想法是可行的，但不是所有的路径。

我写的方法：

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            currentFullPath.add(coord);
            if (!(paths.contains(currentFullPath))) {
                paths.add(currentFullPath);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, currentFullPath); 
            }
        }
    }
}

方法调用：

computeAllPaths(new Point(0, 0), new ArrayList<Point>());

声明：

private List<ArrayList<Point>> paths = new LinkedList<ArrayList<Point>>();

3x3 数组的一些输出：

    Current paths size: 8

(0.0,0.0)(1.0,0.0)(0.0,1.0)(0.0,2.0)(1.0,2.0)(2.0,2.0)(2.0,1.0)(2.0,0.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(1.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(1.0,1.0)(0.0,2.0)(0.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)
(0.0,0.0)(1.0,0.0)(2.0,0.0)(2.0,1.0)(2.0,2.0)(1.0,2.0)(0.0,2.0)(0.0,1.0)(1.0,1.0)

我尝试了许多类型的列表和集合，但似乎没有人在工作，我不知道为什么，有人可以帮我解决这个问题吗？

板子示例：

N | N | A
R | E | TN
| T | ○

允许的动作：假设我们从 R (1,0) 开始，那么允许的动作将是：

  • N(0,0)
  • N(0,1)
  • E(1,1)
  • T(2,1)
  • N(2,0) 所以基本上它是直接邻居。
4

1 回答 1

0

所以我自己不是 Java 编码员，但你做的事情很少。

随着currentFullPath你添加一个指向它的指针paths，你应该添加一个指向它的副本的指针，所以猜猜会发生什么。将其添加到paths您之后，您将进一步更改它。基本上要调试它，只需打印出paths内部循环的每一遍。此外，如果您不这样做，您应该currentFullPath为每个coordin创建副本，您最终会将所有邻居添加到同一路径。neighbouringCoords

请记住，Java 总是将指针传递给对象。

编辑：我看到仍然有很多废话飞来飞去。试试这个：

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            if (!(paths.contains(newList))) {
                paths.add(newList);
                //start over again with same coord
                computeAllPaths(currentFullPath.get(0), new ArrayList<Point>()); 
            } else {
                //try to add another coord
                computeAllPaths(coord, newList); 
            }
        }
    }
}

显示结果。

编辑2：这会快很多。

private void computeAllPaths(Point current, ArrayList<Point> currentFullPath) {

    if (currentFullPath.isEmpty()) {
        currentFullPath.add(current);
    }

    for (Point coord : neighbouringCoords.get(current)) {
        if (!(currentFullPath.contains(coord))) {
            ArrayList<Point> newList = new ArrayList<Point>(currentFullPath);
            newList.add(coord);
            paths.add(newList);                           
            computeAllPaths(coord, new ArrayList<Point>(newList));            
        }
    }
}
于 2013-03-02T11:29:13.317 回答