java - Java中的旅行路线

我对Java有非常基本的了解。我尝试以下问题，但在某些情况下失败（我知道该程序肯定是错误的）。有人可以帮我解决Java中的问题吗？

将下表表示为静态结构，并编写一个函数find_routes（源，目标），该函数可有效输出所有可能的路由。

**Source**      **Destination**
Seattle         LA
LA              Florida
LA              Maine
Florida         Seattle
Seattle         Florida

例如：find_routes（'Seattle'，'Florida'）的解决方案应为[西雅图->佛罗里达，西雅图->洛杉矶->佛罗里达]

我尝试如下，但更改目的地时失败：

public class FindPossibleRoutes {
    static boolean nextItr=true;
    public static void main(String rgs[])
{
        String[] source={"Seattle","LA","LA","Florida","Seattle"};
        String[] dest={"LA","Florida","Maine","Seattle","Florida"};
        find_routes("Seattle", "Florida",source,dest);
    }
    public static void find_routes(String s, String d, String[] sa, String[] da) {
        for(int i=0;i<sa.length;i++)
        {
        if(sa[i].equals(s)&&nextItr==true)
        {
            System.out.println(s+"-->"+da[i]);
            if(!(da[i].equals(d)))
            {
                find_routes(da[i],d,sa,da);
            }
            else {
                   nextItr=false;
                   break;
                }
        }
    }
    }
}

最佳答案

由于您的方法已经不适合find_routes(source, destination)，因此我认为可以添加另一个参数find_routes(source, destination, currentRoute)。

首先，您必须定义问题中所写的“静态结构”。那将是这样的：

private static String[] sourceArray      = {"Seattle", "LA",      "LA",    "Florida", "Seattle"};
private static String[] destinationArray = {"LA",      "Florida", "Maine", "Seattle", "Florida"};

那么，这当然是一个递归问题。因此，您必须找到递归锚点。在继续阅读之前，请花一点时间考虑一下。


   当源与目标相同时，显然是递归锚点。


因此，在找到递归锚点之后，您只需添加后续步骤。您关于将相应的目的地作为新来源的想法已经是正确的方法。
您不要做的就是保存这些后续步骤。

为此，我使用第三个参数：currentRoute。它被初始化为一个空列表，并始终与当前节点一起扩展。如果最终到达递归锚点，则可以将当前路线添加到路线列表中。

如果我们不在递归锚点，我们还必须检查周期。为了避免这种情况，如果当前节点已经在内部，我们可以只查看currentRoute。请注意，对于庞大的数据集，您现在仍然可以达到堆栈数上限，因此需要一些其他的帮助器（例如，切入深度）。

package sto;

import java.util.ArrayList;

public class PathFinding {
    private static ArrayList<ArrayList<String>> routes = new ArrayList<ArrayList<String>>();
    private static String[] sourceArray      = {"Seattle", "LA",      "LA",    "Florida", "Seattle"};
    private static String[] destinationArray = {"LA",      "Florida", "Maine", "Seattle", "Florida"};

    public static void main(String rgs[])
    {
        find_routes("Seattle", "Maine", new ArrayList<String>());
        for(ArrayList<String> route : routes) {
            for(String node : route) {
                System.out.print(node + ", ");
            }
            System.out.println();
        }
    }

    private static void find_routes(String source, String destination, ArrayList<String> currentRoute) {
        // copy current route and add current node
        ArrayList<String> newRoute = new ArrayList<String>();
        newRoute.addAll(currentRoute);
        newRoute.add(source);
        // recursion anchor: source is destination, so route is finished and can be added to our routes
        if(source.equals(destination)) {
            routes.add(newRoute);
        } else {
            // check all possibilities for other routes
            for(int i = 0; i < sourceArray.length; ++i) {
                if(source.equals(sourceArray[i])) {
                    // if node is already in our route: cycle, i.e. no solution or no optimal solution
                    if(!currentRoute.contains(source)) {
                        find_routes(destinationArray[i], destination, newRoute);
                    }
                }
            }
        }
    }

}

这绝对不是最有效的方法，但是应该为您提供一个提示。