Angenommen Matze Finden Sie in Form einer binären rechteckigen Matrix die kürzeste Weglänge im Labyrinth von einer bestimmten Quelle zu einem bestimmten Ziel. Der Pfad kann nur aus Zellen mit dem Wert 1 konstruiert werden, und wir können uns in jedem Moment nur einen Schritt in eine der vier Richtungen bewegen.
Die gültigen Züge sind:
Go Top: (x, y) ——> (x – 1, y)
Go Left: (x, y) ——> (x, y – 1)
Go Down: (x, y) ——> (x + 1, y)
Go Right: (x, y) ——> (x, y + 1)
Betrachten Sie beispielsweise die folgende binäre Matrix. Wenn Quelle = (0, 0) und Ziel = (7, 5), hat der kürzeste Weg von der Quelle zum Ziel die Länge 12.
[ 1 1 1 1 1 0 0 1 1 1 ]
[ 0 1 1 1 1 1 0 1 0 1 ]
[ 0 0 1 0 1 1 1 0 0 1 ]
[ 1 0 1 1 1 0 1 1 0 1 ]
[ 0 0 0 1 0 0 0 1 0 1 ]
[ 1 0 1 1 1 0 0 1 1 0 ]
[ 0 0 0 0 1 0 0 1 0 1 ]
[ 0 1 1 1 1 1 1 1 0 0 ]
[ 1 1 1 1 1 0 0 1 1 1 ]
[ 0 0 1 0 0 1 1 0 0 1 ]
Um den kürzesten Weg des Labyrinths zu finden, suchen Sie alle möglichen Wege im Labyrinth von der Startposition bis zur Zielposition, bis alle Möglichkeiten erschöpft sind. Wir können dies leicht mit Hilfe von erreichen backtracking. Die Idee ist, von der gegebenen Quellzelle in der Matrix auszugehen und alle vier möglichen Pfade zu erkunden und rekursiv zu prüfen, ob sie zum Ziel führen oder nicht. Aktualisieren Sie dann die minimale Pfadlänge, wann immer die Zielzelle erreicht wird. Wenn ein Pfad das Ziel nicht erreicht oder alle möglichen Routen von der aktuellen Zelle aus erkundet hat, gehen Sie zurück. Um sicherzustellen, dass der Pfad einfach ist und keine Zyklen enthält, verfolgen Sie die am aktuellen Pfad beteiligten Zellen in einer Matrix, und ignorieren Sie die Zelle, bevor Sie eine Zelle untersuchen, wenn sie bereits im aktuellen Pfad enthalten ist.
Es folgt die C++-, Java- und Python-Implementierung der Idee:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> #include <vector> #include <climits> #include <cstring> using namespace std; // Prüfen, ob es möglich ist, von der aktuellen Position zu (x, y) zu gehen. Das // Funktion gibt false zurück, wenn die Zelle den Wert 0 hat oder bereits besucht wurde bool isSafe(vector<vector<int>> &mat, vector<vector<bool>> &visited, int x, int y) { return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size()) && mat[x][y] == 1 && !visited[x][y]; } // Finden Sie die kürzestmögliche Route in einer Matrix `mat` von der Quellzelle (i, j) // zur Zielzelle (x, y). // `min_dist` wird als Referenz übergeben und speichert die Länge des längsten Pfades // von der Quelle zu einem bisher gefundenen Ziel, und `dist` behält die Länge bei // des Pfades von einer Quellzelle zu einer aktuellen Zelle (i, j). void findShortestPath(vector<vector<int>> &mat, vector<vector<bool>> &visited, int i, int j, int x, int y, int &min_dist, int dist) { // Wenn das Ziel gefunden wurde, aktualisiere `min_dist` if (i == x && j == y) { min_dist = min(dist, min_dist); return; } // setze (i, j) Zelle als besucht visited[i][j] = true; // Gehe zur untersten Zelle if (isSafe(mat, visited, i + 1, j)) { findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1); } // zur rechten Zelle gehen if (isSafe(mat, visited, i, j + 1)) { findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1); } // zur obersten Zelle gehen if (isSafe(mat, visited, i - 1, j)) { findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1); } // zur linken Zelle gehen if (isSafe(mat, visited, i, j - 1)) { findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1); } // backtrack: entferne (i, j) aus der besuchten Matrix visited[i][j] = false; } // Wrapper über die Funktion findShortestPath() int findShortestPathLength(vector<vector<int>> &mat, pair<int, int> &src, pair<int, int> &dest) { // Basisfall: ungültige Eingabe if (mat.size() == 0 || mat[src.first][src.second] == 0 || mat[dest.first][dest.second] == 0) { return -1; } // `M × N`-Matrix int M = mat.size(); int N = mat[0].size(); // Erstellen Sie eine `M × N`-Matrix, um die besuchten Zellen zu verfolgen vector<vector<bool>> visited; visited.resize(M, vector<bool>(N)); int min_dist = INT_MAX; findShortestPath(mat, visited, src.first, src.second, dest.first, dest.second, min_dist, 0); if (min_dist != INT_MAX) { return min_dist; } return -1; } int main() { vector<vector<int>> mat = { { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }, { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 }, }; pair<int, int> src = make_pair(0, 0); pair<int, int> dest = make_pair(7, 5); int min_dist = findShortestPathLength(mat, src, dest); if (min_dist != -1) { cout << "The shortest path from source to destination " "has length " << min_dist; } else { cout << "Destination cannot be reached from a given source"; } return 0; } |
Ergebnis:
The shortest path from source to destination has length 12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
class Main { // Prüfen, ob es möglich ist, von der aktuellen Position zu (x, y) zu gehen. Das // Die Funktion gibt false zurück, wenn die Zelle ungültig ist, den Wert 0 hat oder bereits besucht wurde private static boolean isSafe(int[][] mat, boolean[][] visited, int x, int y) { return (x >= 0 && x < mat.length && y >= 0 && y < mat[0].length) && mat[x][y] == 1 && !visited[x][y]; } // Finden Sie die kürzestmögliche Route in einer Matrix `mat` von der Quellzelle (i, j) // zur Zielzelle (x, y). // `min_dist` speichert die Länge des längsten Pfades von der Quelle zu einem Ziel // bisher gefunden, und `dist` behält die Länge des Pfades von einer Quellzelle bei // zur aktuellen Zelle (i, j). public static int findShortestPath(int[][] mat, boolean[][] visited, int i, int j, int x, int y, int min_dist, int dist) { // Wenn das Ziel gefunden wurde, aktualisiere `min_dist` if (i == x && j == y) { return Integer.min(dist, min_dist); } // setze (i, j) Zelle als besucht visited[i][j] = true; // Gehe zur untersten Zelle if (isSafe(mat, visited, i + 1, j)) { min_dist = findShortestPath(mat, visited, i + 1, j, x, y, min_dist, dist + 1); } // zur rechten Zelle gehen if (isSafe(mat, visited, i, j + 1)) { min_dist = findShortestPath(mat, visited, i, j + 1, x, y, min_dist, dist + 1); } // zur obersten Zelle gehen if (isSafe(mat, visited, i - 1, j)) { min_dist = findShortestPath(mat, visited, i - 1, j, x, y, min_dist, dist + 1); } // zur linken Zelle gehen if (isSafe(mat, visited, i, j - 1)) { min_dist = findShortestPath(mat, visited, i, j - 1, x, y, min_dist, dist + 1); } // backtrack: entferne (i, j) aus der besuchten Matrix visited[i][j] = false; return min_dist; } // Wrapper über die Funktion findShortestPath() public static int findShortestPathLength(int[][] mat, int i, int j, int x, int y) { // Basisfall: ungültige Eingabe if (mat == null || mat.length == 0 || mat[i][j] == 0 || mat[x][y] == 0) { return -1; } // `M × N`-Matrix int M = mat.length; int N = mat[0].length; int min_dist; // Erstellen Sie eine `M × N`-Matrix, um die besuchten Zellen zu verfolgen boolean[][] visited = new boolean[M][N]; min_dist = findShortestPath(mat, visited, i, j, x, y, Integer.MAX_VALUE, 0); if (min_dist != Integer.MAX_VALUE) { return min_dist; } return -1; } public static void main(String[] args) { int mat[][] = { { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }, { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 }, }; int min_dist = findShortestPathLength(mat, 0, 0, 7, 5); if (min_dist != -1) { System.out.println("The shortest path from source to destination " + "has length " + min_dist); } else { System.out.println("Destination cannot be reached from source"); } } } |
Ergebnis:
The shortest path from source to destination has length 12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
import sys # Prüfen Sie, ob es möglich ist, von der aktuellen Position zu (x, y) zu gehen. Das # Die #-Funktion gibt falsch zurück, wenn die Zelle ungültig ist, den Wert 0 hat oder bereits besucht wurde def isSafe(mat, visited, x, y): return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and \ not (mat[x][y] == 0 or visited[x][y]) # Finden Sie die kürzestmögliche Route in einer Matrix `mat` von der Quellzelle (i, j) # zur Zielzelle `dest`. # `min_dist` speichert die Länge des längsten Pfads von der Quelle zu einem Ziel # bisher gefunden, und `dist` behält die Länge des Pfades von einer Quellzelle zu bei # die aktuelle Zelle (i, j). def findShortestPath(mat, visited, i, j, dest, min_dist=sys.maxsize, dist=0): # Wenn das Ziel gefunden wird, aktualisiere `min_dist` if (i, j) == dest: return min(dist, min_dist) # stellt (i, j) Zelle wie besucht ein visited[i][j] = 1 # gehe zur untersten Zelle if isSafe(mat, visited, i + 1, j): min_dist = findShortestPath(mat, visited, i + 1, j, dest, min_dist, dist + 1) # gehe zur rechten Zelle if isSafe(mat, visited, i, j + 1): min_dist = findShortestPath(mat, visited, i, j + 1, dest, min_dist, dist + 1) # gehe zur obersten Zelle if isSafe(mat, visited, i - 1, j): min_dist = findShortestPath(mat, visited, i - 1, j, dest, min_dist, dist + 1) # gehe zur linken Zelle if isSafe(mat, visited, i, j - 1): min_dist = findShortestPath(mat, visited, i, j - 1, dest, min_dist, dist + 1) # Backtrack: Entferne (i, j) aus der besuchten Matrix visited[i][j] = 0 return min_Abstand # Wrapper über die Funktion findShortestPath() def findShortestPathLength(mat, src, dest): # Quellzelle abrufen (i, j) i, j = src # Zielzelle abrufen (x, y) x, y = dest # Basisgehäuse if not mat or len(mat) == 0 or mat[i][j] == 0 or mat[x][y] == 0: return -1 # `M × N`-Matrix (M, N) = (len(mat), len(mat[0])) # konstruiert eine `M × N`-Matrix, um die besuchten Zellen zu verfolgen visited = [[False for _ in range(N)] for _ in range(M)] min_dist = findShortestPath(mat, visited, i, j, dest) if min_dist != sys.maxsize: return min_dist else: return -1 if __name__ == '__main__': mat = [ [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 1, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0, 1, 0, 1], [0, 1, 1, 1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0, 0, 1, 1, 0, 0, 1] ] src = (0, 0) dest = (7, 5) min_dist = findShortestPathLength(mat, src, dest) if min_dist != -1: print("The shortest path from source to destination has length", min_dist) else: print("Destination cannot be reached from source") |
Ergebnis:
The shortest path from source to destination has length 12
Die zeitliche Komplexität der obigen Backtracking-Lösung wird höher sein, da alle Pfade zurückgelegt werden müssen. Da es sich jedoch um das Kürzeste-Wege-Problem handelt, Breitensuche (BFS) wäre eine ideale Wahl. Wenn BFS zur Lösung dieses Problems eingesetzt wird, reisen wir Ebene für Ebene. Das erste Auftreten des Zielknotens liefert uns also das Ergebnis, und wir können unsere Suche dort beenden. Der BFS-Ansatz wird diskutiert hier.