无限递归 java 问题-解网

问：

我正在尝试解决一个问题，但似乎无法解决这个问题。我尝试创建列表和集合来跟踪访问过的城镇，然后在已经访问过时跳过，但到目前为止，我的实现都没有奏效。

问题是，给定一个带有 AB5 等路线的图表，它意味着从城镇 A 到 B 的路线，距离为 5。现在给定输入 AB5、BC4、CD8、DC8、DE6、AD5、CE2、EB3、AE7，我正在尝试找到从 B 到 B 的最短路径。答案应该是 9。

我已经看到问题存在，因为递归检查路径 C 到 D，然后检查所有 D 的路径。D 包含一条通往 C 的路由，然后它转到 C，这就是无限递归发生的地方。如何实现检查以确保它不会无限地绕过 C 到 D 和 D 到 C 的路由。

这是我针对这个问题的编码函数：

public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step) {
        if (currentTown == endTown && step != 0) {
            return distance;
        }

        int shortestDistance = Integer.MAX_VALUE;
        for (char nextTown : graph.get(currentTown).keySet()) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1));
        }
        return shortestDistance;
    }

Java 递归循环

/*
Set<Character> visited parameter: keeps track of the nodes that have already been visited.
So, before checking a node the function checks if it's in the visited set. 
If it is, the function skips it. If it's not, the function adds it to the visited set and checks it.
*/
public int shortestDistance(char startTown, char endTown, char currentTown, int distance, int step, Set<Character> visited) {
    if (currentTown == endTown && step != 0) {
        return distance;
    }

    visited.add(currentTown);

    int shortestDistance = Integer.MAX_VALUE;
    for (char nextTown : graph.get(currentTown).keySet()) {
        if (!visited.contains(nextTown)) {
            shortestDistance = Math.min(shortestDistance, shortestDistance(startTown, endTown, nextTown,
                    distance + graph.get(currentTown).get(nextTown), step + 1, visited));
        }
    }

    visited.remove(currentTown);

    return shortestDistance;
}

我现在让它工作了。我必须添加这个条件：if （currentTown == endTown && step == 0） { } else { visited.add（currentTown）; } 并且出于某种原因，它才能正常工作。你认为你可以向我解释为什么这有效，为什么我不能只写if（currentTown == endTown && step ！= 0）{ visited.add（currentTown）;}

1赞 mandy8055 10/22/2023

@Wragnam，该条件之所以有效，是因为它正确处理了起始节点与结束节点相同的情况。在这种情况下，该函数会立即返回距离，因为从起始节点到自身的最短路径为 0。你也可以写第二个，但你需要在之后调整一些条件，这在调试时会更有意义。但前者可以。(currentTown == endTown && step == 0) { }

1赞 Wragnam 10/22/2023

非常感谢，谢谢！！

1赞 Dawood ibn Kareem 10/22/2023

@Wragnam - “非常感谢，谢谢”按钮是答案旁边的灰色小勾号，当您单击它时，它会变成绿色。这会奖励写答案的人;但更重要的是，它向所有人发出信号，表明您的问题已得到充分回答，因此他们可以继续前进并帮助其他人。

上一个：在 R Shiny 中使用观察的无限循环

下一个：dbus-cxx 阻塞主线程，直到断开 DBUS 连接

无限递归 java 问题

Infinite recursion java issue

评论

评论