ഡൈനാമിക് കണക്റ്റിവിറ്റി പ്രശ്നം

ഇതൊരു രസകരമായ കമ്പ്യൂട്ടർപ്രശ്നമാണൂ. ഈ പ്രശ്നത്തിൽ ഒരു കൂട്ടം വസ്തുക്കൾ തമ്മിൽ നേരിട്ടോ അല്ലാതെയോ ബന്ധമുണ്ടോ എന്നു മനസ്സിലാക്കുക, വസ്തുക്കൾ തമ്മിൽ ബന്ധങ്ങൾ/പാത്ത്/കണക്ഷൻ സൃഷ്ടിയ്ക്കുക തുടങ്ങിയ വിഷയങ്ങളെ കൈകാര്യം ചെയ്യുന്നു. നിരവധി കമ്പ്യൂട്ടർഅൽഗരിതങ്ങൾ ഈ പ്രശ്നത്തെ വിശദീകരിയ്ക്കാനും, പരിഹരിയ്ക്കാനുമായി വികസിപ്പിച്ചെടുത്തിട്ടുണ്ട്.

ഉദാഹരണമായി 0 1 2 3 4 തുടങ്ങിയവ ഒരു കൂട്ടം വസ്തുക്കളാണെന്നിരിയ്ക്കട്ടെ.

Union(0,4) എന്ന ഫൺക്ഷൻ പൂജ്യത്തിനും, നാലിനും ഇടയിൽ ബന്ധിപ്പിയ്കുന്ന പാലം പണിയുന്നു. Union(1,3) എന്ന ഫൺക്ഷൻ ഒന്നിനും, മൂന്നിനും ഇടയിൽ ബന്ധിപ്പിയ്കുന്ന പാലം പണിയുന്നു.

Connected(0,4) എന്ന ഫൺക്ഷൻ പൂജ്യത്തിനും നാലിനും ഇടയിൽ നേരിട്ടോ അല്ലാതെയോ ബന്ധമുണ്ടോ എന്നു പരിശൊധിയ്ക്കുന്നു. (ഉത്തരം അതെ എന്നാണല്ലോ.)

Connected(1,4) എന്ന ഫൺക്ഷൻ ഒന്നിനും നാലിനും ഇടയിൽ നേരിട്ടോ അല്ലാതെയോ ബന്ധമുണ്ടോ എന്നു പരിശൊധിയ്ക്കുന്നു. (ഉത്തരം അല്ലാ എന്നാണല്ലോ.)

Union(1,4) എന്ന ഫൺക്ഷൻ ഒന്നിനും, നാലിനും ഇടയിൽ ബന്ധിപ്പിയ്കുന്ന പാലം പണിയുന്നു.(തദ്വാരാ 0,1,3,4 എന്ന വസ്തുക്കൾ തമ്മിൽ ബന്ധപ്പെടുന്നു! 0 3 എന്ന വസ്തുക്കൾ നേരിട്ടല്ലാതെയാണൂ ബന്ധപ്പെട്ടിരിയ്ക്കുന്നത്.)

ഈ പ്രശ്നത്തിന്റെ പ്രാധാന്യം

നാം നിത്യേനയെന്ന വണ്ണം ഇടപെടുന്ന പല കാര്യങ്ങളും ഈ പ്രശ്നവുമായി ബന്ധപ്പെട്ടാണിരിയ്ക്കുന്നത്! ചുവട്ടിലുള്ളവ ചില ഉദാഹരണങ്ങൾ മാത്രം

• ഒരു ഡിജിറ്റൽ ഫോട്ടൊയിലെ പിക്സലുകൾ
• ഒരു നെറ്റ്വർക്കിലെ കംബ്യൂട്ടറുകൾ
• സൊഷ്യൽ നെറ്റ്വർക്കിലെ സുഹ്രുത്തുക്കൾ
• ഒരു ചിപ്പിലെ ട്രാൻസിസ്റ്ററുകൾ
• പെർകൊലേഷൻ പ്രശ്നങ്ങൾ

പ്രശ്നപരിഹാരം

ഏറ്റവും മികച്ച രീതിയിൽ ഈ പ്രശ്നത്തെ പരിഹരിയ്ക്കുക എന്നത് ആ കമ്പ്യൂട്ടർ എഞ്ചിനീയറുടെ മുന്നിലുള്ള വെല്ലുവിളി. പലവിധത്തിലുള്ള അൽഗരിതങ്ങളും ഇതിനായി അവർ വികസിപ്പിച്ചെടുത്തിട്ടുണ്ട്. ചുവടെ കൊടുത്തിരിയ്ക്കുന്നത് അത്തരം ചില അൽഗരിതങ്ങളാണു. ഈ അൽഗരിതങ്ങളോരോന്നും മേൽ ചൊന്ന രണ്ട് കർത്തവ്യങ്ങളും(union, connected) ചെയ്യുന്നവയാണു. മെച്ചപ്പെട്ട രീതിയിൽ ഇവ ചെയ്യുന്നതിനായി ഈ അൽഗരിതങ്ങളോരോന്നും വസ്തുക്കളെ പ്രത്യേക രീതിയിൽ ക്രമീകരിക്കുന്നു.

