Comment concevoir un algorithme ? Introduction aux paradigmes algorithmiques courants

Comment concevoir un algorithme ? L'article suivant analysera pour vous les paradigmes d'algorithmes courants. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il sera utile à tout le monde.

Clarifiez d'abord trois concepts :

Algorithme : Le processus de résolution de problèmes étape par étape.

Paradigme : Un mode de réflexion sur un problème.

Paradigme algorithmique : Une approche générale pour construire des solutions efficaces aux problèmes.

Cet article traite de certains paradigmes d'algorithmes couramment utilisés, tels que

• Algorithme Diviser pour régner
• Programmation dynamique
• Algorithme gourmand
• Algorithme de Backtracking

Divide and Conquer

Parmi les algorithmes de tri, le point commun des deux algorithmes, fusion et tri rapide, est l'algorithme diviser pour régner.

Diviser pour mieux régner est une conception d'algorithme courante. L'idée est de décomposer le problème en sous-problèmes plus petits qui sont similaires au problème d'origine. Les sous-problèmes sont généralement résolus de manière récursive et les solutions aux sous-problèmes sont combinées pour résoudre le problème d'origine.

La logique de la méthode diviser pour régner peut être divisée en trois étapes :

1. Diviser le problème d'origine en sous-problèmes plus petits.
2. Résolvez le sous-problème de manière récursive et renvoyez la solution au sous-problème une fois la solution terminée.
3. Fusionnez les solutions aux sous-problèmes dans la solution au problème d'origine.

Exemple de méthode diviser pour régner : recherche binaire

Ce qui suit est une recherche binaire mise en œuvre à l'aide de diviser pour régner.

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

Veuillez noter que la fonction binarySearch ci-dessus est destinée aux autres, tandis que binarySearchRecursive est l'endroit où la méthode diviser pour mieux régner est implémentée.

Programmation dynamique

La programmation dynamique est une technique d'optimisation utilisée pour résoudre des problèmes complexes en les divisant en sous-problèmes plus petits. Cela ressemble beaucoup à la méthode diviser pour régner, mais au lieu de décomposer le problème en sous-problèmes indépendants puis de les combiner ensemble, la programmation dynamique décompose uniquement le problème en sous-problèmes indépendants .

La logique de l'algorithme est divisée en trois étapes :

1. Définir les sous-problèmes.
2. Répétez pour résoudre les sous-problèmes.
3. Identifier et résoudre les problèmes de base.

Cas de programmation dynamique : problème de changement de pièce minimum

Il s'agit d'une question d'entretien courante appelée problème de changement de pièce. Le problème du changement de pièces est un moyen de déterminer combien de nombres spécifiques de pièces peuvent être utilisés pour rendre la monnaie, compte tenu de la quantité de monnaie. Le problème du changement minimum de pièces consiste simplement à trouver le nombre minimum de pièces requis pour utiliser une dénomination monétaire donnée. Par exemple, si vous avez besoin de monnaie pour 37 cents, vous pouvez utiliser 1,2 cent, 1,5 cent, 1,1 centime et 1,2 cent.

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

Dans le code ci-dessus, le paramètre coins représente la dénomination ([1, 2, 5, 10, 20, 50] en RMB). Pour éviter le double comptage, un cache est utilisé. La fonction makeChange est implémentée de manière récursive et est une fonction interne avec accès à cache.

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

Algorithme glouton

L'algorithme glouton est lié à la solution optimale actuelle et tente de trouver une solution optimale globale. Contrairement à la programmation dynamique, elle ne prend pas en compte la situation globale. Les algorithmes gloutons ont tendance à être simples et intuitifs, mais ne constituent peut-être pas la solution globale optimale.

Cas de l'algorithme glouton : problème de changement minimum de pièces

Le problème des pièces résolu par la programmation dynamique ci-dessus peut également être résolu par un algorithme glouton. Que cette solution soit optimale ou non dépend de la dénomination utilisée.

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

Comme vous pouvez le constater, l'algorithme glouton est bien plus simple que la solution de programmation dynamique. Regardons le même cas de solution pour comprendre la différence entre les deux :

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

L'algorithme glouton donne la solution optimale au premier problème, mais le second n'est pas la solution optimale (il devrait être [3，3]).

L'algorithme glouton est plus simple et plus rapide que l'algorithme de programmation dynamique, mais la solution obtenue n'est peut-être pas la solution optimale. L'

Algorithme de retour en arrière

L'algorithme de retour en arrière est idéal pour trouver et créer des solutions étape par étape.

1. Essayez de résoudre le problème dans un sens.
2. Si cela ne fonctionne pas, revenez en arrière et répétez l'étape 1 jusqu'à ce que vous trouviez une solution appropriée.

Pour l'algorithme de backtracking, j'écrirai un autre article pour présenter des algorithmes plus complexes. Je n'ai pas encore trouvé quoi écrire. C'est peut-être pour écrire un programme pour résoudre le Sudoku. Si cela vous intéresse, veuillez suivre mon compte officiel !

Les algorithmes sont sans fin. J'espère que cet article pourra vous aider à comprendre certains paradigmes algorithmiques courants.

Recommandations d'apprentissage gratuites associées : Tutoriel vidéo js

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!