java - Java编写路由程序、递归难点

Question

所以我正在编写一个程序，将一个人从地铁系统的一个车站引导到另一个车站。想法如下:

• 到达起始站并找出该站所在的线路。然后检查它是否与目标站点在同一行
• 如果是则打印所需的路径。这部分确实有效，我已经测试过了。
• 如果没有，则在每条线上上下移动一站并进行相同的检查。

它给了我一个我无法解决的堆栈溢出。尝试调试无果。

public ArrayList<Station> findRoutesBetween(Station start, Station target) {
    ArrayList<Station> path = new ArrayList<Station>();

    for (Route route : findRoutes(start)) {
        ArrayList<Station> stops = route.getStops();
        boolean sameRoute = findRoutes(target).contains(route);
        int stopIdstart = stops.indexOf(start);
        int stopIdtarget = stops.indexOf(target);
        if (sameRoute && stops.contains(start)) {
            if (stopIdtarget > stopIdstart) {
                path.addAll((stops.subList(stopIdstart, stopIdtarget + 1)));
                return path;
            } else {
                List<Station> temp = stops.subList(stopIdstart, stopIdtarget + 1);
                Collections.reverse(temp);
                path.addAll(temp);
                return path;
            }
        } else {
            if (stopIdstart != stops.size() - 1) {
                System.out.println("hh");
                ArrayList<Station> t = findRoutesBetween(stops.get(stopIdstart + 1), target);
                System.out.println(t.toString());
            }
            if (stopIdstart != 0) {
                System.out.println("hh");
                ArrayList<Station> t = findRoutesBetween(stops.get(stopIdstart - 1), target);
                System.out.println(t.toString());
            }
        }

    }
    return path;
}

函数 findroutes() 仅返回该站点所在的所有线路。

Answer 1

您的实现不会忽略您已经检查或继续的电台。这意味着在某个时刻，您可能会通过给定的路线从 A 站前往 B 站。然后，当您到达 B 站时，您检查所有可能的站点并再次看到 A 站。然后你又回到A站，重新开始，再次找到B站。现在，您在无休止的递归方法调用中在这些站点之间来回跳转，直到收到 StackOverflowError。

保留您已经检查过的电台列表，并且当它们在列表中时不要再次检查它们。所以你会得到类似的东西:

Okay, I'm at station K and see the stations R, G, W, Z, C, I and L based on the routes available. However, I skip the stations W, Z and C because I was already there. So lets check only the stations R, G, I and L next...

出于调试目的，您可以打印进入方法的参数(或来自 Station 对象的一些数据，例如站名称)。这样您可能会注意到，您会看到相同的电台在您的方法中重复出现。