我目前正在做一个分配，在此情况下，我们需要查找从无向图上的一个节点（起始节点）到目标节点的路径，而不会改变边的类型（每个边都标记有一个字母）超过指定的数量次。 （例如，如果只允许一个更改，那么从标记为“ a”的边到标记为“ b”的边将用完该更改。但是，从“ a”到“ a”的行将不使用任何更改）。我们只能使用深度优先搜索（DFS）遍历树。
该图采用矩形/正方形网格格式，因此每个节点可以具有至少1个或2个边（这些节点仅连接到一个节点或在图的角处并连接到两个节点），并且最大4个边缘。
我的算法使用DFS遍历图形，找到从开始到结束的每个可能的解决方案/路径，然后找到每个解决方案/路径所需的更改次数，然后返回需要最小更改量的解决方案。更改小于或等于允许的更改数量。这在大多数情况下确实有效，但是，当图形大小为18个节点x向下的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的图形）来说，这似乎没有什么不同。
最佳答案
以下是两种加快解决方案的可能性：
修剪。如果您知道到目前为止的路径已经超出了标签交换允许的预算，则无需继续搜索。也就是说，您可以将变量changesSoFar和lastEdgeLabel传递给您的pathDepthFirstSearch函数。每次处理标签不同于changesSoFar的边时，增加lastEdgeLabel，如果changesSoFar超过允许的最大开关数量，则退出功能。
如果您跟踪当前最知名的路径并在listOfNodes.size() >= bestPathLengthSoFar时保留该功能，则可以进一步简化搜索。但是，如果您依靠，则不需要
迭代加深。通常，DFS不是找到最短路径的正确方法，因为它会迫使您枚举数量成倍增长的路径。如果严格限制您使用DFS，也许您也可以使用其“迭代加深”版本。也就是说，首先运行受深度1限制的DFS。如果找不到目标节点v，请运行受深度2限制的DFS，依此类推，直到最终到达其中一个深度的v。在这种情况下，您无需收集所有路径，而只需输出找到的第一个路径。尽管如前所述，它看上去“慢”，但它比对您当前正在执行的图形中所有路径的盲目完全列举要快得多。
关于java - 从头到尾寻找路径的有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53623703/