प्रौद्योगिकी साझेदारी

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

सामग्रीसूची

फ्लोयड एल्गोरिदम

परिभाषा

प्रयोगः

सावधानताएँ

समस्यानिराकरणविचाराः

मूलभूतपदानि

AcWing 343. क्रमाङ्कनम्

प्रश्नवर्णनम्

run code

संहिताविचाराः

विचारसुधारं कुर्वन्तु

फ्लोयड एल्गोरिदम

परिभाषा

फ्लोयड्-वार्शल् एल्गोरिदम् इत्यस्य पूर्णं नाम फ्लोयड्-एल्गोरिदम् इति गतिशीलप्रोग्रामिंग-एल्गोरिदम् अस्ति यस्य उपयोगः आलेखे सर्वेषां शिखरयुग्मानां मध्ये लघुतममार्गसमस्यायाः समाधानार्थं भवति इदं भारितनिर्देशितलेखानां कृते उपयुक्तं भवति तथा च ऋणात्मकभारधाराः (किन्तु ऋणात्मकभारचक्रयुक्तानि आलेखाः न) सम्भालितुं शक्नोति, तथा च आलेखे ऋणात्मकभारचक्राणि सन्ति वा इति ज्ञातुं शक्नोति

प्रयोगः

1. सर्वेषां शिखरयुग्मानां मध्ये लघुतमं मार्गं गणयन्तु: सामाजिकजालविश्लेषणं, परिवहनजालनियोजनं, संचारजालनिर्माणम् इत्यादिषु क्षेत्रेषु यदा कस्यापि बिन्दुद्वयस्य मध्ये लघुतमं दूरं गणयितुं आवश्यकं भवति तदा फ्लोयड् एल्गोरिदम् उत्तमः विकल्पः भवति
2. नकारात्मकभारचक्राणां अन्वेषणं कुर्वन्तु: केषुचित् अनुप्रयोगपरिदृश्येषु, एतत् सुनिश्चितं कर्तुं आवश्यकं यत् आलेखे नकारात्मकभारचक्राः न सन्ति, यतः एतेन प्रणाल्यां किञ्चित् असामान्यतां वा त्रुटिस्थितिः वा सूचयितुं शक्यते

सावधानताएँ

• स्मृति उपभोगः : फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य अन्तरिक्षजटिलता O(n^2) अस्ति, यत्र n आलेखे शिखरसङ्ख्या अस्ति । बृहत्-प्रमाणस्य आलेखानां कृते एषा समस्या भवितुम् अर्हति ।
• कालजटिलता: फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य समयजटिलता O(n^3) भवति यदा शिखरानाम् संख्या बृहत् भवति तदा एल्गोरिदम् अतीव मन्दं भवितुम् अर्हति ।
• नकारात्मक भार पाश : यदि आलेखे ऋणात्मकं भारचक्रं भवति तर्हि फ्लोयड् इत्यस्य एल्गोरिदम् अनन्तपाशस्य मध्ये पतति, यतः नोड् इत्यस्मात् आरभ्य अस्य चक्रस्य माध्यमेन मार्गस्य दीर्घतां अनन्तरूपेण न्यूनीकर्तुं शक्यते व्यावहारिकप्रयोगेषु एतादृशीनां परिस्थितीनां प्रथमं ज्ञापनं निबन्धनं च आवश्यकम् ।
• एल्गोरिदम् ऋणात्मकभारचक्राणां पत्ताङ्गीकरणं कर्तुं शक्नुवन्ति:यदि एल्गोरिदमस्य निष्पादनकाले ज्ञायते यत् एकस्मात् शिखरात् स्वयमेव यावत् लघुतमः मार्गः 0 इत्यस्मात् न्यूनः अस्ति अर्थात् D[i][i] < 0, तर्हि आलेखे न्यूनातिन्यूनम् एकं ऋणात्मकं भारचक्रं भवति, तथा एल्गोरिदम् अस्मिन् समये सम्यक् लघुतममार्गफलं दातुं न शक्नोति |
• अत्यन्तं बृहत् आलेखानां कृते, एल्गोरिदमस्य उच्चसमयजटिलता, स्थानजटिलता च अड़चनं भवितुम् अर्हति अस्मिन् समये, भवद्भिः अधिककुशल-एल्गोरिदम्-विषये विचारः करणीयः अथवा अधिकव्यावसायिक-दत्तांश-संरचनानां अनुकूलन-तकनीकानां च उपयोगः करणीयः भवितुम् अर्हति

समस्यानिराकरणविचाराः

फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य मूलविचारः गतिशीलप्रोग्रामिंग् अस्ति, तस्य मूलभूतपदार्थाः च निम्नलिखितरूपेण सन्ति ।