1. ക്വിക്ക് ഫൈൻഡ് അൽഗരിതം (പാലമുണ്ടോന്ന് പെട്ടെന്ന് പറയഡോ അൽഗരിതം)
2. ക്വിക്ക് കണക്റ്റ് അൽഗരിതം (പെട്ടെന്ന് പാലം പണിയഡോ അൽഗരിതം)
3. വെയിഡ് ക്വിക്ക് കണക്റ്റ് അൽഗരിതം (പെട്ടെന്ന് ചെറിയ പാലം പണിയഡോ അൽഗരിതം)
4. കംബ്രസിഡ് പാത്ത് ക്വിക്ക് കണക്റ്റ് അൽഗരിതം (പെട്ടെന്ന് കൊറച്ചൂടെ ചെറിയ പാലം പണിയഡോ അൽഗരിതം)

കണക്ഷനുമായി ബന്ധപെട്ട ചില നിയമങ്ങൾ

• ഓരോ വസ്തുവും അതത് വസ്തുവായി സ്വയം ബന്ധപ്പെട്ടിരിയ്ക്കുന്നു.
• ഒരു വസ്തു p മറ്റൊരു വസ്തു q വുമായി ബന്ധപ്പെട്ടിരിക്കുന്നുവെങ്കിൽ, q എന്ന വസ്തു p യുമായി തിരിച്ചും ബന്ധപ്പെട്ടിരിയ്ക്കുന്നു.
• ഒരു വസ്തു p മറ്റൊരു വസ്തു q വുമായി ബന്ധപ്പെട്ടിരിക്കുന്നു, q എന്ന വസ്തു r എന്ന മറ്റൊരു വസ്തുമായി ബന്ധപ്പെട്ടിരിയ്ക്കുന്നുവെങ്കിൽ, p എന്ന വസ്തു r എന്ന വസ്തുവുമായിയും ബന്ധപ്പെട്ടിരിയ്ക്കുന്നു.

ക്വിക്ക് ഫൈൻഡ് അൽഗരിതം (ഈഗർ അൽഗരിതം)

യൂണിയൻ, കണക്റ്റഡ് എന്ന രണ്ട് കർത്തവ്യങ്ങളും ഈ അൽഗരിതം ചെയ്യുന്നുണ്ടെങ്കിലും, രണ്ട് വസ്തുക്കൾ തമ്മിൽ നേരിട്ടോ അല്ലാതെയോ ബന്ധമുണ്ടോയെന്ന്(കണക്റ്റ്ഡ് എന്ന് വിശേഷിപ്പിച്ച ഓപ്പറേഷൻ) പരിശോധിക്കുകയെന്നതാണീ അൽഗരിതത്തിന്റെ പ്രധാന ഉദ്ദേശലക്ഷ്യം. (“പാലമുണ്ടോന്ന് പെട്ടെന്ന് പറയഡോ അൽഗരിതം” എന്നീ അൽഗരിതത്തെ വേണമെങ്കിൽ വിശേഷിപ്പിയ്ക്കാം.)

• ഈ അൽഗരിത പ്രകാരം വസ്തുക്കളെ ഒരു പ്രത്യേകരീതിയിൽ ക്രമീകരിയ്ക്കുന്നു. ഇപ്രകാരം ക്രമീകരിയ്ക്കാൻ അറേ എന്ന ഡാറ്റാസ്ട്രക്ച്ചർ ഉപയോഗിയ്ക്കുന്നു.
• (അത്തരം ഒരു ക്രമീകരണത്തിന്റെ ഫലമായി,) രണ്ട് വസ്തുക്കൾ p,q എന്നിവയ്ക്ക് ഒരേ അറേ വാല്യുവാണുള്ളതെങ്കിൽ മാത്രം അവ തമ്മിൽ ബന്ധന്മുണ്ടാകൂ. അഥവാ p,q എന്നീവസ്തുക്കൾ തമ്മിൽ ബന്ധമുണ്ടാവണമെങ്കിൽ അവ ഉൾക്കൊള്ളുന്ന അറേയിൽ ഒരേ വാല്യുവാകണം ഉണ്ടാകേണ്ടത്.

ഉദാഹരണം

