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

फ्लोयड् इत्यस्य एल्गोरिदम् - AcWing 343. क्रमणं

2024-07-12

한어Русский язык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

  1. #include <algorithm>
  2. #include <bits/stdc++.h>
  3. #include <iostream>
  4. using namespace std;
  5. #define PII pair<int, int>
  6. #define fi first
  7. #define se second
  8. #define endl 'n'
  9. map<int, int> mp;
  10. const int N = 210, mod = 1e9 + 7;
  11. int T, n, m, k;
  12. int a[N], dist[N][N];
  13. PII ans[N];
  14. void floyd(int x) // 以 x 为中转点,更新其他点。
  15. {
  16. for (int i = 1; i <= n; i++)
  17. for (int j = 1; j <= n; j++)
  18. dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
  19. }
  20. bool pd() // 判断是否所有点都已确定
  21. {
  22. for (int i = 1; i <= n; i++) {
  23. int cnt = 0;
  24. for (int j = 1; j <= n; j++)
  25. if (dist[i][j] != 1e9)
  26. cnt++; // 当前点能到达的点数
  27. ans[i] = {cnt, i};
  28. for (int j = 1; j <= n; j++)
  29. if (i != j && dist[j][i] != 1e9)
  30. cnt++; // 能到达当前点的点数
  31. if (cnt != n)
  32. return 0;
  33. }
  34. sort(ans + 1, ans + n + 1);
  35. return 1;
  36. }
  37. int main() {
  38. while (cin >> n >> m && n) {
  39. for (int i = 1; i <= n; i++)
  40. for (int j = 1; j <= n; j++)
  41. if (i != j)
  42. dist[i][j] = 1e9;
  43. int flag = 0;
  44. for (int i = 1; i <= m; i++) {
  45. char a, t, b;
  46. cin >> a >> t >> b;
  47. int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
  48. if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y,出现矛盾
  49. {
  50. printf("Inconsistency found after %d relations.n", i);
  51. flag = 1;
  52. }
  53. dist[y][x] = 1;
  54. floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
  55. if (!flag && pd()) { // 发现所有点都已确定
  56. printf("Sorted sequence determined after %d relations: ", i);
  57. for (int i = 1; i <= n; i++)
  58. cout << char(ans[i].se + 'A' - 1);
  59. printf(".n");
  60. flag = 1;
  61. }
  62. }
  63. if (!flag)
  64. printf("Sorted sequence cannot be determined.n"); // 无法确定
  65. }
  66. return 0;
  67. }

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

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

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

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