java - 找到从 A 到 Z 的所有路径的有效算法？

Question

带有一组random inputs像这样(20k 行):

A B
U Z
B A
A C
Z A
K Z
A Q
D A
U K
P U
U P
B Y
Y R
Y U
C R
R Q
A D
Q Z

找出从 A 到 Z 的所有路径。

1. A - B - Y - R - Q - Z
2. A - B - Y - U - Z
3. A - C - R - Q - Z
4. A - Q - Z
5. A - B - Y - U - K - Z

一个位置在路径中不能出现多次，因此 A - B - Y - U - P - U - Z 无效。

位置被命名为 AAA 到 ZZZ(为简单起见，此处显示为 A - Z)，输入是随机的，可能有也可能没有位置 ABC，所有位置都可能是 XXX(不太可能)，或者有可能并非所有位置的路径都被“隔离”。

最初我认为这是未加权 shortest path problem 的变体，但我觉得它很不一样，我不确定那里的算法在这里如何应用。

我目前的解决方案是这样的:

1. 预处理列表，以便我们有一个 HashMap ，将位置(左)指向位置列表(右)

2. 创建一个 HashMap 来跟踪“访问过的位置”。创建一个列表来存储“找到的路径”。

3. 将 X(起始位置)存储到“访问过的位置” HashMap 。

4. 在第一个 hashmap 中搜索 X，(位置 A 将在 O(1) 时间内为我们提供 (B, C, Q))。

5. 对于每个找到的位置(B、C、Q)，检查它是否是最终目的地(Z)。如果是这样，将其存储在“找到的路径”列表中。否则，如果它不存在于“已访问的位置” HashMap 中，则现在以该位置为“X”返回到第 3 步。 (实际代码如下)

使用当前的解决方案，需要 永远 为 this provided data 映射从“BKI”到“SIN”的所有(不是最短的)可能路线.

我想知道是否有更有效(时间方面)的方式来做这件事。有谁知道找到从任意位置 A 到任意位置 Z 的所有路径的更好算法？

当前解决方案的实际代码:

import java.util.*;
import java.io.*;

public class Test {
    private static HashMap<String, List<String>> left_map_rights;

    public static void main(String args[]) throws Exception {
        left_map_rights = new HashMap<>();
        BufferedReader r = new BufferedReader(new FileReader("routes.text"));
        String line;
        HashMap<String, Void> lines = new HashMap<>();
        while ((line = r.readLine()) != null) {
            if (lines.containsKey(line)) { // ensure no duplicate lines
                continue;
            }
            lines.put(line, null);
            int space_location = line.indexOf(' ');
            String left = line.substring(0, space_location);
            String right = line.substring(space_location + 1);
            if(left.equals(right)){ // rejects entries whereby left = right
                continue;
            }
            List<String> rights = left_map_rights.get(left);
            if (rights == null) {
                rights = new ArrayList<String>();
                left_map_rights.put(left, rights);
            }
            rights.add(right);
        }
        r.close();
        System.out.println("start");
        List<List<String>> routes = GetAllRoutes("BKI", "SIN");
        System.out.println("end");
        for (List<String> route : routes) {
            System.out.println(route);
        }
    }

    public static List<List<String>> GetAllRoutes(String start, String end) {
        List<List<String>> routes = new ArrayList<>();
        List<String> rights = left_map_rights.get(start);
        if (rights != null) {
            for (String right : rights) {
                List<String> route = new ArrayList<>();
                route.add(start);
                route.add(right);
                Chain(routes, route, right, end);
            }
        }
        return routes;
    }

    public static void Chain(List<List<String>> routes, List<String> route, String right_most_currently, String end) {
        if (right_most_currently.equals(end)) {
            routes.add(route);
            return;
        }
        List<String> rights = left_map_rights.get(right_most_currently);
        if (rights != null) {
            for (String right : rights) {
                if (!route.contains(right)) {
                    List<String> new_route = new ArrayList<String>(route);
                    new_route.add(right);
                    Chain(routes, new_route, right, end);
                }
            }
        }
    }
}

Answer 1

据我了解您的问题，Dijkstras 算法不能按原样应用，因为每个定义的最短路径问题会在一组所有可能的路径中找到一条路径。你的任务是找到所有路径本身。

对 Dijkstras 算法的许多优化都涉及以更高成本切断搜索树。您将无法在搜索中删除这些部分，因为您需要所有结果。

我假设你的意思是所有路径不包括圆圈。

算法:

• 将网络泵入一个 26x26 boolean/整数的 2dim 数组。从到[i,j]。为现有链接设置 1/true。

• 从第一个节点开始跟踪所有后续节点(搜索链接为 1/true)。

• 将访问过的节点保存在某个结构(数组/列表)中。由于最大深度似乎是 26，这应该可以通过递归实现。

• 正如@soulcheck 在下面所写，您可能会考虑切断您已经访问过的路径。您可以在数组的每个元素中保留通往目的地的路径列表。相应调整分断条件。

• 休息时间

  • 访问结束节点(存储结果)
  • 访问之前访问过的节点时(圆圈)
  • 访问您已经找到所有到目的地的路径的节点，并将当前路径与来自该节点的所有现有路径合并。

在性能方面，我会投票反对使用 HashMap 和列表，而更喜欢静态结构。

嗯，在重新阅读问题时，我意识到节点的名称不能仅限于 A-Z。您正在编写大约 20k 行、26 个字母的内容，完全连接的 A-Z 网络需要的链接要少得多。也许你跳过递归和静态结构:)

好的，使用从 AAA 到 ZZZ 的有效名称，数组会变得太大。所以你最好也为网络创建一个动态结构。反问:关于性能，对于我的算法所需的较少填充数组的最佳数据结构是什么？我投票支持 2 暗淡的 ArrayList。有人吗？