Id[] എന്ന അറയിൽ 10 അക്കങ്ങൾ കൊള്ളാമെന്നിരിയ്ക്കട്ടെ. അറേയിലെ വാല്യുകൾ താഴെകൊടുത്തിര്യ്കുന്ന പോലെയാണു.

സ്ഥാനം     0 1 2 3 4 5 6 7 8 9

Id[]         0 1 1 8 8 0 0 1 8 8

Id[0], id[5], id[6] എന്നീ അറേ വാല്യുക്കൾ തുല്യമാണു. അതായത്, 0, 5, 6 എന്നീ വസ്തുക്കൾ/ പരസ്പരം ബന്ധട്ട്റ്റിരിയ്ക്കുന്നു!

അതു പോലെ Id[1], id[2], id[7] എന്നീ അറേ വാല്യുക്കൾ തുല്യമാണു. അതായത്, 1, 2, 7 എന്നീ വസ്തുക്കൾ/ പരസ്പരം ബന്ധട്ട്റ്റിരിയ്ക്കുന്നു!

അതു പോലെ Id[3], id[4], id[8], id[9] എന്നീ അറേ വാല്യുക്കൾ തുല്യമാണു. അതായത്, 3, 4, 8, 9 എന്നീ വസ്തുക്കൾ/ പരസ്പരം ബന്ധട്ട്റ്റിരിയ്ക്കുന്നു!

അൽഗരിതം

class QuickFind
{        int[] Id;
        public QuickFind(int n)
        {
            Id = new int[n];
            for (int i = 0; i < Id.Length; i++)
            {
                Id[i] = i;
            }
        }

        public bool Connected(int p, int q)
        {
            return Id[p] == Id[q];
        }

        public void Union(int p, int q)
        {
            int pIndex = Id[p];
            int qIndex = Id[q];
            for (int i = 0; i < Id.Length; i++)
            {
                if (Id[i] == pIndex)
                    Id[i] = qIndex;
            }
        }
}

വിശദീകരണം

Connected ഫണക്ഷൻ രണ്ട് വസ്തുക്കൾ തമ്മിൽ ബന്ധമുണ്ടോയെന്ന് മാത്രം പരിശോധിയ്ക്കുന്നു. മുൻ ചൊന്ന ഉദാഹരണത്തിൽ വിശദീകരിച്ചത് പോലെ അറേയിലെ p ഇന്ദെക്സിലും, q ഇന്ദെക്സിലും ഒരേ വാല്യു ഉണ്ടോ എന്ന് പരിശോധിച്ചാണിത് നടപ്പിലാക്കുന്നത്.

Union ഫൺക്ഷൻ ബന്ധപ്പെടുത്തേണ്ട വസ്തുക്കളിൽ ഒരേ അറേ വാല്യുവരത്തക്കവണ്ണം ഡാറ്റാസ്റ്റ്രക്ച്ചറിനെ മൊത്തത്തിൽ പുന:ക്രമീകരിയ്ക്കുന്നു. അതായത് p, q എന്നിവ ബന്ധിപ്പിയ്ക്കണമെന്നിരിയ്ക്കട്ടെ, അറേയിലെ p ഇന്ദെക്സിലും, q ഇന്ദെക്സിലും ഒരേ വാല്യുവരത്തക്കവണ്ണം മൊത്തം അറേവാല്യുവും പുന:ക്രമീകരിയ്ക്കുന്നു.

അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത

Connected ഫൺക്ഷൻ വളരെ എളുപ്പമാണൂ. അതിന്റെ സങ്കീർണ്ണത/കോംബ്ലക്സിറ്റി O(1) ആണു.

അതേ സമയം union ഫൺക്ഷൻ വളരെ കുഴപ്പമേറിയതാണൂ. ഓരോ ബന്ധപ്പെടുത്തലിനും, അറേ മൊത്തത്തിൽ ഒരിക്കലൂടെ കടന്നു പോയി മാറ്റങ്ങൾ വരുത്തേണ്ടതായി വരുന്നു. അപ്പോൾ N വസ്തുക്കൾ തമ്മിൽ ബന്ധപ്പെടുത്തണമെങ്കിൽ N*N അതായത് N^2 തവണ അറേയിലൂടെ കടന്ന് പോകേണ്ടതായി വരുന്നു. അതായത്, അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത O(N^2) ആണു. വളരെ മോശപ്പെട്ടതെന്ന് വിളിയ്ക്കാവുന്ന ഒരു പ്രശ്നപരിഹാരമാർഗ്ഗമാണിതെന്നതിനുള്ള സൂചനയാണീ സങ്കീർണ്ണതാ നംബർ.

