Κοινή χρήση τεχνολογίας

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

Πίνακας περιεχομένων

Αλγόριθμος Floyd

ορισμός

Χρήση

Προφυλάξεις

Ιδέες επίλυσης προβλημάτων

Τα βασικά βήματα

AcWing 343. Ταξινόμηση

Περιγραφή ερώτησης

κώδικας εκτέλεσης

Ιδέες κώδικα

Βελτιώστε τις ιδέες

Αλγόριθμος Floyd

ορισμός

Ο αλγόριθμος Floyd, το πλήρες όνομα του αλγόριθμου Floyd-Warshall, είναι ένας δυναμικός αλγόριθμος προγραμματισμού που χρησιμοποιείται για την επίλυση του προβλήματος της συντομότερης διαδρομής μεταξύ όλων των ζευγών κορυφών του γραφήματος. Είναι κατάλληλο για σταθμισμένα κατευθυνόμενα γραφήματα και μπορεί να χειριστεί ακμές αρνητικού βάρους (αλλά όχι γραφήματα που περιέχουν κύκλους αρνητικού βάρους) και μπορεί να ανιχνεύσει εάν υπάρχουν κύκλοι αρνητικού βάρους στο γράφημα.

Χρήση

1. Υπολογίστε τη συντομότερη διαδρομή μεταξύ όλων των ζευγών κορυφών: Σε τομείς όπως η ανάλυση κοινωνικών δικτύων, ο σχεδιασμός δικτύων μεταφορών και ο σχεδιασμός του δικτύου επικοινωνίας, ο αλγόριθμος Floyd είναι μια καλή επιλογή όταν είναι απαραίτητο να υπολογιστεί η μικρότερη απόσταση μεταξύ οποιωνδήποτε δύο σημείων.
2. Εντοπίστε αρνητικούς κύκλους βάρους: Σε ορισμένα σενάρια εφαρμογών, είναι απαραίτητο να διασφαλιστεί ότι δεν υπάρχουν αρνητικοί κύκλοι βάρους στο γράφημα, καθώς αυτό μπορεί να υποδεικνύει κάποια ανωμαλία ή κατάσταση σφάλματος στο σύστημα.

Προφυλάξεις

• κατανάλωση μνήμης : Η διαστημική πολυπλοκότητα του αλγορίθμου του Floyd είναι O(n^2), όπου n είναι ο αριθμός των κορυφών στο γράφημα. Για γραφήματα μεγάλης κλίμακας, αυτό μπορεί να γίνει πρόβλημα.
• χρονική πολυπλοκότητα: Η χρονική πολυπλοκότητα του αλγόριθμου του Floyd είναι O(n^3), όταν ο αριθμός των κορυφών είναι μεγάλος, ο αλγόριθμος μπορεί να γίνει πολύ αργός.
• βρόχος αρνητικού βάρους : Εάν υπάρχει αρνητικός κύκλος βάρους στο γράφημα, ο αλγόριθμος του Floyd θα πέσει σε έναν άπειρο βρόχο, επειδή ξεκινώντας από έναν κόμβο, το μήκος της διαδρομής μπορεί να μειωθεί άπειρα σε αυτόν τον κύκλο. Σε πρακτικές εφαρμογές, τέτοιες καταστάσεις πρέπει να ανιχνεύονται και να αντιμετωπίζονται πρώτα.
• Οι αλγόριθμοι μπορούν να ανιχνεύσουν αρνητικούς κύκλους βάρους:Εάν κατά την εκτέλεση του αλγορίθμου διαπιστωθεί ότι η συντομότερη διαδρομή από μια κορυφή προς τον εαυτό της είναι μικρότερη από 0, δηλαδή D[i][i] < 0, τότε υπάρχει τουλάχιστον ένας αρνητικός κύκλος βάρους στο γράφημα, και ο αλγόριθμος δεν μπορεί να δώσει το σωστό αποτέλεσμα της συντομότερης διαδρομής αυτή τη στιγμή.
• Για πολύ μεγάλα γραφήματα, η υψηλή χρονική πολυπλοκότητα και η πολυπλοκότητα του χώρου του αλγορίθμου μπορεί να αποτελέσουν εμπόδιο.

Ιδέες επίλυσης προβλημάτων

Η βασική ιδέα του αλγορίθμου του Floyd είναι ο δυναμικός προγραμματισμός και τα βασικά του βήματα είναι τα εξής:

1. Αρχικοποίηση: Ορίστε τον πίνακα απόστασης D στον πίνακα γειτνίασης του γραφήματος, δηλαδή, D[i][j] = βάρος (i, j), εάν το (i, j) δεν είναι συνδεδεμένο, τότε D[i][ j] = ∞ D[i][i] = 0.
2. Δυναμικός προγραμματισμός: Για k = 1 έως n, ενημερώστε το D έτσι ώστε D[i][j] = min(D[i][j], D[i][k] + D[k][j]), ώστε is Ελέγξτε εάν η απόσταση από το i στο j μπορεί να μειωθεί μέσω του ενδιάμεσου κόμβου k.
3. Αποτέλεσμα: Ο τελικός πίνακας D περιέχει τα μικρότερα μήκη διαδρομής μεταξύ όλων των ζευγών κορυφών. Εάν υπάρχει ένα συγκεκριμένο D[i][j] < 0 και i != j, και το D[i][i] < 0 εμφανίζεται κατά τη διαδικασία ενημέρωσης, σημαίνει ότι υπάρχει ένας αρνητικός κύκλος βάρους στο γράφημα.

