Simplex tree
ટોપોલોજિકલ ડેટા વિશ્લેષણમાં, સિમ્પ્લેક્સ ટ્રી એ એક પ્રકારનો ટ્રી છે જેનો ઉપયોગ કોઈપણ સામાન્ય સરળ સંકુલને અસરકારક રીતે રજૂ કરવા માટે થાય છે. તેના નોડ્સ દ્વારા, આ ડેટા સ્ટ્રક્ચર નોંધપાત્ર રીતે તમામ સરળતાઓને સ્પષ્ટપણે રજૂ કરે છે. તેનું લવચીક માળખું સતત સમરૂપતાની ગણતરી કરવા માટે ઉપયોગી ઘણી મૂળભૂત કામગીરીઓના અમલીકરણને મંજૂરી આપે છે. આ ડેટા સ્ટ્રક્ચરની શોધ જીન-ડેનિયલ બોઇસોનેટ અને ક્લેમેન્ટ મારિયા દ્વારા 2014 માં 'ધ સિમ્પ્લેક્સ ટ્રીઃ એન એફિશિયન્ટ ડેટા સ્ટ્રક્ચર ફોર જનરલ સિમ્પ્લિકલ કોમ્પ્લેક્સિસ' લેખમાં કરવામાં આવી હતી. આ માહિતી માળખું વિરલ સરળ સંકુલ પર કાર્યક્ષમ કામગીરી પ્રદાન કરે છે. ગાઢ અથવા મહત્તમ સરળતા માટે, કંકાલ-બ્લૉકર રજૂઆતો અથવા ટોપલેક્સ નકશાની રજૂઆતો વપરાય છે. વ્યાખ્યાઓ ટોપોલોજીકલ માહિતી વિશ્લેષણમાં ઘણા સંશોધકો સિમ્પ્લેક્સ વૃક્ષને સરળ સંકુલ માટે સૌથી સઘન સિમ્પ્લેક્સ-આધારિત માહિતી માળખું માને છે, અને માહિતી માળખું તેમના ગાણિતિક ગુણધર્મોના સંકલિત ઉપયોગને કારણે સરળ સંકુલની સાહજિક સમજણને મંજૂરી આપે છે. કોઈપણ સરળ સંકુલ એ બિંદુઓ (0 પરિમાણો), રેખા વિભાગો (1 પરિમાણ), ત્રિકોણ (2 પરિમાણો) અને તેમના એન-પરિમાણીય સમકક્ષોથી બનેલો સમૂહ છે, જેને ટોપોલોજિકલ જગ્યામાં એન-સિમ્પ્લેક્સ કહેવાય છે. સિમ્પ્લેક્સના ગાણિતિક ગુણધર્મો અનુસાર, કોઈપણ એન-સિમ્પ્લેક્સ બહુવિધ-સિમ્પ્લેક્સથી બનેલું હોય છે. આમ, રેખાઓ બિંદુઓ, રેખાઓના ત્રિકોણ, ત્રિકોણના ચતુષ્કોણથી બનેલી હોય છે. નોંધ લો કે દરેક ઉચ્ચ સ્તર એન-સિમ્પ્લેક્સના શિરોબિંદુઓમાં 1 શિરોબિંદુ ઉમેરે છે. ડેટા સ્ટ્રક્ચર સિમ્પ્લેક્સ-આધારિત છે, તેથી, તે સિમ્પ્લેક્સને વ્યાખ્યાયિત કરતા બિંદુઓ દ્વારા તમામ સિમ્પ્લેક્સને અનન્ય રીતે રજૂ કરવું જોઈએ. આ હાંસલ કરવાની એક સરળ રીત એ છે કે દરેક સિમ્પ્લેક્સને તેના બિંદુઓ દ્વારા સૉર્ટ કરેલા ક્રમમાં વ્યાખ્યાયિત કરવું. ચાલો પરિમાણ k નું સરળ સંકુલ, તેના શિરોબિંદુ સમૂહ, જ્યાં શિરોબિંદુઓને 1 થી લેબલ કરવામાં આવે છે અને તે મુજબ ક્રમ આપવામાં આવે છે. હવે, ક્રમમાં તમામ શિરોબિંદુ લેબલ ધરાવતો શબ્દકોશનું કદ બનાવો. આ 0-પરિમાણીય સિમ્પ્લેક્સને રજૂ કરે છે. પછી, પ્રારંભિક શબ્દકોશમાં દરેક પ્રવેશના પ્રારંભિક શબ્દકોશના માર્ગ માટે, વર્તમાન શિરોબિંદુઓના સમૂહ સાથે સંપૂર્ણપણે જોડાયેલા તમામ શિરોબિંદુઓને બાળ શબ્દકોશ તરીકે ઉમેરો, જે તમામ શિરોબિંદુઓ કરતાં મોટું લેબલ ધરાવે છે. આ પગલાને k સ્તરો પર રજૂ કરો. સ્પષ્ટપણે, પ્રથમ શબ્દકોશને ઊંડાઈ 0 તરીકે ધ્યાનમાં લેતા, આ ડેટા સ્ટ્રક્ચરમાં કોઈપણ શબ્દકોશની ઊંડાઈ પરની કોઈપણ એન્ટ્રી અનન્ય રીતે અંદરના-સિમ્પ્લેક્સને રજૂ કરે છે. સંપૂર્ણતા માટે, પ્રારંભિક શબ્દકોશનો મુદ્દો ખાલી સિમ્પ્લેક્સની રજૂઆત માનવામાં આવે છે. કામગીરીની કાર્યદક્ષતા માટે, સમાન સ્તર પર પુનરાવર્તિત લેબલો એકસાથે જોડાયેલી હોય છે, જે લૂપ કરેલી લિંક કરેલી સૂચિ બનાવે છે. છેવટે, બાળ શબ્દકોશોમાં પૂર્વજોની ઝડપી પહોંચ માટે તેમના મૂળ શબ્દકોશનાં સૂચનો પણ હોય છે. રચનાત્મક વ્યાખ્યા ચાલો પરિમાણ k નું સરળ સંકુલ હોઈએ. આપણે સરળ સંકુલને પરસ્પર વિશિષ્ટ સિમ્પ્લેક્સમાં વિઘટિત કરીને પ્રારંભ કરીએ છીએ. આ લોભી રીતે સરળ સંકુલમાંથી પુનરાવર્તિત રીતે ઉચ્ચતમ ક્રમના સિમ્પ્લેક્સને દૂર કરીને સરળ સંકુલ ખાલી ન થાય ત્યાં સુધી પ્રાપ્ત કરી શકાય છે. પછી આપણે દરેક શિરોબિંદુને 1 થી લેબલ કરવાની જરૂર છે અને દરેક સિમ્પ્લેક્સને તેના અનુરૂપ "શબ્દ" સાથે સાંકળવાની જરૂર છે, જે લેબલ દ્વારા તેના શિરોબિંદુઓની ક્રમબદ્ધ સૂચિ છે. લેબલોને ઓર્ડર કરવાથી સિમ્પ્લેક્સ વૃક્ષમાં પુનરાવર્તન ન થાય તેની ખાતરી થાય છે, કારણ કે સિમ્પ્લેક્સનું વર્ણન કરવાની માત્ર એક જ રીત છે. આપણે નલ રુટથી શરૂઆત કરીએ છીએ, જે નલ સિમ્પ્લેક્સનું પ્રતિનિધિત્વ કરે છે. પછી, આપણે બધા સિમ્પ્લેક્સ દ્વારા અને દરેક સિમ્પ્લેક્સ શબ્દના દરેક લેબલ દ્વારા પુનરાવર્તન કરીએ છીએ. જો લેબલ વર્તમાન મૂળમાં બાળક તરીકે ઉપલબ્ધ હોય, તો તે બાળકને દાખલ કરવાની પ્રક્રિયાનું કામચલાઉ મૂળ બનાવો, અન્યથા, બાળક માટે એક નવું નોડ બનાવો, તેને નવું કામચલાઉ મૂળ બનાવો અને બાકીના શબ્દ સાથે ચાલુ રાખો. આ પ્રક્રિયા દરમિયાન, k શબ્દકોશો તમામ લેબલો સાથે જાળવવામાં આવે છે અને અનુરૂપ લેબલ માટે નોડનું સરનામું દાખલ કરે છે. જો કોઈ સરનામું શબ્દકોશમાં તે જગ્યા પર પહેલેથી જ હોય, તો જૂના નોડથી નવા નોડ પર એક નિર્દેશક બનાવવામાં આવે છે. એકવાર પ્રક્રિયા પૂર્ણ થઈ જાય પછી દરેક નોડના તમામ બાળકોને શબ્દકોશમાં દાખલ કરવામાં આવે છે, અને બધા પોઇન્ટર લૂપ્ડ લિંક કરેલી સૂચિ બનાવવા માટે લૂપ થાય છે. હેશ કોષ્ટકો જેવા શબ્દકોશોની વિશાળ શ્રેણી અહીં લાગુ કરી શકાય છે, પરંતુ કેટલીક કામગીરીઓ એન્ટ્રીઓના ક્રમબદ્ધ ટ્રાવર્સલની શક્યતા ધારે છે, જેના કારણે લાલ-કાળા વૃક્ષોનો ઉપયોગ કરવા માટેના મોટાભાગના અમલીકરણ શબ્દકોશો છે. કામગીરી જ્યારે સિમ્પ્લેક્સ વૃક્ષો સરળ જટિલ રજૂઆત માટે સૌથી વધુ જગ્યા કાર્યક્ષમ માહિતી માળખાં નથી, ત્યારે વિરલ માહિતી પરની તેમની કામગીરીને અદ્યતન ગણવામાં આવે છે. અહીં, આપણે આ રજૂઆત દ્વારા શક્ય વિવિધ ઉપયોગી કામગીરીઓની સીમાઓ આપીએ છીએ. આ કામગીરીઓના ઘણા અમલીકરણ ઉપલબ્ધ છે. આપણે સૌ પ્રથમ સંકેત રજૂ કરીએ છીએ. ધ્યાનમાં લો કે આપેલ સિમ્પ્લેક્સ, છેલ્લા શિરોબિંદુને અનુરૂપ આપેલ નોડ છે, તે નોડ સાથે સંકળાયેલ લેબલ છે, તે નોડની ઊંડાઈ છે, સરળ સંકુલનું પરિમાણ છે, શબ્દકોશમાં ઍક્સેસ કરવા માટેની કામગીરીની મહત્તમ સંખ્યા છે (જો શબ્દકોશ લાલ-કાળા વૃક્ષ છે, તો તે જટિલતા છે). કોફેસની સંખ્યા ધ્યાનમાં લો, અને તે સિમ્પ્લેક્સ વૃક્ષના ગાંઠોની સંખ્યા છે જે લેબલની ઊંડાઈ કરતાં વધારે છે. નોંધ લો. શબ્દો શોધો, દાખલ કરો અને દૂર કરો. સંપૂર્ણ સિમ્પ્લેક્સ દાખલ કરો અને દૂર કરો. સતત સમરૂપતાની ગણતરી કરવી, અથવા વધુ સંકળાયેલી રીતે, બેટ્ટી સંખ્યાઓની ગણતરી કરવી, સિમ્પ્લેક્સ વૃક્ષનો સૌથી વધુ અસરકારક રીતે ઉપયોગ કરવો એ એક ખુલ્લી સમસ્યા છે, જો કે, વિરલ સરળ સંકુલ પર આ કાર્ય માટે વર્તમાન અલ્ગોરિધમ્સ અદ્યતન કામગીરી પ્રાપ્ત કરે છે. સિમ્પ્લેક્સ વૃક્ષોનું માળખું સંકુચિત સિમ્પ્લેક્સિસના પ્રાથમિક પતન માટે પરવાનગી આપે છે, જો કે સામાન્ય કિસ્સામાં આ કામગીરીની સીમાઓ અજ્ઞાત છે. પ્રાથમિક પતનનો પેટા કેસ ધાર-સંકોચન છે. ધાર સંકોચન પ્રાપ્ત કરી શકાય છે. આપેલ સિમ્પ્લેક્સની કોફેસ શોધવામાં આવી શકે છે. આપેલ સિમ્પ્લેક્સના કોફેસેટ્સને શોધવામાં આવી શકે છે. બાંધકામ માટે, રચનાત્મક વ્યાખ્યામાં જોવામાં આવે છે તેમ, બાંધકામ સરળ સંકુલમાં સિમ્પ્લેક્સની સંખ્યા અને જટિલતાના પ્રમાણમાં છે. આ ખાસ કરીને ખર્ચાળ હોઈ શકે છે જો સરળ સંકુલ ગાઢ હોય. જો કે, ફ્લેગ કોમ્પ્લેક્સ, રિપ્સ કોમ્પ્લેક્સ અને વિટનેસ કોમ્પ્લેક્સ સહિત ચોક્કસ સરળ કોમ્પ્લેક્સ માટે કેટલાક ઓપ્ટિમાઇઝેશન. એપ્લિકેશન્સ સિમ્પ્લેક્સ વૃક્ષ વિરલ સરળ સંકુલમાં કાર્યક્ષમ છે. આ હેતુ માટે, ઉચ્ચ-પરિમાણીય વાસ્તવિક માહિતી (ઘણીવાર વિરલ) પર ધ્યાન કેન્દ્રિત કરતા ઘણા સતત સમરૂપતા અલ્ગોરિધમ્સ આ અલ્ગોરિધમ્સમાં સિમ્પ્લેક્સ વૃક્ષોનો ઉપયોગ કરે છે. જ્યારે સિમ્પ્લેક્સ વૃક્ષો ઇન્સિડેન્સ મેટ્રિક્સ જેટલા કાર્યક્ષમ નથી, તેમનું સિમ્પ્લેક્સ-આધારિત માળખું તેમને સતત સમરૂપતા અલ્ગોરિધમ્સમાં સરળ જટિલ સંગ્રહ માટે ઉપયોગી કાર્યક્ષમ બનવાની મંજૂરી આપે છે. સંદર્ભ વૃક્ષો (માહિતી માળખાં) સરળ સમૂહો