ഉദാഹരണത്തിനു, 100000 വസ്തുക്കൾ തമ്മിൽ ബന്ധിപ്പിയ്ക്കാൻ ഈ അൽഗരിതത്തിനു 10000000000 തവണ മാറ്റങ്ങൾ വരുത്തേണ്ടതായിരിയ്ക്കുന്നു! ബില്യൺ(100 കോടി) വസ്തുക്കളെ തമ്മിൽ ബന്ധപ്പെടുത്താനീ അൽഗരിതം ചിലപ്പോൾ 30 കൊല്ലം എടുക്കുമത്രേ! നേരത്തെ കൊടുത്ത ഉദാഹരണങ്ങളിൽ ബില്യൺ എന്നുള്ളത് അത്ര വലിയ ഒരു അക്കമൊന്നുമല്ലയെന്ന് മനസ്സിലാകുംബോളാണീതിന്റെ കുഴപ്പം വ്യക്തമാകുന്നത്. മികച്ച കമ്പ്യൂട്ടർഹാർഡ്വെയർ ഉണ്ടായാലും മോശം അൽഗരിതമാണൂ ഉപയോഗിയ്ക്കുന്നതെങ്കിൽ, യാതൊരു പ്രയോജനവും ഇല്ല എന്നതാണു ഇവിടെ മനസ്സിലാകുന്ന ഒരു പ്രധാന കാര്യം.

ക്വിക്ക് യൂണിയൻ അൽഗരിതം

ദ്വിമാന സമവാക്യത്തിൽ വരുന്ന സങ്കീർണ്ണതയുള്ള അൽഗരിതങ്ങൾ മികച്ചതല്ല എന്ന് മനസ്സിലാക്കിയതിനാൽ മറ്റ് മികച്ച പ്രശ്നപരിഹാര മാർഗ്ഗത്തിലേയ്ക്ക് കമ്പ്യൂട്ടർശാസ്ത്രകാരന്മാർ തിരിഞ്ഞു.

ക്വിക്ക് യൂണിയൻ അൽഗരിതം ഒരു ട്രീ സ്റ്റ്രക്ചറിൽ വസ്തുക്കളെ ക്രമീകരിക്കുകയാണു ചെയ്യുന്നത്.

ഈ അൽഗരിതത്തിൽ, 2 വസ്തുക്കളെ തമ്മിൽ ബന്ധിപ്പിയ്ക്കണമെങ്കിൽ, രണ്ട് വസ്തുക്കളുടെയും പരമമായ മൂലം/റൂട്ട് കണ്ട് പിടിച്ച്, അവയിലൊന്നിന്റെ പരമമായ മൂലത്തിന്റെ/ റൂട്ടിന്റെ റൂട്ടായി രണ്ടാമത്തെ വസ്തുവിന്റെ പരമമായ മൂലത്തെ പ്രതിഷ്ടിയ്ക്കുന്നു.

ഉദാഹരണത്തിനു, 3 4 എന്ന വസ്തുക്കളെ ബന്ധിപ്പിയ്ക്കണമെങ്കിൽ, 3 ഇന്റെ മൂലമായി/റൂട്ടായി 4ൽ ആക്കി മാറ്റുന്നു. അതിനായി അറേയിലെ 3എന്ന ഇൻഡക്സിലെ വാല്യു ആയി 4 നെ ക്രമീകരിയ്ക്കുന്നു.

2 വസ്തുക്കളുടെ പരമമായമൂലം തുല്യമാണെങ്കിൽ ഈ അൽഗരിതപ്രകാരം, അവ പരസ്പരം ബന്ധപ്പെട്ടിരികുന്നവയാണെന്ന് മനസ്സിലാക്കാവുന്നതാണു.

വിശദമായ ഉദാഹരണം

Id[] എന്ന അറയിൽ 10 അക്കങ്ങൾ കൊള്ളാമെന്നിരിയ്ക്കട്ടെ. അറേയിലെ വാല്യുകൾ താഴെകൊടുത്തിര്യ്കുന്ന പോലെയാണു എന്നിരിയ്ക്കട്ടെ

വസ്തുക്കൾ 0 1 2 3 4 5 6 7 8 9 
Id[]         5 0 7 4 6 5 6 8 9 9

Id[0], Id[1], Id[5] എന്നീ അറേ വാല്യൂക്കൾ നോക്കുക. ഒന്ന് എന്ന വസ്തുവിന്റെ മൂലം പൂജ്യവും, 0 എന്ന വസ്തുവിന്റെ മൂലം 5ഉം, 5ന്റെ മൂലം 5 തന്നെയും ആയ രീതിയിലാണു ക്രമീകരണം. (ഇതൊരു ട്രീ സ്റ്റ്രക്ച്ചറാണെന്ന് ഓർക്കുക.) 0,1, 5 എന്നീ വസ്തുക്കളുടെ പരമമായ മൂലം എന്നത് 5 ആണൂ. 2 വസ്തുക്കളുടെ പരമമായമൂലം തുല്യമാണെങ്കിൽ ഈ അൽഗരിതപ്രകാരം, അവ പരസ്പരം ബന്ധപ്പെട്ടിരികുന്നവയാണു.