1. आरंभीकरणम् : दूरीमात्रिकं D आलेखस्य समीपतामात्रिकायां सेट् कुर्वन्तु, अर्थात् D[i][j] = भारः(i, j) कृते i != j, यदि (i, j) न संबद्धः अस्ति, तर्हि D[i][ j] = ∞ D[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 भवति तर्हि तस्य अर्थः अस्ति यत् आलेखे ऋणात्मकं भारचक्रं भवति

फ्लोयड् इत्यस्य एल्गोरिदम् इत्यस्य कार्यान्वयनम् सामान्यतया त्रिगुणितपाशस्य उपयोगं करोति बाह्यपाशः सर्वान् मध्यवर्तीशिखरान् k भ्रमति, अन्तः पाशद्वयं च सर्वान् शिखरयुग्मान् (i, j) भ्रमति यत् लघुतरः मार्गः अस्ति वा इति

मूलभूतपदानि

मानातु यत् अस्माकं कृते n शिखरयुक्तः भारितः आलेखः G अस्ति, वयं द्विविमीयसरण्याः उपयोगं कर्तुं शक्नुमः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] इति प्रत्येकं तत्त्वं i तः j पर्यन्तं लघुतमं मार्गदीर्घता भवति ।

AcWing 343. क्रमाङ्कनम्

प्रश्नवर्णनम्

343. क्रमाङ्कनम् - AcWing प्रश्नबैङ्कः

run code

#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. आरम्भीकरणम्: प्रयोगः adistद्विविधा सरणी अनन्ततां यावत् आरभ्यते, यस्य अर्थः अस्ति यत् पूर्वनिर्धारितरूपेण असमानतानां मध्ये निश्चितः क्रमसम्बन्धः नास्ति ।
2. निवेशं पठन्तु: मानकनिवेशतः सम्बन्धं "B > A" प्रारूपेण पठन्तु, यत् सूचयति यत् B A इत्यस्मात् श्रेष्ठः अस्ति ।
3. सम्बन्ध संसाधन:
   • यदा नूतनः सम्बन्धः पठ्यते तदा तस्य परीक्षणं भवति यत् किमपि विरोधः अस्ति वा (अर्थात् पूर्वनिर्धारितः सम्बन्धः नूतनसम्बन्धेन सह विग्रहं करोति)।
   • नवीकरणम्distMatrix, सर्वेषां असमानतानां मध्ये लघुतममार्गं अद्यतनीकर्तुं Floyd इत्यस्य एल्गोरिदम् इत्यस्य उपयोगेन, अत्र वस्तुतः "प्राथमिकता" अथवा "क्रमण" सम्बन्धं अद्यतनं करोति ।
4. क्रमणस्य निश्चयं पश्यन्तु:
   • सर्वाणि असमानतानि सम्बद्धानि सन्ति इति पश्यन्तु अर्थात् प्रत्येकं बिन्दुः प्रत्येकं अन्यं बिन्दुं प्राप्तुं शक्नोति तथा च मार्गदीर्घता अनन्तं नास्ति।
   • यदि सम्बन्धपठनप्रक्रियायां क्रमणं लभ्यते, अथवा सर्वेषां सम्बन्धानां पठनानन्तरं क्रमणं अद्यापि निर्धारयितुं न शक्यते, तर्हि तत्सम्बद्धा सूचना निर्गमिष्यति

विचारसुधारं कुर्वन्तु

• दक्षतासुधारः : वर्तमानः floyd call प्रत्येकं नूतनं सम्बन्धं योजितस्य तत्क्षणमेव क्रियते, यत् आवश्यकं न भवेत्। अनावश्यकगणना न्यूनीकर्तुं पुनः फ्लोयड् इत्यस्य एल्गोरिदम् कर्तुं पूर्वं यावत् सर्वे सम्बन्धाः पठिताः न भवन्ति तावत् प्रतीक्षितुं शक्नुवन्ति ।
• तर्कं सरलं कुरुत : वर्तमानसङ्केतः विरोधाभासानां पत्ताङ्गीकरणे समाप्तेः क्रमणस्य तर्कस्य निर्धारणे च अधिकं जटिलः अस्ति । भवान् तर्कं सरलीकर्तुं प्रयतितुं शक्नोति, यथा एतासां शर्तानाम् परीक्षणार्थं अधिकानि सहजज्ञानयुक्तानि दत्तांशसंरचनानि अथवा एल्गोरिदमिकपदार्थानाम् उपयोगः ।
• कोड स्पष्टता: टिप्पणीनां स्पष्टतां कोडसंरचनायाः च वर्धनं कर्तुं शक्नोति, येन कोडस्य अवगमनं, परिपालनं च सुलभं भवति ।