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

Question

使用一组这样的随机输入(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(不太可能),或者可能不存在所有位置的可能路径都是"孤立的".

最初我认为这是未加权最短路径问题的变体,但我觉得它有点不同,我不确定这里的算法是如何应用的.

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

1. 预处理列表,以便我们有一个将位置(左)指向位置列表的哈希图(右)

2. 创建一个hashmap来跟踪"访问过的位置".创建一个列表来存储"找到的路径".

3. 将X(起始位置)存储到"访问位置"散列映射.

4. 在第一个hashmap中搜索X,(位置A将在O(1)时间内给出(B,C,Q)).

5. 对于每个找到的位置(B,C,Q),检查它是否是最终目的地(Z).如果存储,则将其存储在"找到的路径"列表中.否则,如果"访问位置"散列映射中尚不存在,则现在重新启动到步骤3,该位置为"X".(下面的实际代码)

利用这种当前的解决方案,对于所提供的数据,将所有(不是最短的)可能路线从"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算法的许多优化涉及以更高的成本切断搜索树.您将无法在搜索中切断这些部分,因为您需要所有结果.

我假设你指的是除圆圈之外的所有路径.

算法:

• 将网络泵入2xim数组26x26的布尔/整数.的FromTo [I,J].为现有链接设置1/true.

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

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

• 正如@soulcheck在下面写的那样,你可以考虑削减你已经看过的路径.您可以在阵列的每个元素中保留指向目标的路径列表.相应地调整破坏条件.

• 休息的时候

  • 访问结束节点(存储结果)
  • 访问之前访问过的节点时(圆圈)
  • 访问已找到目的地所有路径的节点,并将当前路径与该节点中的所有现有路径合并.

性能方面,我投票反对使用散列图和列表,而不喜欢静态结构.

嗯,在重读这个问题时,我意识到节点的名称不能仅限于AZ.你正在写一些关于20k行的信息,有26个字母,一个完全连接的AZ网络需要更少的链接.也许你跳过递归和静态结构:)

好的,从AAA到ZZZ的有效名称,数组会变得太大.因此,您最好为网络创建动态结构.反问题:关于性能,我的算法需要的popuplate数组的最佳数据结构是什么？我投票支持2 dim ArrayList.任何人？

Answer 2

你提出的是DFS的一个方案,只有回溯.这是正确的,除非你想允许循环路径(你没有指定你是否这样做).

但是有两个陷阱.

1. 您必须密切关注当前路径上已访问过的节点(以消除周期)
2. 您必须知道如何在回溯时选择下一个节点,这样当您在当前路径上访问时,您不会在图中的同一子树上下降.

伪代码或多或少如下:

getPaths(A, current_path) :
    if (A is destination node): return [current_path]
    for B = next-not-visited-neighbor(A) : 
        if (not B already on current path) 
            result = result + getPaths(B, current_path + B)
    return result 

 list_of_paths =  getPaths(A, [A])

这几乎就是你所说的.

但要小心,因为在完整图中查找所有路径都是非常耗时的时间和内存.

编辑 为了澄清,该算法在最坏情况下具有Ω(n!)时间复杂度,因为它必须列出大小为n的完整图形中从一个顶点到另一个顶点的所有路径,并且至少有(n-2)!形式的路径<A,除A和Z之外的所有节点的排列,Z>.如果仅列出结果将花费更多,就无法使其变得更好.