Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Inhaltsverzeichnis

Floyd-Algorithmus

Definition

Verwendung

Vorsichtsmaßnahmen

Ideen zur Problemlösung

Die grundlegenden Schritte

AcWing 343. Sortieren

Beschreibung der Frage

Code ausführen

Code-Ideen

Ideen verbessern

Floyd-Algorithmus

Definition

Der Floyd-Algorithmus, der vollständige Name des Floyd-Warshall-Algorithmus, ist ein dynamischer Programmieralgorithmus, der zur Lösung des Problems des kürzesten Pfades zwischen allen Scheitelpunktpaaren im Diagramm verwendet wird. Es eignet sich für gewichtete gerichtete Diagramme und kann negative Gewichtskanten verarbeiten (jedoch keine Diagramme mit negativen Gewichtszyklen) und kann erkennen, ob das Diagramm negative Gewichtszyklen enthält.

Verwendung

1. Berechnen Sie den kürzesten Weg zwischen allen Scheitelpunktpaaren: In Bereichen wie der Analyse sozialer Netzwerke, der Planung von Transportnetzwerken und dem Entwurf von Kommunikationsnetzwerken ist der Floyd-Algorithmus eine gute Wahl, wenn es darum geht, die kürzeste Entfernung zwischen zwei beliebigen Punkten zu berechnen.
2. Erkennen Sie negative Gewichtszyklen: In einigen Anwendungsszenarien muss sichergestellt werden, dass im Diagramm keine negativen Gewichtszyklen vorhanden sind, da dies auf eine Anomalie oder einen Fehlerzustand im System hinweisen kann.

Vorsichtsmaßnahmen

• Speicherverbrauch : Die Raumkomplexität des Floyd-Algorithmus beträgt O(n^2), wobei n die Anzahl der Eckpunkte im Diagramm ist. Bei großen Diagrammen kann dies zu einem Problem werden.
• Zeitkomplexität: Die zeitliche Komplexität des Floyd-Algorithmus beträgt O(n^3). Wenn die Anzahl der Eckpunkte groß ist, kann der Algorithmus sehr langsam werden.
• negative Gewichtsschleife : Wenn im Diagramm ein negativer Gewichtszyklus vorhanden ist, gerät Floyds Algorithmus in eine Endlosschleife, da ausgehend von einem Knoten die Pfadlänge durch diesen Zyklus unendlich reduziert werden kann. In der Praxis müssen solche Situationen zunächst erkannt und bewältigt werden.
• Algorithmen können negative Gewichtszyklen erkennen:Wenn bei der Ausführung des Algorithmus festgestellt wird, dass der kürzeste Weg von einem Scheitelpunkt zu sich selbst kleiner als 0 ist, d. h. D[i][i] < 0, dann gibt es im Diagramm mindestens einen negativen Gewichtszyklus. und der Algorithmus kann derzeit nicht das korrekte Ergebnis des kürzesten Pfades liefern.
• Bei sehr großen Diagrammen kann die hohe zeitliche und räumliche Komplexität des Algorithmus zu einem Engpass werden. Zu diesem Zeitpunkt müssen Sie möglicherweise effizientere Algorithmen in Betracht ziehen oder professionellere Datenstrukturen und Optimierungstechniken verwenden.

Ideen zur Problemlösung

Die Kernidee des Floyd-Algorithmus ist die dynamische Programmierung. Die grundlegenden Schritte sind wie folgt:

1. Initialisierung: Setzen Sie die Distanzmatrix D auf die Adjazenzmatrix des Diagramms, d. h. D[i][j] = Gewicht(i, j); für i != j, wenn (i, j) nicht verbunden ist D[i][ j] = ∞; D[i][i] = 0.
2. Dynamische Programmierung: Für k = 1 bis n aktualisieren Sie D so, dass D[i][j] = min(D[i][j], D[i][k] + D[k][j]), das ist Überprüfen Sie, ob der Abstand von i nach j durch den Zwischenknoten k verkürzt werden kann.
3. Ergebnis: Die endgültige D-Matrix enthält die kürzesten Pfadlängen zwischen allen Scheitelpunktpaaren. Wenn es ein bestimmtes D[i][j] < 0 und i != j gibt und D[i][i] < 0 während des Aktualisierungsvorgangs auftritt, bedeutet dies, dass es im Diagramm einen negativen Gewichtszyklus gibt.

Die Implementierung des Floyd-Algorithmus verwendet normalerweise eine Dreifachschleife. Die äußere Schleife durchläuft alle Zwischenscheitelpunkte k und die inneren beiden Schleifen durchlaufen alle Scheitelpunktpaare (i, j), um zu prüfen, ob es einen kürzeren Pfad gibt.

Die grundlegenden Schritte

Angenommen, wir haben einen gewichteten Graphen G mit n Eckpunkten, dann können wir ein zweidimensionales Array verwendendist[][] um die kürzeste Pfadlänge zwischen jedem Scheitelpunktpaar zu speichern. Anfänglich,dist[i][j]wird auf das Gewicht der direkt verbundenen Kante im Diagramm gesetzt. Wenn es keine direkt verbundene Kante zwischen i und j gibt, danndist[i][j]Auf unendlich eingestellt (was bedeutet, dass es nicht erreichbar ist).

