Contraction hierarchies
கணினி அறிவியலில், சுருக்க படிநிலைகளின் முறை என்பது ஒரு வரைபடத்தில் குறுகிய பாதையைக் கண்டுபிடிப்பதற்கான வேகத்தை அதிகரிக்கும் நுட்பமாகும். மிகவும் உள்ளுணர்வு பயன்பாடுகள் கார்-வழிசெலுத்தல் அமைப்புகள் ஆகும்ஃ ஒரு பயனர் விரைவாக சாத்தியமான வழியைப் பயன்படுத்த விரும்புகிறார். இங்கே உகந்த அளவீடு பயண நேரம் ஆகும். குறுக்குவெட்டுகள் செங்குத்துகளால் குறிக்கப்படுகின்றன, சாலைப் பிரிவுகள் அவற்றை விளிம்புகளால் இணைக்கின்றன. விளிம்பு எடைகள் சாலையின் இந்த பகுதியில் வாகனம் ஓட்ட எடுக்கும் நேரத்தைக் குறிக்கின்றன. ஒரு பாதை என்பது விளிம்புகளின் வரிசை (சாலை பிரிவுகள்); குறுகிய பாதை என்பது சாத்தியமான அனைத்து பாதைகளிலும் குறைந்தபட்ச விளிம்பு எடைகளைக் கொண்ட பாதையாகும். ஒரு வரைபடத்தில் உள்ள குறுகிய பாதையை டிஜ்க்ஸ்டிராவின் வழிமுறையைப் பயன்படுத்தி கணக்கிட முடியும், ஆனால், சாலை நெட்வொர்க்குகள் பல்லாயிரக்கணக்கான செங்குத்துகளைக் கொண்டிருப்பதால், இது நடைமுறைக்கு மாறானது. சுருக்கம் படிநிலைகள் என்பது சாலை நெட்வொர்க்குகளைக் குறிக்கும் வரைபடங்களின் பண்புகளை சுரண்ட உகந்த வேகத்தை அதிகரிக்கும் முறையாகும். முன்கூட்டிய செயலாக்க கட்டத்தில் குறுக்குவழிகளை உருவாக்குவதன் மூலம் வேகம் அதிகரிக்கப்படுகிறது, பின்னர் அவை "முக்கியமற்ற" செங்குத்துகளைத் தவிர்க்க குறுகிய பாதை வினவலின் போது பயன்படுத்தப்படுகின்றன. இது சாலை நெட்வொர்க்குகள் மிகவும் படிநிலைப்படுத்தப்பட்டவை என்ற அவதானிப்பை அடிப்படையாகக் கொண்டது. சில குறுக்குவெட்டுகள், எடுத்துக்காட்டாக நெடுஞ்சாலை சந்திப்புகள், "மிகவும் முக்கியமானவை" மற்றும் படிநிலையில் உயர்ந்தவை, எடுத்துக்காட்டாக ஒரு முற்றுப்புள்ளிக்கு வழிவகுக்கும் சந்திப்பை விட. இரண்டு முக்கியமான சந்திப்புகளுக்கு இடையிலான முன்கூட்டியே கணக்கிடப்பட்ட தூரத்தை சேமிக்க குறுக்குவழிகளைப் பயன்படுத்தலாம், அதாவது அல்காரிதம் வினவல் நேரத்தில் இந்த சந்திப்புகளுக்கு இடையிலான முழு பாதையையும் கருத்தில் கொள்ள வேண்டியதில்லை. மனிதர்கள் எந்த சாலைகளை "முக்கியமானவை" என்று கருதுகிறார்கள் என்பது சுருக்க படிநிலைகளுக்குத் தெரியாது (எ. கா. நெடுஞ்சாலைகள்), ஆனால் அவை உள்ளீடாக வரைபடத்துடன் வழங்கப்படுகின்றன, மேலும் அவை ஹூரிஸ்டிக்ஸ் பயன்படுத்தி செங்குத்துகளுக்கு முக்கியத்துவத்தை ஒதுக்க முடியும். சுருக்கம் படிநிலைகள் கார்-வழிசெலுத்தல் அமைப்புகளில் வேகமான வழிமுறைகளுக்கு மட்டுமல்லாமல், வலை அடிப்படையிலான பாதைத் திட்டமிடுபவர்கள், போக்குவரத்து உருவகப்படுத்துதல் மற்றும் தளவாட உகப்பாக்கம் ஆகியவற்றிலும் பயன்படுத்தப்படுகின்றன. வழிமுறையின் செயல்பாடுகள் திறந்த மூல மென்பொருளாக பொதுவில் கிடைக்கின்றன. சுருக்கம் படிநிலைகள் (சிஎச்) வழிமுறை என்பது ஒரு முன் செயலாக்க கட்டம் மற்றும் ஒரு வினவல் கட்டத்தைக் கொண்ட குறுகிய பாதை சிக்கலுக்கான இரண்டு கட்ட அணுகுமுறையாகும். சாலை நெட்வொர்க்குகள் எப்போதாவது மாறுவதால், கேள்விகளுக்கு பதிலளிப்பதற்கு முன்பு சில கணக்கீடுகளை முன்கூட்டியே கணக்கிட அதிக நேரம் (விநாடிகள் முதல் மணி நேரம் வரை) பயன்படுத்தப்படலாம். இந்த முன்கூட்டியே கணக்கிடப்பட்ட தரவைப் பயன்படுத்தி, பல கேள்விகளுக்கு மிகக் குறைந்த நேரத்தை (மைக்ரோ விநாடிகள்) எடுத்து பதிலளிக்க முடியும். இந்த வேகத்தை அடைய சிஎச்எஸ் குறுக்குவழிகளை நம்பியுள்ளது. ஒரு குறுக்குவழி இரண்டு செங்குத்துகளை இணைக்கிறது மற்றும் அசல் வரைபடத்தில் அருகில் இல்லை. அதன் விளிம்பு எடை என்பது குறுகிய பாதையில் உள்ள விளிம்பு எடைகளின் கூட்டுத்தொகையாகும். ஒரு நெடுஞ்சாலையால் இணைக்கப்பட்டுள்ள இரண்டு பெரிய நகரங்களைக் கவனியுங்கள். இந்த இரண்டு நகரங்களுக்கும் இடையில், சிறிய கிராமங்கள் மற்றும் புறநகர்ப் பகுதிகளுக்குச் செல்லும் ஏராளமான சந்திப்புகள் உள்ளன. பெரும்பாலான ஓட்டுநர்கள் ஒரு நகரத்திலிருந்து மற்றொன்றுக்குச் செல்ல விரும்புகிறார்கள்-ஒருவேளை ஒரு பெரிய பாதையின் ஒரு பகுதியாக இருக்கலாம்-வழியில் வெளியேறும் வழிகளில் ஒன்றை எடுக்க வேண்டாம். இந்த சாலை அமைப்பைக் குறிக்கும் வரைபடத்தில், ஒவ்வொரு குறுக்குவெட்டும் ஒரு முனையால் குறிக்கப்படுகிறது மற்றும் அண்டை குறுக்குவெட்டுகளுக்கு இடையில் விளிம்புகள் உருவாக்கப்படுகின்றன. இந்த இரண்டு நகரங்களுக்கிடையிலான தூரத்தை கணக்கிட, வழிமுறை வழியில் உள்ள அனைத்து விளிம்புகளையும் கடந்து, அவற்றின் நீளத்தை சேர்க்க வேண்டும். இந்த தூரத்தை ஒரு முறை முன்கூட்டியே கணக்கிடுவதும், இரண்டு பெரிய நகரங்களுக்கு இடையில் உருவாக்கப்பட்ட கூடுதல் விளிம்பில் சேமித்து வைப்பதும் ஒவ்வொரு முறையும் இந்த நெடுஞ்சாலையை ஒரு வினவலில் மதிப்பீடு செய்ய வேண்டியிருக்கும். இந்த கூடுதல் விளிம்பு ஒரு "குறுக்குவழி" என்று அழைக்கப்படுகிறது மற்றும் நிஜ உலகில் எந்த எதிர்ப்பாளரும் இல்லை. சுருக்க படிநிலை வழிமுறைக்கு சாலை வகைகளைப் பற்றி எந்த அறிவும் இல்லை, ஆனால் வரைபடத்தை உள்ளீடாகப் பயன்படுத்தி மட்டுமே எந்த குறுக்குவழிகளை உருவாக்க வேண்டும் என்பதை தீர்மானிக்க முடியும். முன் செயலாக்க கட்டம் சிஎச் வழிமுறை தேடல் இடத்தை குறைக்க முன் செயலாக்க கட்டத்தில் உருவாக்கப்பட்ட குறுக்குவழிகளை நம்பியுள்ளது-அதாவது வினவல் நேரத்தில் சிஎச் பார்க்க வேண்டிய செங்குத்துகளின் எண்ணிக்கை. இதை அடைய, மறுசுழற்சி உச்சி சுருக்கங்கள் செய்யப்படுகின்றன. ஒரு உச்சியை சுருக்கும்போது அது வரைபடத்திலிருந்து தற்காலிகமாக அகற்றப்படுகிறது, மேலும் ஒவ்வொரு ஜோடி அண்டை செங்குத்துகளுக்கும் இடையில் ஒரு குறுக்குவழி உருவாக்கப்படுகிறது. இடையில் உள்ள குறுகிய பாதை மற்றும் உள்ளதா என்பதை தீர்மானிக்கும் செயல்முறை சாட்சி தேடல் என்று அழைக்கப்படுகிறது. எடுத்துக்காட்டாக, இன்னும் சுருங்காத முனைகளைப் பயன்படுத்தி முன்னோக்கி தேடலைப் பயன்படுத்துவதற்கான பாதையை கணக்கிடுவதன் மூலம் இதைச் செய்யலாம். முனை வரிசை உள்ளீட்டு வரைபடத்தின் செங்குத்துகள் சுருக்கங்கள் மூலம் வரைபடத்தில் சேர்க்கப்பட்ட விளிம்புகளின் எண்ணிக்கையைக் குறைக்கும் வகையில் சுருங்க வேண்டும். உகந்த முனை வரிசை NP-முழுமையானது என்பதால், ஹூரிஸ்டிக்ஸ் பயன்படுத்தப்படுகிறது. கீழ்-மேல் மற்றும் மேல்-கீழ் ஹூரிஸ்டிக்ஸ் உள்ளன. ஒருபுறம், கணக்கீட்டு ரீதியாக மலிவான பாட்டம்-அப் ஹூரிஸ்டிக்ஸ் ஒரு பேராசை பாணியில் செங்குத்துகளை சுருக்கும் வரிசையை தீர்மானிக்கிறது; இதன் பொருள் வரிசை முன்கூட்டியே அறியப்படவில்லை, மாறாக முந்தைய சுருக்கம் முடிந்த பிறகு சுருக்கத்திற்கு அடுத்த முனை தேர்ந்தெடுக்கப்படுகிறது. மறுபுறம் மேல்-கீழ் ஹூரிஸ்டிக்ஸ் முதல் முனை சுருங்குவதற்கு முன்பு முழு முனை வரிசையையும் முன்கூட்டியே கணக்கிடுகிறது. இது சிறந்த முடிவுகளைத் தருகிறது, ஆனால் அதிக முன் செயலாக்க நேரம் தேவைப்படுகிறது. பாட்டம்-அப் ஹூரிஸ்டிக்ஸில், சுருக்கத்திற்கான அடுத்த உச்சியைத் தேர்ந்தெடுக்க காரணிகளின் கலவை பயன்படுத்தப்படுகிறது. குறுக்குவழிகளின் எண்ணிக்கை முன்கூட்டிய செயலாக்கம் மற்றும் வினவல் இயக்க நேரத்தை தீர்மானிக்கும் முதன்மை காரணியாக இருப்பதால், அதை முடிந்தவரை சிறியதாக வைத்திருக்க விரும்புகிறோம். சுருக்கத்திற்கான அடுத்த முனையைத் தேர்ந்தெடுப்பதற்கான மிக முக்கியமான சொல், எனவே ஒரு முனை சுருங்கும் போது சேர்க்கப்படும் விளிம்புகளின் நிகர எண்ணிக்கை ஆகும். இது சுருக்கப்பட்டால் உருவாக்கப்படும் குறுக்குவழிகளின் எண்ணிக்கை எங்கே மற்றும் விளிம்புகளின் எண்ணிக்கை எங்கே என்று வரையறுக்கப்படுகிறது. இந்த அளவுகோலைப் பயன்படுத்தி மட்டும், ஒரு நேரியல் பாதை ஒரு நேரியல் படிநிலை (பல நிலைகள்) மற்றும் உருவாக்கப்பட்ட குறுக்குவழிகளை விளைவிக்கும். ஏற்கனவே சுருக்கப்பட்ட அருகிலுள்ள செங்குத்துகளின் எண்ணிக்கையைக் கருத்தில் கொள்வதன் மூலம், ஒரு சீரான சுருக்கம் மற்றும் ஒரு தட்டையான படிநிலை (குறைந்த நிலைகள்) அடையப்படுகிறது. உதாரணமாக, ஒவ்வொரு முனையிலும் ஒரு கவுண்டரை பராமரிப்பதன் மூலம் இது செய்யப்படலாம், இது ஒவ்வொரு முறையும் அண்டை முனை சுருங்கும் போது அதிகரிக்கப்படுகிறது. குறைந்த கவுண்டர்களைக் கொண்ட முனைகள் பின்னர் அதிக கவுண்டர்களைக் கொண்ட முனைகளை விட விரும்பப்படுகின்றன. மறுபுறம், மேல்-கீழ் ஹூரிஸ்டிக்ஸ் சிறந்த முடிவுகளைத் தருகிறது, ஆனால் அதிக முன் செயலாக்க நேரம் தேவைப்படுகிறது. பல குறுகிய பாதைகளின் ஒரு பகுதியாக இருக்கும் செங்குத்துகளை ஒரு சில குறுகிய பாதைகளுக்கு மட்டுமே தேவைப்படும் செங்குத்துகளை விட முக்கியமானவை என்று அவை வகைப்படுத்துகின்றன. நெஸ்டட் டிசெக்ஷன்களைப் பயன்படுத்தி இதை தோராயமாக மதிப்பிடலாம். ஒரு உள்ளமைக்கப்பட்ட பிரிவைக் கணக்கிட, ஒருவர் ஒரு வரைபடத்தை மீண்டும் மீண்டும் இரண்டு பகுதிகளாகப் பிரிக்கிறார், அவை பின்னர் இரண்டு பகுதிகளாகப் பிரிக்கப்படுகின்றன. அதாவது, கணுக்களின் துணைக்குழுவைக் கண்டறியவும், அவை வரைபடத்திலிருந்து அகற்றப்படும்போது தோராயமாக சம அளவிலான இரண்டு துண்டுகளாகப் பிரிக்கப்படுகின்றன. அனைத்து முனைகளையும் முனை வரிசையில் கடைசியாக வைக்கவும், பின்னர் உள்ளமைக்கப்பட்ட பிரிவை மீண்டும் மீண்டும் கணக்கிடவும், உள்ளுணர்வு என்னவென்றால், வரைபடத்தின் ஒரு பாதியிலிருந்து வரைபடத்தின் மற்ற பாதி வரையிலான அனைத்து கேள்விகளும் சிறிய பிரிப்பான் வழியாக செல்ல வேண்டும், எனவே இந்த பிரிப்பானில் உள்ள முனைகள் அதிக முக்கியத்துவம் வாய்ந்தவை. அவற்றின் சிறிய பிரிப்பான்களின் காரணமாக சாலை நெட்வொர்க்குகளில் உள்ளமைக்கப்பட்ட துண்டுகளை திறம்பட கணக்கிட முடியும். வினவல் கட்டத்தில், ஆரம்ப முனை மற்றும் அசல் வரைபடத்தில் உள்ள இலக்கு முனை ஆகியவற்றிலிருந்து தொடங்கி இருதரப்பு தேடல் செய்யப்படுகிறது, இது முன் செயலாக்க கட்டத்தில் உருவாக்கப்பட்ட குறுக்குவழிகளால் அதிகரிக்கப்படுகிறது. மற்றும் இடையே உள்ள குறுகிய பாதையில் மிக முக்கியமான உச்சி ஒன்று அல்லது அவை அல்லது இரண்டையும் விட முக்கியமானதாக இருக்கும். எனவே, வெர்டெக்ஸ் மினிமைசிங் அசல் வரைபடத்தில் குறுகிய பாதையில் உள்ளது மற்றும் வைத்திருக்கிறது. இது, குறுக்குவழிகள் எவ்வாறு உருவாக்கப்படுகின்றன என்பதோடு இணைந்து, முன்னோக்கி மற்றும் பின்தங்கிய தேடல் இரண்டுமே படிமுறையில் மிக முக்கியமான முனைகளுக்கு (மேல்நோக்கி) வழிவகுக்கும் விளிம்புகளை மட்டுமே தளர்த்த வேண்டும், இது தேடல் இடத்தை சிறியதாக வைத்திருக்கிறது. அனைத்து மேல் (கீழ்)-கீழ் பாதைகளிலும், உள் (கீழ்) பாதையைத் தவிர்க்கலாம், ஏனெனில் முன்கூட்டிய செயலாக்க கட்டத்தில் ஒரு குறுக்குவழி உருவாக்கப்பட்டுள்ளது. பாதை மீட்டெடுப்பு ஒரு சிஎச் வினவல், மேலே விவரிக்கப்பட்டுள்ளபடி, நேரம் அல்லது தூரத்தை வழங்குகிறது, ஆனால் உண்மையான பாதையை அல்ல. குறுகிய பாதையில் உள்ள விளிம்புகளின் (சாலைகள்) பட்டியலைப் பெற, எடுக்கப்பட்ட குறுக்குவழிகளை அவிழ்க்க வேண்டும். ஒவ்வொரு குறுக்குவழியும் இரண்டு விளிம்புகளின் இணைப்பாகும்ஃ அசல் வரைபடத்தின் இரண்டு விளிம்புகள், அல்லது இரண்டு குறுக்குவழிகள், அல்லது ஒரு அசல் விளிம்பு மற்றும் ஒரு குறுக்குவழி. சுருக்கத்தின் போது ஒவ்வொரு குறுக்குவழியின் நடுத்தர முனையையும் சேமிப்பது குறுகிய பாதையை நேரியல்-நேர மறுநிகழ்வு திறப்பதற்கு உதவுகிறது. தனிப்பயனாக்கப்பட்ட சுருக்க படிநிலைகள் நெட்வொர்க் இடவியலை விட விளிம்பு எடைகள் அடிக்கடி மாற்றப்பட்டால், முன் செயலாக்கம் மற்றும் வினவல் கட்டத்திற்கு இடையில் தனிப்பயனாக்குதல் கட்டத்தை சேர்ப்பதன் மூலம் சிஎச் மூன்று கட்ட அணுகுமுறைக்கு நீட்டிக்கப்படலாம். எடுத்துக்காட்டாக, குறுகிய தூரத்திற்கும் குறுகிய நேரத்திற்கும் இடையில் மாற இது பயன்படுத்தப்படலாம் அல்லது தற்போதைய போக்குவரத்துத் தகவல்களையும், சில வகையான சாலைகளைத் (படகுகள், நெடுஞ்சாலைகள்) தவிர்ப்பது போன்ற பயனர் விருப்பங்களையும் சேர்க்கலாம். முன்கூட்டிய செயலாக்க கட்டத்தில், இயக்க நேரத்தின் பெரும்பகுதி முனைகள் சுருக்கப்பட்ட வரிசையை கணக்கிட செலவிடப்படுகிறது. முன்கூட்டிய செயலாக்க கட்டத்தில் சுருக்க செயல்பாடுகளின் இந்த வரிசையை அவை பின்னர் தனிப்பயனாக்குதல் கட்டத்தில் தேவைப்படும்போது சேமிக்க முடியும். ஒவ்வொரு முறையும் மெட்ரிக் தனிப்பயனாக்கப்படும்போது, தனிப்பயன் மெட்ரிக் பயன்படுத்தி சேமிக்கப்பட்ட வரிசையில் சுருக்கங்களை திறம்பட பயன்படுத்தலாம். கூடுதலாக, புதிய விளிம்பு எடைகளைப் பொறுத்து சில குறுக்குவழிகளை மீண்டும் கணக்கிட வேண்டியிருக்கலாம். இது வேலை செய்ய, சுருக்க வரிசை மெட்ரிக்-சுயாதீனமான உள்ளமைக்கப்பட்ட விலகல்களைப் பயன்படுத்தி கணக்கிடப்பட வேண்டும். மேலே விவரிக்கப்பட்டுள்ளபடி நீட்டிப்புகள் மற்றும் பயன்பாடுகள் சிஎச்எஸ் ஒரு தொடக்க முனையிலிருந்து ஒரு இலக்கு முனைக்கு குறுகிய பாதையைத் தேடுகின்றன. இது ஒன்றுக்கு ஒன்று குறுகிய பாதை என்று அழைக்கப்படுகிறது மற்றும் எடுத்துக்காட்டாக கார்-வழிசெலுத்தல் அமைப்புகளில் பயன்படுத்தப்படுகிறது. மற்ற பயன்பாடுகளில் ஜி. பி. எஸ் தடங்களை சாலைப் பிரிவுகளுடன் பொருத்துவது மற்றும் போக்குவரத்து சிமுலேட்டர்களை விரைவுபடுத்துவது ஆகியவை அடங்கும், அவை ஒரு நெட்வொர்க்கில் உள்ள அனைத்து ஓட்டுநர்களும் எடுக்கும் பாதைகளை கருத்தில் கொள்ள வேண்டும். பாதை முன்கணிப்பில், ஒரு வாகனம் அதன் தற்போதைய மற்றும் கடந்த நிலைகள் அதன் தொடக்க புள்ளியில் இருந்து எந்தவொரு சாத்தியமான இலக்குக்கும் குறுகிய பாதையுடன் எவ்வளவு நன்றாக உடன்படுகின்றன என்பதைக் கணக்கிடுவதன் மூலம் ஒரு வாகனம் எங்கு செல்கிறது என்பதை மதிப்பிட முயற்சிக்கிறது. சிஎச்எஸ் பயன்படுத்தி இதை திறம்பட செய்ய முடியும். ஒன்று முதல் பல சூழ்நிலைகளில், ஒரு தொடக்க முனை மற்றும் இலக்கு முனைகளின் தொகுப்பு கொடுக்கப்பட்டு, அனைத்திற்கும் தூரம் கணக்கிடப்பட வேண்டும். ஒன்று முதல் பல கேள்விகளுக்கான மிக முக்கியமான பயன்பாடு பாயிண்ட் ஆஃப் இன்டெரெஸ்ட் தேடல்கள் ஆகும். புவியியல் தூரத்திற்கு பதிலாக உண்மையான பயண நேரத்தைப் பயன்படுத்தி அருகிலுள்ள எரிவாயு நிலையம், உணவகம் அல்லது தபால் நிலையத்தைக் கண்டுபிடிப்பது பொதுவான எடுத்துக்காட்டுகளில் அடங்கும். பல முதல் பல குறுகிய பாதை சூழ்நிலையில், தொடக்க முனைகளின் தொகுப்பு மற்றும் இலக்கு முனைகளின் தொகுப்பு கொடுக்கப்பட்டு அனைத்திற்கும் தூரம் கணக்கிடப்பட வேண்டும். இது எடுத்துக்காட்டாக லாஜிஸ்டிக் பயன்பாடுகளில் பயன்படுத்தப்படுகிறது. சிஎச்எஸ் பின்வரும் முறையில் பல கேள்விகளுக்கு நீட்டிக்கப்படலாம். முதலில், ஒவ்வொன்றிலிருந்தும் பின்னோக்கி மேல்நோக்கி தேடுங்கள். இந்த தேடலின் போது ஸ்கேன் செய்யப்பட்ட ஒவ்வொரு உச்சிக்கும், ஒரு வாளியில் ஒரு கடை. பின்னர், ஒருவர் ஒவ்வொருவரிடமிருந்தும் முன்னோக்கி மேல்நோக்கி தேடுகிறார், காலியாக இல்லாத ஒவ்வொரு வாளியையும் சரிபார்க்கிறார், தொடர்புடைய உச்சியில் உள்ள பாதை ஏதேனும் சிறந்த தூரத்தை மேம்படுத்துகிறதா என்று சரிபார்க்கிறார். அதாவது, ஏதேனும் இருந்தால். சில பயன்பாடுகளுக்கு ஒன்-டு-ஆல் கணக்கீடுகள் கூட தேவைப்படுகின்றன, அதாவது, ஒரு மூல உச்சியிலிருந்து வரைபடத்தில் உள்ள மற்ற அனைத்து உச்சிகளுக்கும் உள்ள தூரங்களைக் கண்டறிதல். டிஜ்க்ஸ்டிராவின் வழிமுறை ஒவ்வொரு விளிம்பையும் சரியாக ஒரு முறை பார்வையிடுவதால், அது நேரியல் நேரத்தில் இயங்குகிறது, இது கோட்பாட்டளவில் உகந்ததாகும். இருப்பினும், டிஜ்க்ஸ்டிராவின் வழிமுறை இணையாக இருப்பது கடினம் மற்றும் அதன் மோசமான இருப்பிடம் காரணமாக கேச்-உகந்ததாக இல்லை. அதிக கேச்-உகந்த செயல்பாட்டிற்கு சிஎச்எஸ் பயன்படுத்தப்படலாம். இதற்காக, குறுக்குவழி செறிவூட்டப்பட்ட வரைபடத்தில் உள்ள அனைத்து முனைகளிலும் முன்னோக்கி மேல்நோக்கி தேடல் மற்றும் கீழ்நோக்கி ஸ்கேன் செய்யப்படுகிறது. பிந்தைய செயல்பாடு நினைவகத்தின் மூலம் ஒரு நேரியல் பாணியில் ஸ்கேன் செய்கிறது, ஏனெனில் முனைகள் முக்கியத்துவம் குறைந்து வரும் வரிசையில் செயலாக்கப்படுகின்றன, எனவே அதற்கேற்ப நினைவகத்தில் வைக்கப்படலாம். இரண்டாவது கட்டத்தில் முனைகள் செயலாக்கப்படும் வரிசை மூல முனையிலிருந்து சுயாதீனமாக இருப்பதால் இது சாத்தியமாகும் என்பதை நினைவில் கொள்க. உற்பத்தியில், கார்-வழிசெலுத்தல் அமைப்புகள் முன்னறிவிக்கப்பட்ட போக்குவரத்துத் தகவல்களைப் பயன்படுத்தி வேகமான பயண வழிகளைக் கணக்கிடவும், மாற்று வழிகளைக் காட்டவும் முடியும். இரண்டையும் சிஎச்எஸ் பயன்படுத்தி செய்யலாம். முந்தையது நேரத்தை சார்ந்த நெட்வொர்க்குகளுடன் ரூட்டிங் என்று அழைக்கப்படுகிறது, அங்கு கொடுக்கப்பட்ட விளிம்பின் பயண நேரம் இனி நிலையானது அல்ல, மாறாக விளிம்பிற்குள் நுழையும் போது நாளின் நேரத்தின் செயல்பாடு. மாற்று வழித்தடங்கள் மென்மையாக இருக்க வேண்டும், குறுகிய பாதையிலிருந்து கணிசமாக வேறுபட்டிருக்க வேண்டும், ஆனால் கணிசமாக நீண்டதாக இருக்கக்கூடாது. சிஎச்எஸ் ஒரே நேரத்தில் பல அளவீடுகளை மேம்படுத்த நீட்டிக்கப்படலாம்; இது பல அளவுகோல்கள் பாதை திட்டமிடல் என்று அழைக்கப்படுகிறது. எடுத்துக்காட்டாக, பயணச் செலவு மற்றும் நேரம் ஆகிய இரண்டையும் ஒருவர் குறைக்க முடியும். மற்றொரு உதாரணம் மின்சார வாகனங்கள் ஆகும், இதற்கு கிடைக்கக்கூடிய பேட்டரி சார்ஜ் சரியான பாதைகளை கட்டுப்படுத்துகிறது, ஏனெனில் பேட்டரி காலியாக இயங்காது. கோட்பாடு சுருக்க படிநிலைகளின் முன் செயலாக்கம் மற்றும் வினவல் செயல்திறன் குறித்து பல வரம்புகள் நிறுவப்பட்டுள்ளன. பின்வருவனவற்றில் வரைபடத்தில் உள்ள செங்குத்துகளின் எண்ணிக்கை, விளிம்புகளின் எண்ணிக்கை, நெடுஞ்சாலை பரிமாணம், வரைபட விட்டம் ஆகியவை மரத்தின் ஆழம் மற்றும் மரத்தின் அகலம் ஆகும். சுருக்க படிநிலை செயல்திறனின் முதல் பகுப்பாய்வு நெடுஞ்சாலை பரிமாணம் என்று அழைக்கப்படும் அளவைப் பொறுத்தது. இந்த அளவின் வரையறை தொழில்நுட்பமானது என்றாலும், உள்ளுணர்வாக ஒரு வரைபடம் ஒரு சிறிய நெடுஞ்சாலை பரிமாணத்தைக் கொண்டுள்ளது, ஒவ்வொன்றிற்கும் ஒரு சிறிய செங்குத்தான தொகுப்பு இருந்தால், ஒவ்வொரு குறுகிய பாதையும் நீளத்தின் ஒவ்வொரு குறுகிய பாதையும் ஒரு உச்சியை உள்ளடக்கியது. நெடுஞ்சாலை பரிமாணத்தின் சரியான மதிப்பைக் கணக்கிடுவது NP-கடின மற்றும் W [1]-கடினமாகும், ஆனால் கட்டங்களைப் பொறுத்தவரை நெடுஞ்சாலை பரிமாணம் என்று அறியப்படுகிறது. தனிப்பயனாக்கக்கூடிய சுருக்கம் படிநிலை வேலையில் ஒரு மாற்று பகுப்பாய்வு வழங்கப்பட்டது. வினவல் இயங்கும் நேரங்களை வரையறுக்கலாம். மரத்தின் ஆழத்தை மரத்தின் அகலத்தின் அடிப்படையில் வரையறுக்க முடியும் என்பதால், இது ஒரு செல்லுபடியாகும் மேல் வரம்பாகும். முக்கிய ஆதாரம் என்னவென்றால், மோசமான வழக்கு இயங்கும் நேரங்களுக்கான விளைவுகள் சிறப்பாக விவரிக்கப்பட்டுள்ளன. முன் செயலாக்கம் செயல்திறன் கேள்வி செயல்திறன் குறிப்புகள் வெளிப்புற இணைப்புகள் திறந்த மூல அமலாக்கங்கள் https://www.graphhopper.com https://github.com/ifsttar/Tempus https://github.com/RoutingKit/RoutingKit http://project-osrm.org http://www.opentripplanner.org வரைபட வழிமுறைகள் தேடல் வழிமுறைகள் ரூட்டிங் வழிமுறைகள்