Bidirectional search
இருதரப்பு தேடல் என்பது ஒரு வரைபடத் தேடல் வழிமுறையாகும், இது ஒரு ஆரம்ப உச்சியில் இருந்து ஒரு இலக்கு உச்சிக்கு ஒரு குறுகிய பாதையைக் கண்டறிகிறது. இது ஒரே நேரத்தில் இரண்டு தேடல்களை இயக்குகிறதுஃ ஒன்று ஆரம்ப நிலையில் இருந்து முன்னோக்கி, மற்றும் இலக்கில் இருந்து பின்னோக்கி, இருவரும் சந்திக்கும் போது நிறுத்துகிறது. இந்த அணுகுமுறைக்கான காரணம் என்னவென்றால், பல சந்தர்ப்பங்களில் இது வேகமானதுஃ எடுத்துக்காட்டாக, தேடல் சிக்கல் சிக்கலின் எளிமைப்படுத்தப்பட்ட மாதிரியில், இரண்டு தேடல்களும் கிளை காரணி b உடன் ஒரு மரத்தை விரிவுபடுத்துகின்றன, மேலும் தொடக்கத்திலிருந்து இலக்குக்கான தூரம் d ஆகும், இரண்டு தேடல்களில் ஒவ்வொன்றும் சிக்கலான O (bd/2) (பிக் O குறியீட்டில்) உள்ளது, மேலும் இந்த இரண்டு தேடல் நேரங்களின் கூட்டுத்தொகையும் O (bd) சிக்கலை விட மிகக் குறைவு, இது தொடக்கத்திலிருந்து இலக்கு வரை ஒரே தேடலின் விளைவாக இருக்கும். ஆண்ட்ரூ கோல்ட்பர்க் மற்றும் பலர் டிஜ்க்ஸ்டிராவின் வழிமுறையின் இருதரப்பு பதிப்பிற்கான சரியான முடித்தல் நிபந்தனைகளை விளக்கினர். A * தேடலில் உள்ளதைப் போல, இரு-திசை தேடலை இலக்குக்கான மீதமுள்ள தூரத்தின் (முன்னோக்கி மரத்தில்) அல்லது தொடக்கத்திலிருந்து (பின்தங்கிய மரத்தில்) ஒரு ஹூரிஸ்டிக் மதிப்பீட்டின் மூலம் வழிநடத்த முடியும். இரு-திசை ஹூரிஸ்டிக் தேடல் வழிமுறையை வடிவமைத்து செயல்படுத்திய முதல் நபர் இவர்தான். தொடக்கத்தில் இருந்து வெளிவரும் தேடல் மரங்கள் மற்றும் இலக்கு முனைகள் தீர்வு இடத்தின் நடுவில் சந்திக்கத் தவறிவிட்டன. பி. எச். எஃப். எஃப். ஏ வழிமுறை இந்த குறைபாட்டை சாம்பியாக்ஸ் (1977) சரி செய்தது. ஏற்றுக்கொள்ளக்கூடிய ஹூரிஸ்டிக்கைப் பயன்படுத்தி ஒற்றை-திசை ஏ * வழிமுறையால் கண்டுபிடிக்கப்பட்ட ஒரு தீர்வு குறுகிய பாதை நீளத்தைக் கொண்டுள்ளது; டி சாம்பியாக்ஸ் (1983) இல் விவரிக்கப்பட்டுள்ள பி. எச். எஃப். எஃப். ஏ 2 இருதரப்பு ஹூரிஸ்டிக் பதிப்பிற்கு அதே பண்பு உள்ளது. மற்றவற்றுடன், பி. எச். எஃப். எஃப். ஏ-வை விட பி. எச். எஃப். எஃப். ஏ 2 மிகவும் கவனமான பணிநீக்க நிபந்தனைகளைக் கொண்டுள்ளது. இருதரப்பு ஹூரிஸ்டிக் தேடல் என்பது ஒரு மாநிலத்திலிருந்து மற்றொரு மாநிலத்திற்கு ஒரு மாநில விண்வெளி தேடல் ஆகும், இது ஒரே நேரத்தில் இருந்து தேடுகிறது. இது ஆபரேட்டர்களின் செல்லுபடியாகும் பட்டியலைத் தருகிறது, அதற்கு விண்ணப்பித்தால் அது நமக்குத் தரும். தலைகீழ் தேடலுக்கு ஆபரேட்டர்கள் தலைகீழாக இருக்க வேண்டும் என்று தோன்றலாம் என்றாலும், எந்தவொரு முனையையும் கொடுக்கும்போது, ஒவ்வொரு பெற்றோர் முனைகளிலிருந்தும் சில செல்லுபடியாகும் ஆபரேட்டர்கள் இருக்கும் வகையில் பெற்றோர் முனைகளின் தொகுப்பைக் கண்டறிய முடியும். இது பெரும்பாலும் பாதையைக் கண்டுபிடிக்கும் களத்தில் ஒரு வழி தெருவுடன் ஒப்பிடப்படுகிறதுஃ இரு திசைகளிலும் பயணிக்க வேண்டிய அவசியமில்லை, ஆனால் தெருவின் முடிவில் நிற்கும்போது தெருவின் தொடக்கத்தை சாத்தியமான பாதையாக தீர்மானிக்க வேண்டியது அவசியம். இதேபோல், தலைகீழ் வளைவுகளைக் கொண்ட விளிம்புகளுக்கு (அதாவது. இரு திசைகளிலும் செல்லும் வளைவுகள்) ஒவ்வொரு திசையும் சமமான செலவில் இருக்க வேண்டிய அவசியமில்லை. தலைகீழ் தேடல் எப்போதும் தலைகீழ் செலவைப் பயன்படுத்தும் (அதாவது. முன்னோக்கி திசையில் வளைவின் விலை). மேலும் முறைப்படி, பெற்றோர் கொண்ட ஒரு முனை என்றால், பின்னர், இருந்து செலவு என வரையறுக்கப்படுகிறது. (Auer Kaindl 2004) சொற்களஞ்சியம் மற்றும் குறியீடு ஒரு தேடல் மரத்தின் கிளையிடும் காரணி முனையிலிருந்து முனைக்கு நகர்வது தொடர்பான செலவு மூலத்திலிருந்து முனைக்குச் செல்வதற்கான செலவு முனைக்கும் இலக்குக்கும் இடையிலான தூரத்தின் ஹூரிஸ்டிக் மதிப்பீடு இலக்கு நிலையை (சில நேரங்களில், செயல்பாட்டுடன் குழப்பமடையக்கூடாது) தற்போதைய தேடல் திசையைக் குறிப்பிடுகிறது. வழக்கமாக, முன்னோக்கி திசையில் 1 க்கும், பின்தங்கிய திசையில் 2 க்கும் சமம் (குவா 1989) எதிர் தேடல் திசை (அதாவது) திசையில் உள்ள தேடல் மரம் d. என்றால், வேர் என்றால், வேர் என்பது இலைகள் (சில நேரங்களில் என குறிப்பிடப்படுகிறது). இந்த தொகுப்பிலிருந்து தான் விரிவாக்கத்திற்கு ஒரு முனை தேர்ந்தெடுக்கப்படுகிறது. இருதரப்பு தேடலில், இவை சில நேரங்களில் தேடல் 'எல்லைகள்' அல்லது 'அலை முனைகள்' என்று அழைக்கப்படுகின்றன, இது ஒரு தேடல் வரைபடமாக குறிப்பிடப்படும்போது அவை எவ்வாறு தோன்றும் என்பதைக் குறிக்கிறது. இந்த உருவகத்தில், விரிவாக்க கட்டத்தில், ஒரு அலைமுனையில் இருந்து ஒரு முனை எதிர் அலைமுனையில் வாரிசுகளைக் கொண்டிருப்பது கண்டறியப்படும் போது ஒரு 'மோதல்' ஏற்படுகிறது. இலை அல்லாத முனைகள். இந்த தொகுப்பில் ஏற்கனவே தேடல் அணுகுமுறைகளால் பார்வையிடப்பட்ட முனைகள் உள்ளன இருதரப்பு வழிமுறைகளை பரவலாக மூன்று பிரிவுகளாகப் பிரிக்கலாம்ஃ முன்-க்கு-முன், முன்-க்கு-பின் (அல்லது முன்-க்கு-முடிவு), மற்றும் சுற்றளவு தேடல் (கைண்டில் கைன்ஸ் 1997). இவை ஹூரிஸ்டிக் கணக்கிட பயன்படுத்தப்படும் செயல்பாட்டைப் பொறுத்து வேறுபடுகின்றன. முன்-பின்-பின் வழிமுறைகள் எதிர் தேடல் மரத்தின் மூலத்திற்கும் இடையே உள்ள ஹூரிஸ்டிக் மதிப்பீட்டைப் பயன்படுத்தி ஒரு முனையின் மதிப்பைக் கணக்கிடுகின்றன, அல்லது. ஃப்ரண்ட்-டு-பேக் என்பது மூன்று பிரிவுகளில் மிகவும் தீவிரமாக ஆராய்ச்சி செய்யப்பட்டுள்ளது. தற்போதைய சிறந்த வழிமுறை (குறைந்தபட்சம் பதினைந்து புதிர் களத்தில்) BiMAX-BS * F வழிமுறை ஆகும், இது Auer மற்றும் Kaindl (Auer, Kaindl 2004) ஆல் உருவாக்கப்பட்டது. முன்-முதல்-முன் வழிமுறைகள் மற்றும் சில துணைக்குழுக்களுக்கு இடையிலான ஹூரிஸ்டிக் மதிப்பீட்டைப் பயன்படுத்தி ஒரு முனையின் மதிப்பைக் கணக்கிடுகின்றன. நியதி உதாரணம் பி. எச். எஃப். எஃப். ஏ (இருதரப்பு ஹூரிஸ்டிக் ஃப்ரண்ட்-டு-ஃப்ரண்ட் அல்காரிதம்) ஆகும், இதில் செயல்பாடு தற்போதைய முனைக்கும் எதிர் முனையில் உள்ள முனைகளுக்கும் இடையிலான அனைத்து ஹூரிஸ்டிக் மதிப்பீடுகளின் குறைந்தபட்சமாக வரையறுக்கப்படுகிறது. அல்லது, முறைப்படிஃ ஏற்றுக்கொள்ளக்கூடிய (அதாவது. முனைகள் மற்றும் முனைகளுக்கு இடையிலான தூரத்தை மிகைப்படுத்தி மதிப்பிடவில்லை). ஃப்ரண்ட்-டு-ஃப்ரண்ட் அதிகப்படியான கணக்கீட்டு கோரிக்கையால் பாதிக்கப்படுகிறது. ஒவ்வொரு முறையும் ஒரு முனை திறந்த பட்டியலில் வைக்கப்படும்போது, அதன் மதிப்பு கணக்கிடப்பட வேண்டும். மேலே விவரிக்கப்பட்டுள்ளபடி, எதிர் தொகுப்பில் உள்ள ஒவ்வொரு முனையிலிருந்தும் ஒரு ஹூரிஸ்டிக் மதிப்பீட்டைக் கணக்கிடுவது இதில் அடங்கும். அனைத்து களங்களுக்கும் செட் அளவு அதிவேகமாக அதிகரிக்கிறது. குறிப்புகள். . . . வரைபட வழிமுறைகள் தேடல் வழிமுறைகள்