java - java 的旅行路线

Question

我有非常基本的 Java 知识。我尝试了下面的问题，但在某些情况下失败了(我知道该程序肯定是不正确的)。有人可以帮我用 Java 解决这个问题吗？

将下表表达为静态结构，并编写一个函数find_routes(source,destination)来高效输出所有可能的路由。

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

例如: find_routes('Seattle', 'Florida') 的解决方案应该是 [Seattle -> Florida, Seattle -> LA -> 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;
                }
        }   
    }
    }
}

Answer 1

因为你的方法已经不适合 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"};

那么这当然是一个递归问题。所以你必须找到递归 anchor 。在继续阅读之前花点时间思考一下。

显然，当源与目标相同时，递归 anchor 就出现了。

因此，找到递归 anchor 后，您只需添加后续步骤即可。你把相应的目的地作为新的来源的想法已经是正确的方法了。 您不需要做的是保存后续步骤。

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

如果我们不在递归 anchor ，我们还必须检查循环。为了避免这些，我们可以只查看 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);
                    }
                }
            }
        }
    }

}

这绝对不是最有效的方法，但它应该会提示您如何做到这一点。