Condivisione della tecnologia

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

Sommario

Algoritmo di Floyd

definizione

Utilizzo

Precauzioni

Idee per la risoluzione dei problemi

I passaggi fondamentali

AcWing 343. Ordinamento

Descrizione della domanda

eseguire il codice

Idee per il codice

Migliorare le idee

Algoritmo di Floyd

definizione

L'algoritmo di Floyd, il nome completo dell'algoritmo di Floyd-Warshall, è un algoritmo di programmazione dinamica utilizzato per risolvere il problema del percorso più breve tra tutte le coppie di vertici nel grafico. È adatto per grafici diretti ponderati e può gestire bordi di peso negativi (ma non grafici contenenti cicli di peso negativi) e può rilevare se sono presenti cicli di peso negativi nel grafico.

Utilizzo

1. Calcola il percorso più breve tra tutte le coppie di vertici: In campi quali l'analisi delle reti sociali, la pianificazione della rete di trasporto, la progettazione della rete di comunicazione, ecc., l'algoritmo di Floyd è una buona scelta quando è necessario calcolare la distanza più breve tra due punti qualsiasi.
2. Rileva cicli di peso negativi: In alcuni scenari applicativi, è necessario assicurarsi che non siano presenti cicli di peso negativi nel grafico, poiché ciò potrebbe indicare qualche anomalia o stato di errore nel sistema.

Precauzioni

• consumo di memoria : La complessità spaziale dell'algoritmo di Floyd è O(n^2), dove n è il numero di vertici nel grafico. Per i grafici su larga scala, questo può diventare un problema.
• complessità temporale: La complessità temporale dell'algoritmo di Floyd è O(n^3). Quando il numero di vertici è elevato, l'algoritmo può diventare molto lento.
• ciclo di peso negativo : Se nel grafico è presente un ciclo di peso negativo, l'algoritmo di Floyd cadrà in un ciclo infinito, poiché a partire da un nodo, la lunghezza del percorso può essere ridotta all'infinito attraverso questo ciclo. Nelle applicazioni pratiche, tali situazioni devono essere prima rilevate e gestite.
• Gli algoritmi possono rilevare cicli di peso negativi:Se durante l'esecuzione dell'algoritmo si riscontra che il percorso più breve da un vertice a se stesso è minore di 0, cioè D[i][i] < 0, allora nel grafico è presente almeno un ciclo di peso negativo, e l'algoritmo non può fornire il risultato corretto del percorso più breve in questo momento.
• Per grafici molto grandi, l'elevata complessità temporale e spaziale dell'algoritmo potrebbe diventare un collo di bottiglia. In questo momento, potrebbe essere necessario prendere in considerazione algoritmi più efficienti o utilizzare strutture dati e tecniche di ottimizzazione più professionali.

Idee per la risoluzione dei problemi

L'idea centrale dell'algoritmo di Floyd è la programmazione dinamica e i suoi passaggi fondamentali sono i seguenti:

1. Inizializzazione: imposta la matrice delle distanze D sulla matrice di adiacenza del grafico, ovvero D[i][j] = peso(i, j); per i != j, se (i, j) non è connesso, allora D[i][j] = ∞; D[i][i] = 0.
2. Programmazione dinamica: per k = da 1 a n, aggiornare D in modo tale che D[i][j] = min(D[i][j], D[i][k] + D[k][j]), che is Controllare se la distanza da i a j può essere accorciata attraverso il nodo intermedio k.
3. Risultato: la matrice D finale contiene le lunghezze del percorso più breve tra tutte le coppie di vertici. Se durante il processo di aggiornamento si verifica un certo D[i][j] < 0 e i != j e D[i][i] < 0, significa che nel grafico è presente un ciclo di peso negativo.

L'implementazione dell'algoritmo di Floyd utilizza solitamente un triplo ciclo. Il ciclo esterno attraversa tutti i vertici intermedi k e i due cicli interni attraversano tutte le coppie di vertici (i, j) per verificare se esiste un percorso più breve.

I passaggi fondamentali

Supponiamo di avere un grafo pesato G contenente n vertici, possiamo utilizzare un array bidimensionaledist[][] per memorizzare la lunghezza del percorso più breve tra ciascuna coppia di vertici. Inizialmente,dist[i][j]è impostato sul peso dell'arco direttamente connesso nel grafico Se non c'è alcun arco direttamente connesso tra i e j, alloradist[i][j]Impostato su infinito (che indica irraggiungibile).

1. inizializzazione : Crea una matrice n×n D, dove D[i][j] è inizializzato al peso dell'arco diretto da i a j nel grafico, o impostato a infinito se non c'è alcun arco diretto tra i e j. Elemento diagonale D[i][i] = 0.

2. programmazione dinamica : Per ogni vertice k (come vertice intermedio), aggiorna il percorso più breve tra ogni coppia di vertici i e j È possibile ottenere un percorso più breve con k come punto intermedio. La formula di aggiornamento è: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Ciò significa che se il percorso da i a j si accorcia passando per k come vertice intermedio, aggiornare D[i][j].

3. Uscita del risultato: Dopo n cicli di iterazioni, ciascun elemento D[i][j] nella matrice D ha la lunghezza del percorso più breve da i a j.

AcWing 343. Ordinamento

Descrizione della domanda

343. Ordinamento - Banca delle domande AcWing

eseguire il codice

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

Idee per il codice

1. inizializzazione: usare undistL'array bidimensionale è inizializzato all'infinito, il che significa che per impostazione predefinita non esiste una relazione di ordine definita tra le disuguaglianze.
2. Leggi l'input: legge la relazione dall'input standard nel formato "B > A", indicando che B è migliore di A.
3. Elaborazione delle relazioni:
   • Quando viene letta una nuova relazione, viene verificato se esiste qualche contraddizione (cioè una relazione precedentemente determinata è in conflitto con la nuova relazione).
   • rinnovaredistMatrix, utilizzando l'algoritmo di Floyd per aggiornare il percorso più breve tra tutte le disuguaglianze, qui sta effettivamente aggiornando la relazione di "priorità" o "ordine".
4. Verificare la certezza dell'ordinamento:
   • Controlla che tutte le disuguaglianze siano correlate, cioè ogni punto può raggiungere ogni altro punto e la lunghezza del percorso non è infinita.
   • Se l'ordinamento viene trovato durante il processo di lettura della relazione, o se dopo aver letto tutte le relazioni non è ancora possibile determinare l'ordinamento, verranno emesse le informazioni corrispondenti.

Migliorare le idee

• Miglioramento dell'efficienza : la chiamata Floyd corrente viene effettuata immediatamente dopo l'aggiunta di ogni nuova relazione, il che potrebbe non essere necessario. Puoi attendere finché tutte le relazioni non siano state lette prima di eseguire nuovamente l'algoritmo di Floyd per ridurre i calcoli non necessari.
• Semplifica la logica : Il codice attuale è più complesso nel rilevare le contraddizioni e nel determinare la logica del completamento dell'ordinamento. Puoi provare a semplificare la logica, ad esempio utilizzando strutture dati più intuitive o passaggi algoritmici per verificare queste condizioni.
• chiarezza del codice: può aumentare la chiarezza dei commenti e della struttura del codice, rendendo il codice più facile da comprendere e mantenere.