java是一种从开始到结束查找路径的有效方法

Question

我目前正在做一项任务，我们需要找到一条从无向图上的一个节点（起始节点）到目标节点的路径，而不改变边的类型（每条边都用字母标记）超过指定的次数。（例如，如果只允许进行一次更改，则从标记为“a”的边到标记为“b”的边将使用该更改。但从“a”到“a”不会使用任何更改）。我们只能使用深度优先搜索（DFS）遍历树。 图形采用矩形/方形网格格式，因此每个节点可以具有至少1条或2条边（这些节点要么仅连接到一个节点，要么在图形的拐角处连接到两个节点），最多4条边

我的算法使用DFS遍历图形，从开始到结束查找每个可能的解决方案/路径，然后查找每个解决方案/路径需要的更改数量，如果更改数量小于或等于允许的更改数量，则返回需要最小更改量的解决方案。这在大多数情况下都有效，但是，当图形大小为18个节点（向下和向上）时，需要花费太长的时间才能得出答案，或者干脆崩溃

所以我只是想知道是否有更有效的方法？有没有办法修改我的代码以提高效率

//The solver method that returns the solution
public Iterator<GraphNode> solve() throws GraphException {
    GraphNode startNode = graph.getNode(startLoc); //Creates the starting node.
    GraphNode endNode = graph.getNode(endLoc); //Creates the ending node.

    pathDepthFirstSearch(graph, startNode, endNode);

    int smallest = findSmallestChangeSolution(listOfSolutions);
    if(smallest == -1) {
        return null;
    }

    return listOfSolutions.get(smallest).iterator();
}

//DFS traversal and add the nodes along a path to an ArrayList.
private void pathDepthFirstSearch(Graph graph, GraphNode u, GraphNode v) throws GraphException {
    listOfNodes.add(u);
    u.setMark(true);
    if(u.getName() == v.getName()) {
        addSolutionToList(new ArrayList<GraphNode>(listOfNodes));
    } else {
        for (Iterator<GraphEdge> iter = graph.incidentEdges(u); iter.hasNext();) {
            GraphEdge nextEdge = iter.next();
            GraphNode secondEndPoint = nextEdge.secondEndpoint();
            if(secondEndPoint.getMark() == false) {
                pathDepthFirstSearch(graph,secondEndPoint, v);
            }
        }
    }
    listOfNodes.remove(u);
    u.setMark(false);
}

//Adds the each solution to an ArrayList
private void addSolutionToList(ArrayList<GraphNode> list) {
    ArrayList<GraphNode> tempList = new ArrayList<GraphNode>();
    for (int i = 0; i < list.size(); i++) {
        tempList.add(list.get(i));
    }
    listOfSolutions.add(tempList);
}

//Finds the solution with the smallest number of changes and returns the
//index of the solution list with that number of changes.
private int findSmallestChangeSolution(ArrayList<ArrayList<GraphNode>> list) throws GraphException {
    int changes = 0;
    int[] changesForEachSolution = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        for(int j = 0; j < list.get(i).size() - 2; j++) {
            if(graph.getEdge(list.get(i).get(j), list.get(i).get(j+1)).getLabel() != graph.getEdge(list.get(i).get(j+1), list.get(i).get(j+2)).getLabel()) {
                changes++; //Increments the number of changes by 1 if the two consecutive edges have different labels.
            }
        }
        changesForEachSolution[i] = changes;
        changes = 0; //Resets the number of changes to 0 for the next solution.
    }

    //Finds the position of the solution with the smallest number of changes.
    int smallest = changesForEachSolution[0];
    int indexOfSmallest = 0;
    for(int i = 0; i < changesForEachSolution.length; i++) {
        if(changesForEachSolution[i] < smallest) {
            smallest = changesForEachSolution[i];
            indexOfSmallest = i;
        }
    }

    //If the smallest number of changes is larger than the allowed number of changes, no solution exists, so return -1.
    if(smallest > kNumOfChanges) {
        return -1;
    }
    //Otherwise, the index of the solution is returned.
    return indexOfSmallest;
}

我还尝试过稍微修改代码，以便在找到有效的解决方案时停止DFS方法中的递归调用，但对于较大的图形（大于18 x 18的任何图形），这似乎没有什么区别

Answer 1

以下是加快解决方案速度的两种可能性：

1. 修剪。如果您知道到目前为止您的路径已经超出了允许的标签切换预算，则无需继续搜索。也就是说，可以将变量changesSoFar和lastEdgeLabel传递给pathDepthFirstSearch函数。每次处理标签不同于lastEdgeLabel的边缘时，增加changesSoFar，如果changesSoFar超过允许的最大开关数，则退出该函数

   如果跟踪当前最为人所知的路径并在listOfNodes.size() >= bestPathLengthSoFar时保留该函数，则可以进一步删减搜索。但是，如果您依赖

2. 迭代深化。总的来说，DFS并不是寻找最短路径的正确方法，因为它迫使您枚举数量呈指数增长的路径。如果严格限制您使用DFS，那么您也可以使用它的“迭代深化”版本。也就是说，首先运行受深度1限制的DFS。如果没有找到目标节点v，则运行受深度2限制的DFS，以此类推，直到最终到达其中一个深度的v。在这种情况下，不需要收集所有路径，只需输出找到的第一条路径即可。尽管它可能看起来像所描述的那样“缓慢”，但它比您当前正在进行的图形中所有路径的盲完全枚举要快得多