Méthode d'implémentation de l'algorithme de backtracking en PHP

Méthode d'implémentation de l'algorithme de backtracking en PHP

L'algorithme de backtracking est une méthode couramment utilisée pour résoudre des problèmes. Son idée principale est d'essayer toutes les solutions possibles de manière récursive, puis de filtrer en fonction des exigences du problème pour trouver celles qui répondent aux conditions optimales. solution.

En PHP, nous pouvons utiliser l'algorithme de backtracking pour résoudre une série de problèmes tels que des problèmes de combinaison, des problèmes de permutation, des labyrinthes, etc. Ci-dessous, nous présenterons comment implémenter l'algorithme de backtracking en PHP et donnerons des exemples de code.

1. Implémentation d'un algorithme de backtracking du problème combinatoire

Le problème combinatoire fait référence à la sélection de plusieurs éléments dans un ensemble donné afin que les éléments sélectionnés répondent à des conditions spécifiques. Prenons comme exemple la combinaison C(n, k), où n représente la taille de l'ensemble donné et k représente le nombre d'éléments à sélectionner. Voici un exemple d'implémentation d'algorithme de backtracking en PHP pour résoudre des problèmes combinatoires :

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);

Dans le code ci-dessus, la fonction backtracking est utilisée pour effectuer des recherches de backtracking. Lorsque le nombre d'éléments sélectionnés est égal à k, nous enregistrons la piste actuelle dans le tableau résultat $res. Effectuez ensuite un appel récursif dans la boucle for. Les paramètres transmis sont l'ensemble $nums donné, le nombre d'éléments à sélectionner $k, la position de départ actuellement sélectionnée $start, le tableau d'éléments actuellement sélectionné $track et le tableau de résultats. $rés.

2. Implémentation d'un algorithme de retour en arrière pour le problème de permutation

Le problème de permutation fait référence à la sélection d'un nombre correspondant d'éléments dans un ensemble donné afin que l'ordre des éléments sélectionnés réponde à des conditions spécifiques. Prenons l'exemple de l'arrangement P(n, k), où n représente la taille de l'ensemble donné et k représente le nombre d'éléments à sélectionner. Voici un exemple d'implémentation de l'algorithme de backtracking pour résoudre le problème de permutation en 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);

Dans le code ci-dessus, la fonction backtracking est utilisée pour effectuer une recherche de backtracking. Lorsque le nombre d'éléments sélectionnés est égal à k, nous enregistrons la piste actuelle dans le tableau résultat $res. Dans la boucle for, nous sélectionnons à chaque fois un élément non visité et l'ajoutons à la piste. Effectuez ensuite un appel récursif. Les paramètres transmis sont l'ensemble donné $nums, le nombre d'éléments à sélectionner $k, le tableau $visited qui enregistre si l'élément actuel est visité, le tableau d'éléments actuellement sélectionné $track et le. tableau de résultats. $res.

3. Implémentation d'un algorithme de retour en arrière pour le problème du labyrinthe

Le problème du labyrinthe fait référence à la recherche du chemin depuis le point de départ jusqu'au point final dans un labyrinthe donné. Un labyrinthe peut être représenté par un tableau bidimensionnel, où 0 représente une grille praticable et 1 représente un obstacle. Voici un exemple d'implémentation de l'algorithme de backtracking en PHP pour résoudre le problème du labyrinthe :

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);

Dans le code ci-dessus, la fonction backtracking est utilisée pour effectuer des recherches de backtracking. Lorsque nous atteignons le point final, nous enregistrons le chemin actuel dans le tableau de résultats $res. Dans la boucle for, nous essayons d'avancer dans quatre directions : droite, bas, gauche et haut, et d'effectuer des appels récursifs. Avant l'appel récursif, nous devons déterminer si la grille actuelle est une grille praticable et la marquer comme inaccessible pour éviter des visites répétées.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!