അതു പോലെ, Id[2], Id[7], Id[8], Id[9] എന്നീ അറേ വാല്യൂക്കൾ നോക്കുക. 2 എന്ന വസ്തുവിന്റെ മൂലം 7ഉം, 7ന്റെ മൂലം 8ഉം, 8ന്റെ മൂലം 9ഉം, 9ന്റെ മൂലം 9 തന്നെയും ആണു. (ഇതുമൊരു ട്രീ സ്റ്റ്രക്ച്ചറാണെന്ന് ഓർക്കുക.) 2,7,8,9 എന്നീ വസ്തുക്കളുടെ പരമമായ മൂലം എന്നത് 9 ആണൂ. (2 വസ്തുക്കളുടെ പരമമായമൂലം തുല്യമാണെങ്കിൽ ഈ അൽഗരിതപ്രകാരം, അവ പരസ്പരം ബന്ധപ്പെട്ടിരികുന്നവയാണു എന്നത് ഓർക്കുക)

അതു പോലെ, Id[3], Id[4], Id[6] എന്നീ അറേ വാല്യൂക്കൾ നോക്കുക. 3 എന്ന വസ്തുവിന്റെ മൂലം 4ഉം, 4ന്റെ മൂലം 6ഉം, 6ന്റെ മൂലം 6 തന്നെയും ആണു. (ഇതുമൊരു ട്രീ സ്റ്റ്രക്ച്ചറാണെന്ന് ഓർക്കുക.) 3,4, 6 എന്നീ വസ്തുക്കളുടെ പരമമായ മൂലം എന്നത് 6 ആണൂ. (2 വസ്തുക്കളുടെ പരമമായമൂലം തുല്യമാണെങ്കിൽ ഈ അൽഗരിതപ്രകാരം, അവ പരസ്പരം ബന്ധപ്പെട്ടിരികുന്നവയാണു എന്നത് ഓർക്കുക)

അൽഗരിതം

class QuickUnion
    {
        int[] Id;
        public QuickUnion(int n)
        {
            Id = new int[n];
            for (int i = 0; i < Id.Length; i++)
            {
                Id[i] = i;
            }
        }

        public bool Find(int p, int q)
        {
            return GetRoot(p) == GetRoot(q);
        }

        public void Union(int p, int q)
        {
            int pRoot = GetRoot(p);
            int qRoot = GetRoot(q);
            Id[pRoot] = qRoot;

        }

        public int GetRoot(int p)
        {
            //recursive way!
            //if (p == Id[p])
            //    return p;
            //else
            //    return GetRoot(Id[p]);
            while (p != Id[p])
                p = Id[p];
            return p;
        }
    }

വിശദീകരണം

Connected ഫണക്ഷൻ രണ്ട് വസ്തുക്കൾ തമ്മിൽ ബന്ധമുണ്ടോയെന്ന് മാത്രം പരിശോധിയ്ക്കുന്നു. പരിശോധിയ്ക്കണ്ട രണ്ട് വസ്തുക്കളുടെ പരമമായ മൂലം/റൂട്ട് കണ്ട് പിടിച്ച് അവ രണ്ടും തുല്യമാണോയെന്ന് പരിശോധിച്ചാണിത് നടപ്പിലാക്കുന്നത്.

Union ഫൺക്ഷൻ ബന്ധപ്പെടുത്തേണ്ട വസ്തുക്കളുടെ രണ്ടിന്റെയും പരമമായ മൂലം കണ്ട് പിടിയ്ക്കുന്നു. എന്നിട്ട് ബന്ധപ്പെടുത്തെണ്ട വസ്തുവിക്കളുടെ ഒന്നിന്റെ പരമമായ മൂലം/റൂട്ട് ബന്ധപ്പെടേണ്ട രണ്ടാമത്തെ വസ്തുവിന്റെ പരമമായ റൂട്ടാക്കി മാറ്റി ട്രീ സ്റ്റ്രക്ച്ചറിനെ പുന:ക്രമീകരിയ്ക്കുന്നു. അതായത് p, q എന്നിവ ബന്ധിപ്പിയ്ക്കണമെന്നിരിയ്ക്കട്ടെ, p യുടെ റൂട്ട് വാല്യു r ഉം, qവിന്റെ s ഉം ആണെന്നിരിക്കട്ടെ. ഇനി r ന്റെ റൂട്ട് വാല്യു ആയി s നിശ്ചയിക്കുന്നു(അറേയിലെ r ഇന്ദെക്സിലെ വാല്യു ആയി, s നെ നിശ്ചയിക്കുന്നുവെന്നർഥം)

അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത

ഈ അൽഗരിതം അൽപ്പം മെച്ചമാണെന്ന് തോന്നൽ ഉളവാക്കുമെങ്കിലും, അന്തിമ വിശകലനത്തിൽ നമ്മെ നിരാശപ്പെടുത്തികളയുകയാണു ചെയ്യുന്നത്. വിശകലനത്തിനു പല തരത്തിലുമൊരൽഗരിതത്തെ സമീപിയ്ക്കാവുന്നതാണു. അൽഗരിതം എത്തി ചേരാവുന്ന ഒരു പ്രത്യേക അവസ്ഥയാണു ചുവടെ കൊടുക്കുന്നത്.

10 എണ്ണമുള്ള ഒരറയിലെ വസ്തുക്കൾ തമ്മിൽ ബന്ധപ്പെടുത്തണമെന്നിരിയ്ക്കട്ടെ. 0 തൊട്ട് 8 വരെ യുള്ള വസ്തുക്കൾ രേഘീയമായി ബന്ധപ്പെട്ടിരിക്കുന്ന ഒരു അവസ്ഥയിൽ, 9 എന്ന വസ്തുവിനെ ഇതുമായി ബന്ധപ്പെടുത്തണമെങ്കിൽ, നാം അറേയിൽ മൊത്തം യാത്ര ചെയ്യേണ്ടിയിരിയ്ക്കുന്നു. അതായത് ഈ ഒരവസ്ഥയിൽ ഒരു വസ്തു മറ്റൊരു വസ്തുവുമായി ബന്ധപ്പെട്ടിട്ടുണ്ടോയെന്ന് മനസ്സിലാക്കാനും ഒരു വസ്തുവിനെ പുതുതായി കൂട്ടി ചേർക്കാനും ആ അറേയിലൂടെ മൊത്തം യാത്ര ചെയ്യണം! അപ്പോൾ N വസ്തുക്കൾ തമ്മിൽ ബന്ധപ്പെടുത്തണമെങ്കിൽ N*N അതായത് N^2 തവണ അറേയിലൂടെ കടന്ന് പോകേണ്ടതായി വരുന്നു. അതായത്, അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത O(N^2) ആണു. ചുരുക്കി പറയുകയാണേൽ ക്വിക്ക് ഫൈൻഡ് അൽഗരിതത്തിനാരോപിച്ച കുറ്റങ്ങൾ വരാവുന്ന അവസ്ഥകൾ ഈ അൽഗരിതത്തിനും ഉണ്ടാകാം!

വെയിറ്റഡ് ക്വിക്ക് യൂണിയൻ അൽഗരിതം

ക്വിക്ക് യൂണിയൻ അൽഗരിതത്തിലെ കുഴപ്പമെന്താണെന്നു വച്ചാൽ ട്രീ സ്റ്റ്രക്ച്ചറിനു വലിപ്പം ക്രമമായി വർദ്ധിക്കുന്നുവെന്നതാണൂ. വസ്തുക്കളെല്ലാം രേഘീയമായി ക്രമീകരിക്കപ്പെടുന്ന, അവസ്ഥയാണിതിലെ ഏറ്റവും മോശപ്പെട്ട അവസ്ഥ. വെയിറ്റഡ് ക്വിക്ക് യൂണിയൻ അൽഗരിതത്തിൽ രണ്ട് ട്രീകൾ പരസ്പരം ബന്ധപ്പെടുത്തുംബോൾ രണ്ട് ട്രീകളുടെയും ആഴം പരിശോധിച്ച്, അവയിലെ ചെറിയ ട്രീയുടെ മൂലമായി വലിയ ട്രീയുടെ മൂലത്തെ പ്രതിഷ്ടിയ്ക്കുന്നു. ക്വിക്ക് യൂണിയൻ അൽഗരിതത്തിലുണ്ടാക്കിയ ഈയൊരു ചെറിയ മാറ്റം വഴി ഉണ്ടാക്കുന്ന നേട്ടം ചില്ലറയല്ല! (മേൽപ്പറഞ്ഞതുപോലെ രണ്ട് വസ്തുക്കൾ തമ്മിലുള്ള ബന്ധം ഉണ്ടാക്കുംബോൾ, ട്രീ സ്ട്രക്ച്ചറിന്റെ ആഴം ഒരുപാട് വർദ്ധിയ്ക്കാതെ നോക്കുന്നതിനാൽ ഈ അൽഗരിതത്തിനെ “പെട്ടെന്ന് ചെറിയ പാലം പണിയഡോ അൽഗരിതം” എന്നു വേണേൽ വിളിയ്ക്കാം)

അൽഗരിതം

