Reverse-search algorithm
રિવર્સ-સર્ચ અલ્ગોરિધમ્સ એ સંયોજન પદાર્થોના ચોક્કસ વર્ગોમાંથી આપેલ કદના તમામ પદાર્થો બનાવવા માટેના અલ્ગોરિધમ્સનો એક વર્ગ છે. ઘણા કિસ્સાઓમાં, આ પદ્ધતિઓ પદાર્થોને પદાર્થ દીઠ બહુપદી સમયમાં ઉત્પન્ન કરવાની મંજૂરી આપે છે, જેમાં પદાર્થોની સતત સંખ્યા (બહુપદી જગ્યા) સંગ્રહિત કરવા માટે માત્ર પૂરતી મેમરીનો ઉપયોગ થાય છે. (સામાન્ય રીતે, જોકે, તેમને બહુપદી-સમયના અલ્ગોરિધમ્સ તરીકે વર્ગીકૃત કરવામાં આવતા નથી, કારણ કે તેઓ પેદા કરેલા પદાર્થોની સંખ્યા ઘાતાંકીય હોય છે.) તેઓ તેમના રાજ્યના વિસ્તારમાં ફેલાયેલા વૃક્ષમાં પેદા થનારી વસ્તુઓને ગોઠવીને કામ કરે છે, અને પછી આ વૃક્ષની ઊંડાણપૂર્વક-પ્રથમ શોધ કરે છે. બહિર્મુખ પોલીટોપ્સના શિરોબિંદુઓ અને હાયપરપ્લેનની ગોઠવણીના કોષો પેદા કરવાની સમસ્યાઓ માટે 1991માં ડેવિડ એવિસ અને કોમેઈ ફુકુડા દ્વારા રિવર્સ-સર્ચ અલ્ગોરિધમ્સ રજૂ કરવામાં આવ્યા હતા. 1996માં એવિસ અને ફુકુડા દ્વારા તેમને વધુ વ્યાપક રીતે ઔપચારિક બનાવવામાં આવ્યા હતા. સિદ્ધાંતો રિવર્સ-સર્ચ અલ્ગોરિધમ સ્થિતિ અવકાશમાં સંયુક્ત પદાર્થો ઉત્પન્ન કરે છે, એક ગર્ભિત આલેખ કે જેના શિરોબિંદુઓ સૂચિબદ્ધ કરવાના પદાર્થો છે અને જેની ધાર પદાર્થોની જોડીને જોડતી ચોક્કસ "સ્થાનિક ચાલ" નું પ્રતિનિધિત્વ કરે છે, સામાન્ય રીતે તેમની રચનામાં નાના ફેરફારો કરીને. તે નીચેની માહિતી દ્વારા વર્ણવેલ આ રાજ્ય જગ્યાના મૂળ ફેલાયેલા વૃક્ષમાં ઊંડાણ-પ્રથમ શોધનો ઉપયોગ કરીને દરેક વસ્તુને શોધે છેઃ ફેલાયેલા વૃક્ષનું મૂળ, વસ્તુઓમાંની એક વૃક્ષમાં દરેક પદાર્થના પેરેન્ટને ઉત્પન્ન કરવા માટે એક સબરૂટિન, મિલકત સાથે કે જો પૂરતી વખત પુનરાવર્તન કરવામાં આવે તો તે આખરે રાજ્ય જગ્યામાં તમામ પડોશીઓને સૂચિબદ્ધ કરવા માટે એક સબરૂટિન સુધી પહોંચશે (જેમાંથી બધા વૃક્ષમાં પડોશીઓ ન હોઈ શકે) આ માહિતીમાંથી વૃક્ષમાં આપેલ કોઈપણ નોડના બાળકોને શોધવાનું શક્ય છે, પેરેન્ટ સબરૂટિન દ્વારા આપવામાં આવેલી લિંક્સને ઉલટાવી શકાય છેઃ તેઓ ફક્ત પડોશીઓ છે જેમના પેરેન્ટ આપેલ નોડ છે. તે ચાઈલ્ડ નોડ્સની આ વિપરીત કડીઓ છે જે અલ્ગોરિધમ શોધે છે. આ ફેલાયેલા વૃક્ષની શાસ્ત્રીય ઊંડાઈ-પ્રથમ શોધ વૃક્ષને પુનરાવર્તિત રીતે પસાર કરશે, મૂળથી શરૂ કરીને, દરેક નોડ પર તમામ બાળકોની યાદી બનાવશે અને દરેક માટે પુનરાવર્તિત કૉલ કરશે. ચક્ર સાથેના આલેખની ઊંડાઈ-પ્રથમ શોધથી વિપરીત, વારંવાર મુલાકાત ટાળવા માટે પહેલેથી જ મુલાકાત લેવાયેલા ગાંઠોના સમૂહને જાળવવાની જરૂર નથી; વૃક્ષમાં આવું પુનરાવર્તન શક્ય નથી. જો કે, આ પુનરાવર્તિત અલ્ગોરિધમને હજુ પણ તેના કોલ સ્ટેક માટે મોટી માત્રામાં મેમરીની જરૂર પડી શકે છે, એવા કિસ્સાઓમાં જ્યારે વૃક્ષ ખૂબ ઊંડું હોય. તેના બદલે, રિવર્સ સર્ચ ફેલાયેલા વૃક્ષને એક જ ક્રમમાં પસાર કરે છે જ્યારે માત્ર બે વસ્તુઓનો સંગ્રહ કરે છેઃ ટ્રાવર્સલનો વર્તમાન પદાર્થ અને અગાઉ પસાર થયેલ પદાર્થ. શરૂઆતમાં, વર્તમાન પદાર્થ વૃક્ષના મૂળ પર સેટ કરવામાં આવે છે, અને ત્યાં કોઈ અગાઉનો પદાર્થ નથી. આ માહિતી પરથી, નીચેના કેસ વિશ્લેષણ દ્વારા ટ્રાવર્સલનું આગળનું પગલું નક્કી કરવું શક્ય છેઃ જો અગાઉનો કોઈ પદાર્થ ન હોય, અથવા અગાઉનો પદાર્થ વર્તમાન પદાર્થનો પેરેન્ટ હોય, તો આ પ્રથમ વખત છે જ્યારે ટ્રાવર્સલ વર્તમાન પદાર્થ સુધી પહોંચ્યો છે, તેથી તે શોધમાંથી આઉટપુટ છે. આગળનો ઉદ્દેશ તેનું પ્રથમ બાળક અથવા, જો તેને કોઈ સંતાન ન હોય, તો તેના માતાપિતા છે. અન્ય તમામ કિસ્સાઓમાં, અગાઉનો પદાર્થ વર્તમાન પદાર્થનો બાળક હોવો જોઈએ. અલ્ગોરિધમ આ અગાઉના બાળક સુધી પહોંચે ત્યાં સુધી બાળકોને (એટલે કે, વર્તમાન ઑબ્જેક્ટના રાજ્ય-અવકાશ પડોશીઓ કે જેમની પાસે વર્તમાન ઑબ્જેક્ટ તેમના માતાપિતા તરીકે છે) એક સમયે એક સૂચિબદ્ધ કરે છે, અને પછી બાળકોની આ સૂચિમાં વધુ એક પગલું લે છે. જો અન્ય બાળક આ રીતે જોવા મળે, તો તે આગામી પદાર્થ છે. જો ત્યાં કોઈ આગામી બાળક ન હોય અને વર્તમાન પદાર્થ મૂળ ન હોય, તો આગામી પદાર્થ વર્તમાન પદાર્થનો પિતૃ છે. બાકીના કિસ્સામાં, જ્યારે કોઈ આગામી બાળક ન હોય અને વર્તમાન પદાર્થ મૂળ હોય, ત્યારે વિપરીત શોધ સમાપ્ત થાય છે. આ અલ્ગોરિધમમાં શોધના દરેક પગલા માટે ઑબ્જેક્ટના પડોશીઓને એકવાર સૂચિબદ્ધ કરવાનો સમાવેશ થાય છે. જો કે, જો ત્યાં સૂચિબદ્ધ કરવા માટે વસ્તુઓ હોય, તો પછી શોધ પગલાંઓ કરે છે, તેથી તે વસ્તુઓના પડોશીઓને કેટલી વાર ઉત્પન્ન કરે છે તે પુનરાવર્તિત ઊંડાઈ-પ્રથમ શોધ એ જ વસ્તુ કરશે તે સંખ્યાના બે ગણો પરિબળની અંદર છે. એપ્લિકેશન્સ રિવર્સ સર્ચ લાગુ કરવામાં આવી છે તે સમસ્યાઓના ઉદાહરણોમાં નીચેની સંયુક્ત પેઢીની સમસ્યાઓનો સમાવેશ થાય છેઃ સરળ બહિર્મુખ પોલીટોપ્સના શિરોબિંદુ જો-પરિમાણીય બહિર્મુખ પોલીટોપને અર્ધ-જગ્યાઓના આંતરછેદ તરીકે વ્યાખ્યાયિત કરવામાં આવે, તો તેના શિરોબિંદુઓને અર્ધ-જગ્યાઓને બંધાયેલા આંતરછેદના બિંદુઓ અથવા વધુ હાયપરપ્લેન તરીકે વર્ણવી શકાય છે; જો કોઈ શિરોબિંદુ આ હાયપરપ્લેન કરતાં વધુનું આંતરછેદ ન હોય તો તે એક સરળ પોલીટોપ છે. શિરોબિંદુ ગણતરીની સમસ્યા એ આ તમામ શિરોબિંદુઓને સૂચિબદ્ધ કરવાની સમસ્યા છે. પોલીટોપની કિનારીઓ એવા શિરોબિંદુઓની જોડીને જોડે છે જે સામાન્ય રીતે હાયપરપ્લેન ધરાવે છે, તેથી શિરોબિંદુઓ અને કિનારીઓ એક સ્થિતિ જગ્યા બનાવે છે જેમાં દરેક શિરોબિંદુ પડોશીઓ ધરાવે છે. રેખીય પ્રોગ્રામિંગના સિદ્ધાંતમાંથી સિમ્પ્લેક્સ અલ્ગોરિધમ શિરોબિંદુથી શિરોબિંદુ સુધી ચાલીને, દરેક તબક્કે કાર્યના વધુ મૂલ્ય સાથે શિરોબિંદુ પસંદ કરીને, કોઓર્ડિનેટ્સના આપેલ રેખીય કાર્યને મહત્તમ કરતું શિરોબિંદુ શોધે છે; "પિવોટ નિયમ" ની ઘણી પ્રમાણભૂત પસંદગીઓ છે જે વધુ ચોક્કસપણે સ્પષ્ટ કરે છે કે કયા શિરોબિંદુને પસંદ કરવું. આવા કોઈપણ ધરી નિયમને પોલીટોપનાં ફેલાયેલા વૃક્ષના મૂળ કાર્યને વ્યાખ્યાયિત કરવા તરીકે અર્થઘટન કરી શકાય છે, જેનું મૂળ શ્રેષ્ઠ શિરોબિંદુ છે. આ માહિતી પર વિપરીત શોધ લાગુ કરવાથી પોલીટોપનાં તમામ શિરોબિંદુઓ ઉત્પન્ન થાય છે. સમાન અલ્ગોરિધમ પણ રેખીય પ્રોગ્રામના તમામ પાયાની ગણતરી કરી શકે છે, તેની જરૂર વગર તે એક સરળ પોલીટોપને વ્યાખ્યાયિત કરે છે. હાયપરપ્લેન ગોઠવણીના કોષો હાયપરપ્લેન ગોઠવણી યુક્લિડિયન જગ્યાને કોષોમાં વિઘટિત કરે છે, દરેક "સાઇન વેક્ટર" દ્વારા વર્ણવવામાં આવે છે જે વર્ણવે છે કે તેના બિંદુઓ હાયપરપ્લેન (સાઇન 0) માંથી એકના છે, હાયપરપ્લેન (સાઇન + 1) ની એક બાજુ છે, અથવા બીજી બાજુ (સાઇન-1) છે. કોષો સ્થાનિક ચાલ હેઠળ જોડાયેલ સ્થિતિ જગ્યા બનાવે છે જે એક એકમ દ્વારા એક ચિહ્નને બદલે છે, અને તે તપાસવું શક્ય છે કે આ કામગીરી રેખીય પ્રોગ્રામિંગ શક્યતા સમસ્યાને હલ કરીને માન્ય કોષ ઉત્પન્ન કરે છે. મૂળ કોષની કોઈપણ પસંદગી માટે સ્પૅનિંગ ટ્રીનું નિર્માણ પેરેન્ટ ઓપરેટરને વ્યાખ્યાયિત કરીને કરી શકાય છે જે પ્રથમ સંભવિત ફેરફાર કરે છે જે સાઇન વેક્ટરને મૂળની નજીક લાવશે. આ સ્ટેટ સ્પેસ અને પેરેન્ટ ઓપરેટર માટે રિવર્સ સર્ચનો ઉપયોગ કરીને કોષ દીઠ બહુપદી સમયમાં તમામ કોષોને સૂચિબદ્ધ કરવા માટે એક અલ્ગોરિધમ ઉત્પન્ન કરે છે. બિંદુ-સમૂહ ત્રિકોણ સમતલીય બિંદુ સમૂહના ત્રિકોણને "પલટી" ચાલ દ્વારા જોડવામાં આવે છે જે ત્રિકોણમાંથી એક કર્ણને દૂર કરે છે અને તેને બીજા દ્વારા બદલે છે. જો ડેલાઉને ત્રિકોણને મૂળ તરીકે પસંદ કરવામાં આવે, તો પછી દરેક ત્રિકોણને ડેલાઉને ત્રિકોણમાં પગલાં દ્વારા ફેરવી શકાય છે જેમાં ચાર બિંદુઓના કેટલાક સબસેટના ત્રિકોણને તેના ડેલાઉને ત્રિકોણ દ્વારા બદલવામાં આવે છે. દરેક ત્રિકોણના મૂળ તરીકે પ્રથમ ડેલાઉને વળાંક પસંદ કરવાથી, અને સ્થાનિક શોધ લાગુ કરવાથી, ત્રિકોણ દીઠ બહુપદી સમયમાં તમામ ત્રિકોણને સૂચિબદ્ધ કરવા માટે એક અલ્ગોરિધમ ઉત્પન્ન થાય છે. જોડાયેલા સબગ્રાફ આપેલ જોડાયેલા ગ્રાફના જોડાયેલા સબગ્રાફ્સ અને જોડાયેલા પ્રેરિત સબગ્રાફ્સ, સ્ટેટ સ્પેસ બનાવે છે, જેની સ્થાનિક ચાલ અનુક્રમે ગ્રાફની એક ધાર અથવા શિરોબિંદુને ઉમેરવા અથવા દૂર કરવાની હોય છે. આ સ્થિતિ જગ્યાનું ફેલાયેલું વૃક્ષ પ્રથમ ધાર અથવા શિરોબિંદુ (ધાર અથવા શિરોબિંદુઓના અમુક ક્રમમાં) ઉમેરીને મેળવી શકાય છે, જેનો ઉમેરો અન્ય જોડાયેલ પેટા આલેખ ઉત્પન્ન કરે છે; તેનું મૂળ સમગ્ર આલેખ છે. આ સ્ટેટ સ્પેસ અને પેરેન્ટ ઓપરેટર પર સ્થાનિક શોધ લાગુ કરવાથી સબગ્રાફ દીઠ બહુપદી સમયમાં તમામ જોડાયેલા સબગ્રાફ્સને સૂચિબદ્ધ કરવા માટે એક અલ્ગોરિધમ ઉત્પન્ન થાય છે. અન્ય ઉપયોગોમાં નીચેની રચનાઓ પેદા કરવા માટેના અલ્ગોરિધમ્સનો સમાવેશ થાય છેઃ પોલિમિનોસ, પોલિઆમોન્ડ પ્રોટોટાઇલ્સ અને પોલીહેક્સ (ગણિત) હાઇડ્રોકાર્બન પરમાણુઓ. સ્ટેટ સ્પેસનો ઉપયોગ કરીને નિર્દેશિત એસાયક્લિક ગ્રાફના ટોપોલોજીકલ ક્રમ, જેની સ્થાનિક ચાલ બે તત્વોના ક્રમને ઉલટાવી દે છે. ગ્રાફના વૃક્ષો, સમતલીય બિંદુ સમૂહોના વૃક્ષોને પાર ન કરવા અને વધુ સામાન્ય રીતે મેટ્રોઇડના પાયા, રાજ્ય જગ્યાનો ઉપયોગ કરીને જે એક ધારને બીજી ધાર સાથે અદલાબદલી કરે છે. યુલર આલેખમાં પ્રવાસ કરે છે. વિરલ આલેખનો મહત્તમ સ્વતંત્ર સમૂહ. મહત્તમ સમતલીય આલેખ અને પોલિહેડ્રલ આલેખ. આપેલ બિંદુ સમૂહ પર બિન-પાર લઘુત્તમ કઠોર આલેખ. આસપાસના બહુકોણ, બહુકોણ કે જે આપેલ કેટલાક બિંદુઓને શિરોબિંદુઓ તરીકે ધરાવે છે અને બાકીનાને ઘેરી લે છે, તે સ્થિતિ જગ્યાનો ઉપયોગ કરે છે જે બહુકોણના એક શિરોબિંદુને ઉમેરે છે અથવા દૂર કરે છે. બહિર્મુખ પોલીટોપ્સના મિન્કોવ્સ્કી સરવાળાના શિરોબિંદુઓ અથવા પાસાઓ. એકવિધ આદર્શોના ખૂણાઓ (બહુ-ડિગ્રી). સંદર્ભો શોધ અલ્ગોરિધમ્સ સંયુક્ત અલ્ગોરિધમ્સ