Wie entwerfe ich einen Algorithmus? Einführung in gängige Algorithmusparadigmen

Wie entwerfe ich einen Algorithmus? Der folgende Artikel analysiert für Sie gängige Algorithmusparadigmen. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird für alle hilfreich sein.

Klären Sie zunächst drei Konzepte:

Algorithmus: Der Prozess der schrittweisen Lösung von Problemen.

Paradigma: Eine Art, über ein Problem nachzudenken.

Algorithmisches Paradigma: Ein allgemeiner Ansatz zum Aufbau effizienter Lösungen für Probleme.

In diesem Artikel werden einige häufig verwendete Algorithmusparadigmen besprochen, wie zum Beispiel

• Divide-and-Conquer-Algorithmus
• Dynamische Programmierung
• Greedy-Algorithmus
• Backtracking-Algorithmus

Divide and Conquer

Unter den Sortieralgorithmen ist der Divide and Conquer-Algorithmus der gemeinsame Punkt der beiden Algorithmen Merge und Quick Sort.

Teile und herrsche ist ein gängiger Algorithmusentwurf. Die Idee besteht darin, das Problem in kleinere Teilprobleme zu zerlegen, die dem ursprünglichen Problem ähneln. Teilprobleme werden normalerweise rekursiv gelöst und die Lösungen der Teilprobleme werden kombiniert, um das ursprüngliche Problem zu lösen.

Die Logik der Divide-and-Conquer-Methode lässt sich in drei Schritte unterteilen:

1. Das ursprüngliche Problem in kleinere Teilprobleme aufteilen.
2. Lösen Sie das Unterproblem rekursiv und geben Sie die Lösung an das Unterproblem zurück, nachdem die Lösung abgeschlossen ist.
3. Fügen Sie die Lösungen der Teilprobleme zur Lösung des ursprünglichen Problems zusammen.

Beispiel für die Divide-and-Conquer-Methode: binäre Suche

Das Folgende ist eine binäre Suche, die mit Divide-and-Conquer implementiert wurde.

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

Bitte beachten Sie, dass die Funktion binarySearch oben für den Aufruf durch andere gedacht ist, während binarySearchRecursive dort ist, wo die Methode „Teile und herrsche“ implementiert ist.

Dynamische Programmierung

Dynamische Programmierung ist eine Optimierungstechnik, die zur Lösung komplexer Probleme durch Aufteilung in kleinere Teilprobleme verwendet wird. Es ähnelt stark der Methode „Teile und herrsche“, aber anstatt das Problem in unabhängige Unterprobleme zu zerlegen und diese dann miteinander zu kombinieren, zerlegt die dynamische Programmierung das Problem nur in unabhängige Unterprobleme.

Die Algorithmuslogik ist in drei Schritte unterteilt:

1. Unterprobleme definieren.
2. Wiederholen Sie diesen Vorgang, um Teilprobleme zu lösen.
3. Grundlegende Probleme identifizieren und lösen.

Dynamischer Programmierfall: Minimales Münzwechselproblem

Dies ist eine häufige Frage im Vorstellungsgespräch, die als Münzwechselproblem bezeichnet wird. Das Münzwechselproblem ist eine Möglichkeit, herauszufinden, wie viele bestimmte Münzenzahlen angesichts der Wechselgeldmenge zum Wechseln verwendet werden können. Das Problem des minimalen Münzwechsels besteht einfach darin, die Mindestanzahl an Münzen zu ermitteln, die erforderlich ist, um einen bestimmten Geldwert zu verwenden. Wenn Sie beispielsweise 37 Cent Wechselgeld benötigen, können Sie 1 2 Cent, 1 5 Cent, 1 1 Dime und 1 2 Cent verwenden.

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

Im obigen Code stellt der Parameter coins den Nennwert dar ([1, 2, 5, 10, 20, 50] in RMB). Um Doppelzählungen zu vermeiden, wird ein cache verwendet. Die Funktion makeChange wird rekursiv implementiert und ist eine interne Funktion mit Zugriff auf cache.

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

Greedy-Algorithmus

Greedy-Algorithmus bezieht sich auf die aktuelle optimale Lösung und versucht, eine globale optimale Lösung zu finden. Im Gegensatz zur dynamischen Programmierung wird die Gesamtsituation nicht berücksichtigt. Greedy-Algorithmen sind in der Regel einfach und intuitiv, stellen jedoch möglicherweise nicht die insgesamt optimale Lösung dar.

Fall eines gierigen Algorithmus: Problem des minimalen Münzwechsels

Das oben durch dynamische Programmierung gelöste Münzproblem kann auch durch einen gierigen Algorithmus gelöst werden. Ob diese Lösung optimal ist oder nicht, hängt von der verwendeten Stückelung ab.

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

Wie Sie sehen, ist der Greedy-Algorithmus viel einfacher als die dynamische Programmierlösung. Werfen wir einen Blick auf denselben Lösungsfall, um den Unterschied zwischen den beiden zu verstehen:

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

Der Greedy-Algorithmus liefert die optimale Lösung für das erste Problem, aber das zweite ist nicht die optimale Lösung ( Das sollte es sein). sein [3，3]).

Der Greedy-Algorithmus ist einfacher und schneller als der dynamische Programmieralgorithmus, aber die erhaltene Lösung ist möglicherweise nicht die optimale Lösung.

Backtracking-Algorithmus

Backtracking-Algorithmus eignet sich hervorragend, um Schritt für Schritt Lösungen zu finden und zu entwickeln.

1. Versuchen Sie, das Problem auf eine Weise zu lösen.
2. Wenn es nicht funktioniert, gehen Sie einen Schritt zurück und wiederholen Sie Schritt 1, bis Sie eine passende Lösung gefunden haben.

Für den Backtracking-Algorithmus werde ich einen weiteren Artikel schreiben, um komplexere Algorithmen vorzustellen. Ich habe noch nicht herausgefunden, was ich schreiben soll. Vielleicht geht es darum, ein Programm zum Lösen von Sudoku zu schreiben. Wenn Sie daran interessiert sind, folgen Sie bitte meinem offiziellen Account!

Algorithmen sind endlos. Ich hoffe, dieser Artikel kann Ihnen helfen, einige gängige Algorithmusparadigmen zu verstehen.

Verwandte kostenlose Lernempfehlungen: JS-Video-Tutorial

Das obige ist der detaillierte Inhalt vonWie entwerfe ich einen Algorithmus? Einführung in gängige Algorithmusparadigmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!