Implementierungsmethode des Backtracking-Algorithmus in PHP

Implementierungsmethode des Backtracking-Algorithmus in PHP

Der Backtracking-Algorithmus ist eine häufig verwendete Methode zur Lösung von Problemen. Seine Kernidee besteht darin, alle möglichen Lösungen rekursiv auszuprobieren und dann entsprechend den Anforderungen des Problems zu filtern, um diejenigen zu finden, die die Bedingungen erfüllen. optimale Lösung.

In PHP können wir den Backtracking-Algorithmus verwenden, um eine Reihe von Problemen wie Kombinationsprobleme, Permutationsprobleme, Labyrinthe usw. zu lösen. Im Folgenden stellen wir vor, wie der Backtracking-Algorithmus in PHP implementiert wird, und geben Codebeispiele.

1. Backtracking-Algorithmus-Implementierung des kombinatorischen Problems

Das kombinatorische Problem bezieht sich auf die Auswahl mehrerer Elemente aus einer gegebenen Menge, sodass die ausgewählten Elemente bestimmte Bedingungen erfüllen. Nehmen Sie als Beispiel die Kombination C(n, k), wobei n die Größe der gegebenen Menge und k die Anzahl der auszuwählenden Elemente darstellt. Das Folgende ist ein Beispiel für die Implementierung eines Backtracking-Algorithmus in PHP zur Lösung kombinatorischer Probleme:

function backtrack($nums, $k, $start, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = $start; $i < count($nums); $i++) {
        $track[] = $nums[$i];
        backtrack($nums, $k, $i + 1, $track, $res);
        array_pop($track);
    }
}

function combine($n, $k) {
    $nums = [];
    for ($i = 1; $i <= $n; $i++) {
        $nums[] = $i;
    }
    
    $res = [];
    backtrack($nums, $k, 0, [], $res);
    return $res;
}

$n = 4;
$k = 2;
$result = combine($n, $k);
print_r($result);

Im obigen Code wird die Backtrack-Funktion verwendet, um Backtracking-Suchen durchzuführen. Wenn die Anzahl der ausgewählten Elemente gleich k ist, zeichnen wir den aktuellen Track im Ergebnisarray $res auf. Führen Sie dann einen rekursiven Aufruf in der for-Schleife durch. Die übergebenen Parameter sind der gegebene Satz $nums, die Anzahl der auszuwählenden Elemente $k, die aktuell ausgewählte Startposition $start, das aktuell ausgewählte Elementarray $track und das Ergebnisarray $res.

2. Implementierung des Backtracking-Algorithmus für das Permutationsproblem

Das Permutationsproblem bezieht sich auf die Auswahl einer entsprechenden Anzahl von Elementen aus einer gegebenen Menge, sodass die Reihenfolge der ausgewählten Elemente bestimmte Bedingungen erfüllt. Nehmen Sie als Beispiel die Anordnung P(n, k), wobei n die Größe der gegebenen Menge und k die Anzahl der auszuwählenden Elemente darstellt. Das Folgende ist ein Beispiel für die Implementierung des Backtracking-Algorithmus zur Lösung des Permutationsproblems in PHP:

function backtrack($nums, $k, &$visited, $track, &$res) {
    if (count($track) == $k) {
        $res[] = $track;
        return;
    }
    
    for ($i = 0; $i < count($nums); $i++) {
        if (!$visited[$i]) {
            $visited[$i] = true;
            $track[] = $nums[$i];
            backtrack($nums, $k, $visited, $track, $res);
            array_pop($track);
            $visited[$i] = false;
        }
    }
}

function permute($nums, $k) {
    $res = [];
    $visited = array_fill(0, count($nums), false);
    backtrack($nums, $k, $visited, [], $res);
    return $res;
}

$nums = [1, 2, 3];
$k = 2;
$result = permute($nums, $k);
print_r($result);

Im obigen Code wird die Backtrack-Funktion verwendet, um eine Backtracking-Suche durchzuführen. Wenn die Anzahl der ausgewählten Elemente gleich k ist, zeichnen wir den aktuellen Track im Ergebnisarray $res auf. In der for-Schleife wählen wir jedes Mal ein nicht besuchtes Element aus und fügen es der Spur hinzu. Führen Sie dann einen rekursiven Aufruf durch. Die übergebenen Parameter sind die gegebene Menge $nums, die Anzahl der auszuwählenden Elemente $k, das Array $visited, das aufzeichnet, ob das aktuelle Element besucht wurde, das aktuell ausgewählte Elementarray $track und das Ergebnisarray $res.

3. Implementierung des Backtracking-Algorithmus für das Labyrinthproblem

Das Labyrinthproblem bezieht sich auf das Finden des Pfades vom Startpunkt zum Endpunkt in einem bestimmten Labyrinth. Ein Labyrinth kann durch ein zweidimensionales Array dargestellt werden, wobei 0 ein passierbares Gitter und 1 ein Hindernis darstellt. Das Folgende ist ein Beispiel für die Implementierung des Backtracking-Algorithmus zur Lösung des Labyrinthproblems in PHP:

function backtrack($maze, $i, $j, $path, &$res) {
    if ($i == count($maze) - 1 && $j == count($maze[0]) - 1) {
        $res[] = $path;
        return;
    }
    
    $maze[$i][$j] = -1;
    
    $dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $dirNames = ['right', 'down', 'left', 'up'];
    
    for ($k = 0; $k < 4; $k++) {
        $ni = $i + $dirs[$k][0];
        $nj = $j + $dirs[$k][1];
        
        if ($ni >= 0 && $ni < count($maze) && $nj >= 0 && $nj < count($maze[0]) && $maze[$ni][$nj] == 0) {
            backtrack($maze, $ni, $nj, $path . ' -> ' . $dirNames[$k], $res);
        }
    }
    
    $maze[$i][$j] = 0;
}

function solveMaze($maze) {
    $res = [];
    backtrack($maze, 0, 0, '(0, 0)', $res);
    return $res;
}

$maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 0, 0]
];

$result = solveMaze($maze);
print_r($result);

Im obigen Code wird die Backtrack-Funktion verwendet, um Backtracking-Suchen durchzuführen. Wenn wir den Endpunkt erreichen, zeichnen wir den aktuellen Pfad im Ergebnisarray $res auf. In der for-Schleife versuchen wir, uns in vier Richtungen vorwärts zu bewegen: rechts, unten, links und oben, und führen rekursive Aufrufe durch. Vor dem rekursiven Aufruf müssen wir feststellen, ob das aktuelle Gitter passierbar ist, und es als unzugänglich markieren, um wiederholte Besuche zu vermeiden.

Das obige ist der detaillierte Inhalt vonImplementierungsmethode des Backtracking-Algorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!