В настоящее время я выполняю задание, в котором нам нужно найти путь от узла на неориентированном графе, начального узла, к узлу назначения без изменения типа ребра (каждое ребро помечено буквой) больше, чемуказанное количество раз.(Например, если разрешено только одно изменение, то переход от ребра с надписью «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).