Bidirectional search
દ્વિદિશાત્મક શોધ એ આલેખ શોધ અલ્ગોરિધમ છે જે નિર્દેશિત આલેખમાં પ્રારંભિક શિરોબિંદુથી લક્ષ્ય શિરોબિંદુ સુધીનો ટૂંકો માર્ગ શોધે છે. તે એક સાથે બે શોધ ચલાવે છેઃ એક પ્રારંભિક સ્થિતિથી આગળ અને એક ગોલથી પાછળ, જ્યારે બંને મળે ત્યારે અટકી જાય છે. આ અભિગમ માટેનું કારણ એ છે કે ઘણા કિસ્સાઓમાં તે ઝડપી હોય છેઃ દાખલા તરીકે, શોધ સમસ્યાની જટિલતાના સરળ મોડેલમાં જેમાં બંને શોધ શાખા પરિબળ b સાથે વૃક્ષને વિસ્તૃત કરે છે, અને શરૂઆતથી લક્ષ્ય સુધીનું અંતર d હોય છે, બે શોધોમાંની દરેકમાં જટિલતા O (bd/2) (મોટા O સંકેતલિપીમાં) હોય છે, અને આ બે શોધ સમયનો સરવાળો O (bd) જટિલતા કરતાં ઘણો ઓછો હોય છે જે શરૂઆતથી લક્ષ્ય સુધી એક જ શોધથી પરિણમે છે. એન્ડ્રુ ગોલ્ડબર્ગ અને અન્યોએ ડિજ્ક્સ્ટ્રાના અલ્ગોરિધમના દ્વિદિશાત્મક સંસ્કરણ માટે યોગ્ય સમાપ્તિ શરતો સમજાવી. એ * શોધની જેમ, દ્વિ-દિશાત્મક શોધને લક્ષ્ય (આગળના વૃક્ષમાં) અથવા શરૂઆતથી (પછાત વૃક્ષમાં) બાકીના અંતરના સંશોધનાત્મક અંદાજ દ્વારા માર્ગદર્શન આપી શકાય છે. તે દ્વિ-દિશાત્મક હ્યુરિસ્ટિક સર્ચ અલ્ગોરિધમની રચના અને અમલ કરનાર પ્રથમ વ્યક્તિ હતા. શરૂઆતથી નીકળતા વૃક્ષો શોધો અને ગોલ નોડ્સ ઉકેલ જગ્યાની મધ્યમાં મળવામાં નિષ્ફળ ગયા. બી. એચ. એફ. એફ. એ. અલ્ગોરિધમે આ ખામીને ચામપેક્સ (1977) માં સુધારી હતી. સ્વીકાર્ય હ્યુરિસ્ટિકનો ઉપયોગ કરીને યુનિ-ડાયરેક્શનલ A * અલ્ગોરિધમ દ્વારા શોધાયેલ ઉકેલની પાથ લંબાઈ ટૂંકી હોય છે; આ જ ગુણધર્મ ડી શેમ્પિઓક્સ (1983) માં વર્ણવેલ BHFFA2 બાયડાયરેક્શનલ હ્યુરિસ્ટિક વર્ઝન માટે છે. બી. એચ. એફ. એફ. એ. 2, અન્યમાં, બી. એચ. એફ. એફ. એ. કરતાં વધુ સાવચેતીપૂર્વક સમાપ્તિ શરતો ધરાવે છે. વર્ણન દ્વિદિશાત્મક હ્યુરિસ્ટિક સર્ચ એ અમુક રાજ્યમાંથી બીજા રાજ્યમાં એક રાજ્ય અવકાશ શોધ છે, જે એક સાથે આવે છે અને જાય છે. તે ઓપરેટરોની માન્ય સૂચિ આપે છે જેને જો લાગુ કરવામાં આવે તો તે આપણને આપશે. જ્યારે એવું લાગે છે કે ઓપરેટરોએ રિવર્સ સર્ચ માટે ઇન્વર્ટિબલ હોવું જોઈએ, ત્યારે કોઈપણ નોડને જોતાં, પેરેન્ટ નોડ્સનો સમૂહ શોધવામાં સક્ષમ બનવું જરૂરી છે, જેમ કે દરેક પેરેન્ટ નોડ્સમાંથી કેટલાક માન્ય ઓપરેટર અસ્તિત્વમાં છે. આને ઘણીવાર માર્ગ શોધવાના ક્ષેત્રમાં એક તરફી શેરી સાથે સરખાવવામાં આવે છેઃ બંને દિશામાં નીચે મુસાફરી કરવામાં સક્ષમ હોવું જરૂરી નથી, પરંતુ શેરીના અંતે ઊભા રહીને શેરીની શરૂઆતને સંભવિત માર્ગ તરીકે નક્કી કરવી જરૂરી છે. તેવી જ રીતે, તે કિનારીઓ માટે કે જેમાં ઊંધી કમાન હોય (એટલે કે. ચાપ બંને દિશામાં જાય છે) તે જરૂરી નથી કે દરેક દિશા સમાન કિંમતની હોય. વિપરીત શોધ હંમેશા વિપરીત કિંમતનો ઉપયોગ કરશે (એટલે કે. આગળની દિશામાં ચાપની કિંમત). વધુ ઔપચારિક રીતે, જો પેરેન્ટ સાથેનો નોડ હોય, તો તેને થી થી ની કિંમત તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. (Auer Kaindl 2004) પરિભાષા અને સંકેત શોધ વૃક્ષની શાખાઓનું પરિબળ નોડથી નોડ તરફ જવા સાથે સંકળાયેલ ખર્ચ, મૂળથી નોડ તરફનો ખર્ચ, નોડ અને ધ્યેય વચ્ચેના અંતરનો સંશોધનાત્મક અંદાજ, લક્ષ્ય સ્થિતિ (કેટલીકવાર, કાર્ય સાથે મૂંઝવણ ન કરવી) વર્તમાન શોધ દિશા દર્શાવે છે. પરંપરા મુજબ, આગળની દિશા માટે 1 અને પાછળની દિશા માટે 2 ની બરાબર છે (ક્વા 1989) વિરુદ્ધ શોધ દિશા (એટલે કે) શોધ વૃક્ષની દિશામાં d. જો, મૂળ છે, જો, મૂળ એ પાંદડા છે (કેટલીકવાર તરીકે ઓળખવામાં આવે છે). આ સમૂહમાંથી વિસ્તરણ માટે નોડ પસંદ કરવામાં આવે છે. દ્વિદિશાત્મક શોધમાં, તેને કેટલીકવાર શોધ 'સરહદો' અથવા 'વેવફ્રન્ટ' કહેવામાં આવે છે, જે શોધને ગ્રાફિકલી રીતે રજૂ કરવામાં આવે ત્યારે તે કેવી રીતે દેખાય છે તેનો ઉલ્લેખ કરે છે. આ રૂપકમાં, 'અથડામણ' ત્યારે થાય છે જ્યારે, વિસ્તરણના તબક્કા દરમિયાન, એક વેવફ્રન્ટમાંથી નોડ વિરોધી વેવફ્રન્ટમાં અનુગામી હોવાનું જોવા મળે છે. ના બિન-પર્ણ ગાંઠો. આ સમૂહમાં દ્વિદિશાત્મક સંશોધનાત્મક શોધ માટે શોધ અભિગમો દ્વારા પહેલેથી જ મુલાકાત લેવાયેલા નોડ્સ છે દ્વિદિશાત્મક અલ્ગોરિધમ્સને વ્યાપક રીતે ત્રણ વર્ગોમાં વિભાજિત કરી શકાય છેઃ ફ્રન્ટ-ટુ-ફ્રન્ટ, ફ્રન્ટ-ટુ-બેક (અથવા ફ્રન્ટ-ટુ-એન્ડ), અને પરિમિતિ શોધ (કેન્ડલ કેન્ઝ 1997). આ હ્યુરિસ્ટિકની ગણતરી કરવા માટે ઉપયોગમાં લેવાતા કાર્ય દ્વારા અલગ પડે છે. ફ્રન્ટ-ટુ-બેક એલ્ગોરિધમ્સ વિરુદ્ધ શોધ વૃક્ષની વચ્ચે અને મૂળના સંશોધનાત્મક અંદાજનો ઉપયોગ કરીને નોડના મૂલ્યની ગણતરી કરે છે, અથવા. ફ્રન્ટ-ટુ-બેક એ ત્રણ શ્રેણીઓમાં સૌથી વધુ સક્રિય સંશોધન છે. વર્તમાન શ્રેષ્ઠ અલ્ગોરિધમ (ઓછામાં ઓછું પંદર પઝલ ડોમેનમાં) એ BiMAX-BS * F અલ્ગોરિધમ છે, જે Auer અને Kaindl (Auer, Kaindl 2004) દ્વારા બનાવવામાં આવ્યું છે. ફ્રન્ટ-ટુ-ફ્રન્ટ અલ્ગોરિધમ્સ અને તેના કેટલાક સબસેટ વચ્ચેના હ્યુરિસ્ટિક અંદાજનો ઉપયોગ કરીને નોડના મૂલ્યની ગણતરી કરે છે. કેનોનિકલ ઉદાહરણ બી. એચ. એફ. એફ. એ. (બાયડાયરેક્શનલ હ્યુરિસ્ટિક ફ્રન્ટ-ટુ-ફ્રન્ટ અલ્ગોરિધમ) નું છે, જ્યાં કાર્યને વર્તમાન નોડ અને વિરોધી ફ્રન્ટ પરના નોડ વચ્ચેના તમામ હ્યુરિસ્ટિક અંદાજોના લઘુત્તમ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. અથવા, ઔપચારિક રીતેઃ જ્યાં સ્વીકાર્ય વળતર મળે છે (એટલે કે. ગાંઠો અને ગાંઠો વચ્ચેના અંતરનો અનુમાનાત્મક અંદાજ) વધુ પડતો અંદાજ નથી. ફ્રન્ટ-ટુ-ફ્રન્ટ અતિશય કોમ્પ્યુટેશનલ માંગથી પીડાય છે. દર વખતે જ્યારે નોડને ખુલ્લી સૂચિમાં મૂકવામાં આવે છે, ત્યારે તેની કિંમતની ગણતરી કરવી આવશ્યક છે. આમાં ઉપર વર્ણવ્યા મુજબ, વિરોધી સમૂહમાં દરેક નોડથી હ્યુરિસ્ટિક અંદાજની ગણતરીનો સમાવેશ થાય છે. સાથે તમામ ડોમેન્સ માટે સમૂહોના કદમાં ઝડપથી વધારો થાય છે. સંદર્ભો. . . . આલેખ અલ્ગોરિધમ્સ શોધ અલ્ગોરિધમ્સ