Teknologian jakaminen

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

Sisällysluettelo

Floyd-algoritmi

määritelmä

Käyttö

Varotoimenpiteet

Ideoita ongelmanratkaisuun

Perusvaiheet

AcWing 343. Lajittelu

Kysymyksen kuvaus

suorita koodi

Koodi ideoita

Paranna ideoita

Floyd-algoritmi

määritelmä

Floydin algoritmi, Floyd-Warshall-algoritmin koko nimi, on dynaaminen ohjelmointialgoritmi, jota käytetään ratkaisemaan lyhimmän polun ongelma graafin kaikkien pisteparien välillä. Se sopii painotetuille suunnatuille kaavioille ja pystyy käsittelemään negatiivisen painotuksen reunoja (mutta ei negatiivisia painosyklejä sisältäviä kaavioita) ja voi havaita, onko kaaviossa negatiivisia painosyklejä.

Käyttö

1. Laske lyhin polku kaikkien kärkiparien välillä: Aloilla, kuten sosiaalisten verkostojen analyysi, liikenneverkkojen suunnittelu, viestintäverkkojen suunnittelu jne., Floyd-algoritmi on hyvä valinta, kun on tarpeen laskea lyhin etäisyys minkä tahansa kahden pisteen välillä.
2. Tunnista negatiiviset painosyklit: Joissakin sovellusskenaarioissa on varmistettava, että kaaviossa ei ole negatiivisia painosyklejä, koska tämä voi viitata johonkin epänormaaliin tai virhetilaan järjestelmässä.

Varotoimenpiteet

• muistin kulutus : Floydin algoritmin avaruuden monimutkaisuus on O(n^2), missä n on graafin kärkien lukumäärä. Suuren mittakaavan kaavioissa tästä voi tulla ongelma.
• aika monimutkaisuus: Floydin algoritmin aikamonimutkaisuus on O(n^3), kun pisteiden lukumäärä on suuri, algoritmista voi tulla hyvin hidas.
• negatiivinen painosilmukka : Jos kaaviossa on negatiivinen painosykli, Floydin algoritmi putoaa äärettömään silmukkaan, koska solmusta alkaen polun pituutta voidaan lyhentää loputtomasti tämän jakson aikana. Käytännön sovelluksissa tällaiset tilanteet täytyy havaita ja käsitellä ensin.
• Algoritmit voivat havaita negatiiviset painosyklit:Jos algoritmia suoritettaessa havaitaan, että lyhin polku kärjestä itseensä on pienempi kuin 0, eli D[i][i] < 0, niin kaaviossa on ainakin yksi negatiivinen painosykli, ja algoritmi ei voi antaa oikeaa lyhimmän polun tulosta tällä hetkellä.
• Erittäin suurille kaavioille algoritmin suuri aika- ja tilamonimutkaisuus voi muodostua pullonkaulaksi. Tällä hetkellä saatat joutua harkitsemaan tehokkaampia algoritmeja tai käyttämään ammattimaisempia tietorakenteita ja optimointitekniikoita.

Ideoita ongelmanratkaisuun

Floydin algoritmin ydinajatus on dynaaminen ohjelmointi, ja sen perusvaiheet ovat seuraavat:

1. Alustus: Aseta etäisyysmatriisi D graafin viereisyysmatriisiin, eli D[i][j] = paino(i, j) i != j:lle, jos (i, j) ei ole kytketty, niin D[i][ j] = ∞; D[i][i] = 0.
2. Dynaaminen ohjelmointi: Jos k = 1 - n, päivitä D siten, että D[i][j] = min(D[i][j], D[i][k] + D[k][j]), että is Tarkista, voidaanko etäisyyttä i:stä j:een lyhentää välisolmun k kautta.
3. Tulos: Lopullinen D-matriisi sisältää lyhyimmän polun pituudet kaikkien kärkiparien välillä. Jos on tietty D[i][j] < 0 ja i != j, ja D[i][i] < 0 tapahtuu päivitysprosessin aikana, se tarkoittaa, että kaaviossa on negatiivinen painosykli.