class WeightedQuickUnion
    {
        int[] Id;
        int[] depth;
        public WeightedQuickUnion(int n)
        {
            Id = new int[n];
            depth = new int[n];
            for (int i = 0; i < Id.Length; i++)
            {
                Id[i] = i;
                depth[i] = 1;
            }
        }

        public bool Find(int p, int q)
        {
            return GetRoot(p) == GetRoot(q);
        }

        public void Union(int p, int q)
        {
            int pRoot = GetRoot(p );
            int qRoot = GetRoot(q);
            if (depth[pRoot] < depth[qRoot])
            {
                Id[pRoot] = qRoot;
                depth[qRoot] += pRoot;
            }
            else if (depth[pRoot] > depth[qRoot])
            {
                Id[qRoot] = pRoot;
                depth[pRoot] += qRoot;

            }
            else if (depth[pRoot] == depth[qRoot])
            {
                Id[pRoot] = qRoot;
                depth[qRoot]++;
            }
        }
        public int GetRoot(int p)
        {
            while (p != Id[p])
            {
                p = Id[p];
            }
            return p;
        }
    }

വിശദീകരണം

Connected ഫണക്ഷൻ ക്വിക്ക് യൂണിയൻ അൽഗരിതത്തിലുള്ളതു പോലെ തന്നെയാണു. ബന്ധം നിലവിലുണ്ടോയെന്ന് പരിശോധിയ്ക്കണ്ട രണ്ട് വസ്തുക്കളുടെ പരമമായ മൂലം/റൂട്ട് കണ്ട് പിടിച്ച് അവ രണ്ടും തുല്യമാണോയെന്ന് പരിശോധിച്ചാണിത് നടപ്പിലാക്കുന്നത്.

Union ഫൺക്ഷൻ ബന്ധപ്പെടുത്തേണ്ട വസ്തുക്കളുടെ രണ്ടിന്റെയും പരമമായ മൂലം കണ്ട് പിടിയ്ക്കുന്നു. രണ്ടിന്റെയും ആഴം മനസ്സിലാക്കുന്നു. ആഴം കുറവുള്ള മൂലത്തിന്റെ റൂട്ടായി ആഴം കൂടിയ മൂലത്തെ പ്രതിഷ്ടിച്ച്, ട്രീ സ്റ്റ്രക്ച്ചറിനെ പുന:ക്രമീകരിയ്ക്കുന്നു. അതായത് p, q എന്നിവ ബന്ധിപ്പിയ്ക്കണമെന്നിരിയ്ക്കട്ടെ, p യുടെ റൂട്ട് വാല്യു r ഉം, qവിന്റെ s ഉം ആണെന്നിരിക്കട്ടെ. ഇവയിൽ r ന്റെ ആഴം കുറവാണെന്നിരിയ്ക്കട്ടെ, ഇനി r ന്റെ റൂട്ട് വാല്യു ആയി s നിശ്ചയിക്കുന്നു(അറേയിലെ r ഇന്ദെക്സിലെ വാല്യു ആയി, s നെ നിശ്ചയിക്കുന്നുവെന്നർഥം). മറിച്ചാണെങ്കിൽ s ന്റെ റൂട്ട് വാല്യു ആയി rനെ നിശ്ചയിക്കുന്നു

രണ്ടിന്റെയും ആഴം തുല്യമാണെങ്കിൽ, ഏതെങ്കിലുമൊരു ട്രീയുടെ മൂലത്തിന്റെ റൂട്ടായി, മറ്റേ ട്രീയുടെ മൂലത്തെ പ്രതിഷ്ടിക്കുകയും, രണ്ടാമത്തെ ട്രീയുടെ ആഴം ഒന്ന് വർദ്ധിപ്പിക്കുകയും ചെയ്യുന്നു.

അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത

ക്വിക്ക് യൂണീയൻ അൽഗരിതത്തിലുണ്ടാക്കിയ ഈ ചെറിയ മാറ്റം കൊണ്ടുണ്ടാകുന്ന നേട്ടം അത്ഭുതകരമാണു. കുറേകൂടെ ഫ്ലാറ്റ് ആയ/നിരപ്പായ ഒരു ട്രീ സ്റ്റ്രക്ച്ചറാണീ അൽഗരിതം വഴി ഉണ്ടാകുന്നത്. അതിനാൽ മൂലം കണ്ട് പിടിയ്ക്കാനും, പുതിയ വസ്തുക്കൾ കൂട്ടിചേർക്കാനും, വളരെ കുറച്ച് യാത്ര(iteration) മാത്രം മതിയാകും. ഈ അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത N+ lgN ആണു.

പാത്ത് കംപ്രസ്ഡ് വെയിറ്റഡ് ക്വിക്ക് യൂണിയൻ അൽഗരിതം