1. Initialisierung : Erstellen Sie eine n×n-Matrix D, wobei D[i][j] mit dem Gewicht der direkten Kante von i nach j im Diagramm initialisiert oder auf unendlich gesetzt wird, wenn es keine direkte Kante zwischen i und j gibt. Diagonalelement D[i][i] = 0.

2. dynamische Programmierung : Aktualisieren Sie für jeden Scheitelpunkt k (als Zwischenscheitelpunkt) den kürzesten Pfad zwischen jedem Scheitelpunktpaar i und j. Es ist möglich, einen kürzeren Pfad mit k als Zwischenpunkt zu erhalten. Die Aktualisierungsformel lautet: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Das heißt, wenn der Weg von i nach j über k als Zwischenscheitelpunkt kürzer wird, aktualisieren Sie D[i][j].

3. Ergebnisausgabe: Nach n Iterationsrunden ist jedes Element D[i][j] in der Matrix D die kürzeste Pfadlänge von i nach j.

AcWing 343. Sortieren

Beschreibung der Frage

343. Sortieren – AcWing-Fragenbank

Code ausführen

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
#define PII pair<int, int>
#define fi first
#define se second
#define endl 'n'
map<int, int> mp;
 
const int N = 210, mod = 1e9 + 7;
int T, n, m, k;
int a[N], dist[N][N];
PII ans[N];
 
void floyd(int x) // 以 x 为中转点，更新其他点。
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
}
 
bool pd() // 判断是否所有点都已确定
{
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            if (dist[i][j] != 1e9)
                cnt++; // 当前点能到达的点数
        ans[i] = {cnt, i};
        for (int j = 1; j <= n; j++)
            if (i != j && dist[j][i] != 1e9)
                cnt++; // 能到达当前点的点数
        if (cnt != n)
            return 0;
    }
    sort(ans + 1, ans + n + 1);
    return 1;
}
 
int main() {
    while (cin >> n >> m && n) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)
                    dist[i][j] = 1e9;
 
        int flag = 0;
        for (int i = 1; i <= m; i++) {
            char a, t, b;
            cin >> a >> t >> b;
            int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
 
            if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y，出现矛盾
            {
                printf("Inconsistency found after %d relations.n", i);
                flag = 1;
            }
 
            dist[y][x] = 1;
            floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
            if (!flag && pd()) { // 发现所有点都已确定
                printf("Sorted sequence determined after %d relations: ", i);
                for (int i = 1; i <= n; i++)
                    cout << char(ans[i].se + 'A' - 1);
                printf(".n");
                flag = 1;
            }
        }
        if (!flag)
            printf("Sorted sequence cannot be determined.n"); // 无法确定
    }
 
    return 0;
}

Code-Ideen

1. Initialisierung: benutze einendistDas zweidimensionale Array wird auf unendlich initialisiert, was bedeutet, dass es standardmäßig keine eindeutige Ordnungsbeziehung zwischen den Ungleichungen gibt.
2. Eingabe lesen: Lesen Sie die Beziehung aus der Standardeingabe im Format „B > A“ und geben Sie an, dass B besser als A ist.
3. Beziehungsverarbeitung:
   • Überprüfen Sie beim Lesen einer neuen Beziehung, ob ein Widerspruch vorliegt (d. h. ob eine zuvor festgelegte Beziehung mit der neuen Beziehung in Konflikt steht).
   • erneuerndistMatrix verwendet den Floyd-Algorithmus, um den kürzesten Weg zwischen allen Ungleichungen zu aktualisieren. Hier wird tatsächlich die „Prioritäts“- oder „Reihenfolge“-Beziehung aktualisiert.
4. Sortiersicherheit prüfen:
   • Überprüfen Sie, ob alle Ungleichungen zusammenhängen, d. h. jeder Punkt kann jeden anderen Punkt erreichen und die Weglänge ist nicht unendlich.
   • Wenn die Sortierung beim Lesen der Beziehung gefunden wird oder die Sortierung nach dem Lesen aller Beziehungen immer noch nicht ermittelt werden kann, werden die entsprechenden Informationen ausgegeben.

Ideen verbessern

• Effizienzverbesserung : Der aktuelle Floyd-Aufruf erfolgt unmittelbar nach dem Hinzufügen jeder neuen Beziehung, was möglicherweise nicht erforderlich ist. Sie können warten, bis alle Beziehungen gelesen wurden, bevor Sie den Floyd-Algorithmus erneut ausführen, um unnötige Berechnungen zu vermeiden.
• Vereinfachen Sie die Logik : Der aktuelle Code ist komplexer bei der Erkennung von Widersprüchen und der Bestimmung der Sortiervervollständigungslogik. Sie können versuchen, die Logik zu vereinfachen, indem Sie beispielsweise intuitivere Datenstrukturen oder algorithmische Schritte verwenden, um diese Bedingungen zu überprüfen.
• Klarheit des Codes: Kann die Klarheit von Kommentaren und der Codestruktur erhöhen und den Code leichter verständlich und wartungsfreundlich machen.