如何在回溯期间打印路径？

Question

我目前正在开发一个回溯程序，并被要求打印结果的路径。这是一个例子：

假设我们有一个加权图，由邻接表 g 表示，

g = {
    "A": {"B": 6, "D": 1},
    "B": {"A": 6, "C": 5, "D": 2, "E": 2},
    "D": {"A": 1, "B": 2, "E": 2},
    "E": {"B": 2, "C": 5, "D": 2},
    "C": {"B": 5, "E": 5}
}

连同起始节点“A”和目标节点“C”，我们的目标是找到边权重与其路径的乘积的最大值。对于这个例子，我们应该找到一条路径 A -> B -> D -> E -> C，边的乘积 = 6 * 2 * 2 * 5 = 120。我已经实现了一个回溯程序来找到 maxProduct，但是我找不到将路径存储在 class 变量 List<String> path 中的方法，有人可以帮我完成存储的实现吗List<String> path 的路径下面是我的回溯实现：

import java.util.*;

public class Test {
    static final String START = "A";
    static final String TARGET = "C";
    List<String> path = new ArrayList<>();
    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = getSimplerStaticData();
        System.out.println(getMaximumPathProduct(graph, START, TARGET));
    }

    private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
        Set<String> seen = new HashSet<>();
        seen.add(start);
        return dfs(start, target, seen, graph, new LinkedList<>());
    }

    private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph, List<String> subPath) {
        if(target.equals(current)) {
            return 1;
        }

        int res = 0;
        Map<String, Integer> neighbors = graph.get(current);
        for(String neighbor: neighbors.keySet()) {
            if(!seen.contains(neighbor)) {
                seen.add(neighbor);
                int distance = neighbors.get(neighbor);
                res = Math.max(res, distance * dfs(neighbor, target, seen, graph, subPath));
                seen.remove(neighbor);
            }
        }

        return res;
    }

    private static Map<String, Map<String, Integer>> getSimplerStaticData() {
        Map<String, Map<String, Integer>> res = new HashMap<>();
        Map<String, Integer> value1 = new HashMap<>();
        value1.put("B", 6);
        value1.put("D", 1);
        res.put("A", value1);

        Map<String, Integer> value2 = new HashMap<>();
        value2.put("A", 6);
        value2.put("D", 2);
        value2.put("E", 2);
        value2.put("C", 5);
        res.put("B", value2);

        Map<String, Integer> value3 = new HashMap<>();
        value3.put("B", 5);
        value3.put("E", 5);
        res.put("C", value3);

        Map<String, Integer> value4 = new HashMap<>();
        value4.put("A", 1);
        value4.put("B", 2);
        value4.put("E", 2);
        res.put("D", value4);

        Map<String, Integer> value5 = new HashMap<>();
        value5.put("B", 2);
        value5.put("C", 5);
        value5.put("D", 2);
        res.put("E", value5);

        return res;
    }
}

Answer 1

这是你想要实现的原型（我还没有在各种情况下进行测试，也没有尝试优化它，但它可能会帮助你开始）：

import java.util.*;

public class Test {
    static final String START = "A";
    static final String TARGET = "C";
    static List<String> path = new ArrayList<>();

    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = getSimplerStaticData();
        System.out.println(getMaximumPathProduct(graph, START, TARGET));
        System.out.println(path);
    }

    private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
        Set<String> seen = new HashSet<>();
        seen.add(start);
        List<String>aPath = new ArrayList<>();
        aPath.add(start);
        return dfs(start, target, seen, graph, aPath);
    }

    private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph,
                                                                                        List<String> aPath) {
        if(target.equals(current))
            return 1;

        int res = 0;

        Map<String, Integer> neighbors = graph.get(current);
        for(String neighbor: neighbors.keySet()) {
            if(!seen.contains(neighbor) ) {
                seen.add(neighbor);
                List<String> newPath = new ArrayList<>(aPath);
                newPath.add(neighbor);
                int distance = neighbors.get(neighbor);
                int newDistance = distance * dfs(neighbor, target, seen, graph, newPath);
                if(newDistance > res){
                    res = newDistance;
                    path = newPath;
                    path.add(target);
                }
                seen.remove(neighbor);
            }
        }

        return res;
    }

    private static Map<String, Map<String, Integer>> getSimplerStaticData() {
        Map<String, Map<String, Integer>> res = new HashMap<>();
        Map<String, Integer> value1 = new HashMap<>();
        value1.put("B", 6);
        value1.put("D", 1);
        res.put("A", value1);

        Map<String, Integer> value2 = new HashMap<>();
        value2.put("A", 6);
        value2.put("D", 2);
        value2.put("E", 2);
        value2.put("C", 5);
        res.put("B", value2);

        Map<String, Integer> value3 = new HashMap<>();
        value3.put("B", 5);
        value3.put("E", 5);
        res.put("C", value3);

        Map<String, Integer> value4 = new HashMap<>();
        value4.put("A", 1);
        value4.put("B", 2);
        value4.put("E", 2);
        res.put("D", value4);

        Map<String, Integer> value5 = new HashMap<>();
        value5.put("B", 2);
        value5.put("C", 5);
        value5.put("D", 2);
        res.put("E", value5);

        return res;
    }
}

如何在回溯期间打印路径？

How to print path during backtracking?

depth-first-search

recursive-backtracking