വെയിറ്റഡ് ക്വിക്ക് യൂണിയൻ അൽഗരിതത്തിൽ ഒരു വസ്തുവിന്റെ പരമമായ റൂട്ട് കണ്ട് പിടിയ്കുന്ന പ്രക്രിയയിൽ, വഴിക്ക് കാണുന്ന എല്ലാ വസ്തുവിന്റെയും തൊട്ട് മേളിലുള്ള മൂലത്തെ ഈ പരമമായ മൂലമാക്കി പ്രതിഷ്ടിച്ചാൽ പാത്ത് കംബ്രസിഡ് ക്വിക്ക് യൂണീയൻ അൽഗരിതമായി. ഇപ്രകാരം ഓരോ വസ്തുവുന്റെയും മൂലമായി, പരമമായ റൂട്ടിനെ ക്രമീകരിച്ചാൽ നമുക്ക് വളരെ ഫ്ലാറ്റ് ആയ ഒരു ട്രീ സ്റ്റ്രക്ച്ചറാണൂ ലഭിയ്ക്കുന്നത്. അതോടെ അൽഗരിതത്തിന്റെ സങ്കീർണ്ണത അവിശ്വസിനീയമായി കുറയുന്നു. ഹോപ്പ്മാൻ -ഉൾമാൻ, ടർജൻ അനാലിസിസ് പ്രകാരം, ഒരു ശൂന്യമായ അറേയിൽ നിന്നും തുടങ്ങി, M യൂണീയൻ/ഫൈൻഡ് ഓപ്പറേഷൻ ഒരു N വസ്തുക്കളിൽ നടത്താൻ N + Mlg*N തവണ അറേയിലൂടെ യാത്ര(iterate) ചെയ്യേണ്ടി വരുമത്രേ . lg* N എന്നു പറഞ്ഞാൽ N നെ എത്രത്തോളം ലൊഗരിതമിക്കായിട്ട്(ബേയ്സ് 2) iterate ചെയ്താൽ, 1 ലഭിയ്ക്കും എന്നത്രെ.

N	lg*N
1	0
2	1
4	2
16	3
65536	4
2^65536	5

അതായത് ഈ അൽഗരിതം ഏകദേശം ലീനിയറായ സങ്കീർണത നൽകുന്നു. (ഫ്രഡ്മാൻ , സാക്സ് തുടങ്ങിയവർ ലീനിയർ ആയ സങ്കീർണതയുള്ള അൽഗരിതം ഈ പ്രശ്നത്തിൽ ഉണ്ടാവില്ലയെന്ന് തെളിയിച്ചിട്ടുണ്ട്)

അൽഗരിതം

class CompressedPathWithWeightedQuickUnion
    {
        int[] Id;
        int[] depth;
        public CompressedPathWithWeightedQuickUnion(int n)
        {
            Id = new int[n];
            depth = new int[n];
            for (int i = 0; i < Id.Length; i++)
            {
                Id[i] = i;
                depth[i] = 1;
            }
        }

        public bool Find(int p, int q)
        {
            return GetRoot(p) == GetRoot(q);
        }

        public void Union(int p, int q)
        {
            int pRoot = GetRoot(p);
            int qRoot = GetRoot(q);


           	 if (depth[pRoot] < depth[qRoot])
                {
                    Id[pRoot] = qRoot;
                }
                else if (depth[pRoot] > depth[qRoot])
                {
                    Id[qRoot] = pRoot;
                }
                else if (depth[pRoot] == depth[qRoot])
                {
                    Id[pRoot] = qRoot;
                    depth[qRoot]++;
                }
        }
        public int GetRoot(int p)
        {
            while (p != Id[p])
            {
 		//assigns root of root as the root of P. This does the magic!
                Id[p] = Id[Id[p]];
                p = Id[p];
            }
            return p;
        }
    }

വിശദീകരണം

ഒരു വസ്തുവിന്റെ പരമമായ റൂട്ട് കണ്ട് പിടിയ്ക്കാനുള്ള ശ്രമത്തിനിടയിൽ, ആ വസ്തുവിന്റെ റൂട്ടായി തന്റെ തൊട്ടടുത്ത(ഇപ്പോഴത്തെ) റൂട്ടിന്റെ റൂട്ടിനെ പ്രതിഷ്ടിയ്ക്കുന്നു.( Id[p] = Id[Id[p]] എന്ന സ്റ്റെപ്പ് ശ്രദ്ധിയ്ക്കുക) ഈയൊരറ്റ വിദ്യ വഴിയാണൂ ഈ അൽഗരിതം അവിശ്വസിനീയമായ നേട്ടം കൈവരിക്കുന്നത്!

അവലംബം

Ref: Algorithms: session given by Robert Sedgewick and Kevin Wayne