Η υλοποίηση του αλγόριθμου του Floyd χρησιμοποιεί συνήθως έναν τριπλό βρόχο Ο εξωτερικός βρόχος διασχίζει όλες τις ενδιάμεσες κορυφές k και οι δύο εσωτερικοί βρόχοι διασχίζουν όλα τα ζεύγη κορυφών (i, j) για να ελέγξουν αν υπάρχει μικρότερη διαδρομή.

Τα βασικά βήματα

Ας υποθέσουμε ότι έχουμε ένα σταθμισμένο γράφημα G που περιέχει n κορυφές, μπορούμε να χρησιμοποιήσουμε έναν δισδιάστατο πίνακαdist[][] για να αποθηκεύσετε το μικρότερο μήκος διαδρομής μεταξύ κάθε ζεύγους κορυφών. Αρχικά,dist[i][j]ορίζεται στο βάρος της άμεσα συνδεδεμένης ακμής στο γράφημα Εάν δεν υπάρχει άμεσα συνδεδεμένη ακμή μεταξύ i και j, τότεdist[i][j]Ορίστηκε στο άπειρο (που υποδεικνύει ότι δεν είναι προσβάσιμο).

1. αρχικοποίηση : Δημιουργήστε έναν n×n πίνακα D, όπου το D[i][j] αρχικοποιείται στο βάρος της άμεσης ακμής από i έως j στο γράφημα ή ορίζεται στο άπειρο εάν δεν υπάρχει άμεση ακμή μεταξύ i και j. Διαγώνιο στοιχείο D[i][i] = 0.

2. δυναμικός προγραμματισμός : Για κάθε κορυφή k (ως ενδιάμεση κορυφή), ενημερώστε τη συντομότερη διαδρομή μεταξύ κάθε ζεύγους κορυφών i και j Είναι δυνατόν να λάβετε μια συντομότερη διαδρομή με το k ως ενδιάμεσο σημείο. Ο τύπος ενημέρωσης είναι: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Αυτό σημαίνει ότι εάν η διαδρομή από το i στο j γίνει μικρότερη μέσω του k ως ενδιάμεση κορυφή, ενημερώστε το D[i][j].

3. Έξοδος αποτελέσματος: Μετά από n γύρους επαναλήψεων, κάθε στοιχείο D[i][j] στον πίνακα D είναι το μικρότερο μήκος διαδρομής από το i έως το j.

AcWing 343. Ταξινόμηση

Περιγραφή ερώτησης

343. Ταξινόμηση - Τράπεζα Ερωτήσεων AcWing

κώδικας εκτέλεσης

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

Ιδέες κώδικα

1. αρχικοποίηση: χρησιμοποίησε έναdistΟ δισδιάστατος πίνακας αρχικοποιείται στο άπειρο, πράγμα που σημαίνει ότι δεν υπάρχει σχέση ορισμένης τάξης μεταξύ των ανισοτήτων από προεπιλογή.
2. Ανάγνωση εισόδου: Διαβάστε τη σχέση από την τυπική είσοδο στη μορφή "B > A", υποδεικνύοντας ότι το B είναι καλύτερο από το A.
3. Επεξεργασία σχέσεων:
   • Όταν διαβάζεται μια νέα σχέση, ελέγξτε αν υπάρχει κάποια αντίφαση (δηλαδή, μια σχέση που καθορίστηκε προηγουμένως έρχεται σε σύγκρουση με τη νέα σχέση).
   • ανανεώνωdistΤο Matrix, χρησιμοποιώντας τον αλγόριθμο του Floyd για να ενημερώσει τη συντομότερη διαδρομή μεταξύ όλων των ανισοτήτων, εδώ στην πραγματικότητα ενημερώνει τη σχέση "προτεραιότητας" ή "παραγγελίας".
4. Ελέγξτε τη βεβαιότητα ταξινόμησης:
   • Ελέγξτε ότι όλες οι ανισότητες σχετίζονται, δηλ. κάθε σημείο μπορεί να φτάσει σε κάθε άλλο σημείο και το μήκος της διαδρομής δεν είναι άπειρο.
   • Εάν η ταξινόμηση βρεθεί κατά τη διαδικασία ανάγνωσης της σχέσης ή η ταξινόμηση εξακολουθεί να μην μπορεί να προσδιοριστεί μετά την ανάγνωση όλων των σχέσεων, θα βγουν οι αντίστοιχες πληροφορίες.

Βελτιώστε τις ιδέες

• Βελτίωση της αποτελεσματικότητας : Η τρέχουσα κλήση floyd πραγματοποιείται αμέσως μετά την προσθήκη κάθε νέας σχέσης, η οποία μπορεί να μην είναι απαραίτητη. Μπορείτε να περιμένετε μέχρι να διαβαστούν όλες οι σχέσεις πριν εκτελέσετε ξανά τον αλγόριθμο του Floyd για να μειώσετε τους περιττούς υπολογισμούς.
• Απλοποιήστε τη λογική : Ο τρέχων κώδικας είναι πιο περίπλοκος στον εντοπισμό αντιφάσεων και στον προσδιορισμό της λογικής της ολοκλήρωσης της ταξινόμησης. Μπορείτε να προσπαθήσετε να απλοποιήσετε τη λογική, όπως να χρησιμοποιήσετε πιο εύχρηστες δομές δεδομένων ή αλγοριθμικά βήματα για να ελέγξετε αυτές τις συνθήκες.
• σαφήνεια κώδικα: Μπορεί να αυξήσει τη σαφήνεια των σχολίων και τη δομή του κώδικα, καθιστώντας τον κώδικα ευκολότερο να κατανοηθεί και να διατηρηθεί.