Floydin algoritmin toteutuksessa käytetään yleensä kolmoissilmukkaa. Ulompi silmukka kulkee kaikkien välipisteiden k läpi ja kaksi sisäsilmukkaa kaikkien kärkiparien (i, j) läpi tarkistaakseen, onko olemassa lyhyempi polku.

Perusvaiheet

Oletetaan, että meillä on painotettu graafi G, joka sisältää n kärkeä, voimme käyttää kaksiulotteista taulukkoadist[][] tallentaaksesi lyhimmän polun pituuden kunkin kärkiparin välille. Aluksidist[i][j]on asetettu graafin suoraan yhdistetyn reunan painoon. Jos i:n ja j:n välillä ei ole suoraan kytkettyä reunaa, niindist[i][j]Aseta äärettömään (ilmaisee tavoittamatonta).

1. alustus : Luo n×n matriisi D, jossa D[i][j] alustetaan graafin i:n ja j:n suoran reunan painoon tai asetetaan äärettömyyteen, jos i:n ja j:n välillä ei ole suoraa reunaa. Diagonaalielementti D[i][i] = 0.

2. dynaaminen ohjelmointi : Päivitä jokaiselle kärkipisteelle k (välipisteenä) lyhin polku kunkin kärkiparin i ja j välillä. On mahdollista saada lyhyempi polku k välipisteenä. Päivityskaava on: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Tämä tarkoittaa, että jos polku i:stä j:hen lyhenee k:n kautta välipisteenä, päivitä D[i][j].

3. Tulostulostus: n iteraatiokierroksen jälkeen jokainen matriisin D elementti D[i][j] on lyhin polun pituus i:stä j:hen.

AcWing 343. Lajittelu

Kysymyksen kuvaus

343. Lajittelu - AcWingin kysymyspankki

suorita koodi

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

Koodi ideoita

1. alustus: KäytädistKaksiulotteinen taulukko alustetaan äärettömyyteen, mikä tarkoittaa, että epäyhtälöiden välillä ei ole oletusarvoisesti määrättyä järjestyssuhdetta.
2. Lue syöttö: Lue suhde vakiosyötteestä muodossa "B > A", mikä osoittaa, että B on parempi kuin A.
3. Suhteen käsittely:
   • Kun uutta suhdetta luetaan, tarkistetaan, onko siinä ristiriitaa (eli aiemmin määritetty suhde on ristiriidassa uuden suhteen kanssa).
   • uusiadistMatrix, joka käyttää Floydin algoritmia päivittääkseen lyhimmän polun kaikkien epätasa-arvojen välillä, tässä itse asiassa päivittää "prioriteetti" tai "järjestys" -suhdetta.
4. Tarkista lajitteluvarmuus:
   • Tarkista, että kaikki epäyhtälöt liittyvät toisiinsa, eli jokainen piste pääsee joka toiseen pisteeseen ja polun pituus ei ole ääretön.
   • Jos lajittelu löydetään suhteen lukuprosessin aikana tai lajittelua ei vieläkään voida määrittää kaikkien suhteiden lukemisen jälkeen, vastaavat tiedot tulostetaan.

Paranna ideoita

• Tehokkuuden parantaminen : Nykyinen floyd-kutsu tehdään välittömästi jokaisen uuden suhteen lisäämisen jälkeen, mikä ei välttämättä ole tarpeen. Voit odottaa, kunnes kaikki suhteet on luettu, ennen kuin suoritat Floydin algoritmin uudelleen tarpeettomien laskelmien vähentämiseksi.
• Yksinkertaista logiikkaa : Nykyinen koodi on monimutkaisempi havaitsemaan ristiriitoja ja määrittämään lajittelun loppuunsaattamisen logiikan. Voit yrittää yksinkertaistaa logiikkaa, esimerkiksi käyttämällä intuitiivisempia tietorakenteita tai algoritmisia vaiheita näiden ehtojen tarkistamiseen.
• koodin selkeys: Voi selventää kommentteja ja koodirakennetta, mikä tekee koodista helpompi ymmärtää ja ylläpitää.