Reverse-search algorithm
தலைகீழ்-தேடல் வழிமுறைகள் என்பது குறிப்பிட்ட அளவிலான ஒருங்கிணைந்த பொருட்களின் சில வகுப்புகளிலிருந்து கொடுக்கப்பட்ட அளவிலான அனைத்து பொருட்களையும் உருவாக்குவதற்கான வழிமுறைகளின் ஒரு வகுப்பாகும். பல சந்தர்ப்பங்களில், இந்த முறைகள் ஒரு பொருளுக்கு பல்லுறுப்புக்கோவை நேரத்தில் பொருட்களை உருவாக்க அனுமதிக்கின்றன, நிலையான எண்ணிக்கையிலான பொருள்களை (பல்லுறுப்புக்கோவை இடம்) சேமிக்க போதுமான நினைவகத்தை மட்டுமே பயன்படுத்துகின்றன. (இருப்பினும், பொதுவாக, அவை பல்லுறுப்புக்கோவை-நேர வழிமுறைகளாக வகைப்படுத்தப்படவில்லை, ஏனெனில் அவை உருவாக்கும் பொருட்களின் எண்ணிக்கை அதிவேகமானது.) அவர்கள் தங்கள் மாநில இடத்தில் ஒரு பரவலான மரத்தில் உருவாக்கப்பட வேண்டிய பொருட்களை ஒழுங்கமைப்பதன் மூலம் வேலை செய்கிறார்கள், பின்னர் இந்த மரத்தின் ஆழமான முதல் தேடலைச் செய்கிறார்கள். தலைகீழ்-தேடல் வழிமுறைகள் 1991 ஆம் ஆண்டில் டேவிட் அவிஸ் மற்றும் கோமே ஃபுகுடா ஆகியோரால் அறிமுகப்படுத்தப்பட்டன, குவிந்த பாலிட்டோப்புகளின் செங்குத்துகள் மற்றும் ஹைப்பர்பிளேன்களின் ஏற்பாடுகளின் செல்களை உருவாக்குவதில் உள்ள சிக்கல்களுக்காக. அவை 1996 ஆம் ஆண்டில் அவிஸ் மற்றும் ஃபுகுடா ஆகியோரால் மிகவும் பரவலாக முறைப்படுத்தப்பட்டன. கோட்பாடுகள் ஒரு தலைகீழ் தேடல் வழிமுறை ஒரு நிலை இடத்தில் ஒருங்கிணைந்த பொருட்களை உருவாக்குகிறது, அதன் செங்குத்துகள் பட்டியலிடப்பட வேண்டிய பொருள்கள் மற்றும் அதன் விளிம்புகள் சில "உள்ளூர் நகர்வுகளை" இணைக்கும் ஜோடி பொருட்களைக் குறிக்கின்றன, பொதுவாக அவற்றின் கட்டமைப்பில் சிறிய மாற்றங்களைச் செய்வதன் மூலம். பின்வரும் தகவல்களால் விவரிக்கப்படும் இந்த நிலை இடத்தின் வேரூன்றிய பரவலான மரத்தில் ஆழமான முதல் தேடலைப் பயன்படுத்தி ஒவ்வொரு பொருளையும் இது கண்டறிகிறதுஃ பரவலான மரத்தின் வேர், பொருட்களில் ஒன்று மரத்தில் உள்ள ஒவ்வொரு பொருளின் பெற்றோரையும் உருவாக்குவதற்கான ஒரு சப்ரூட்டின், போதுமான முறை மீண்டும் மீண்டும் செய்தால் அது இறுதியில் ரூட்டை அடையும் என்ற சொத்துடன் மாநில இடத்தில் உள்ள அனைத்து அண்டை நாடுகளையும் பட்டியலிடுவதற்கான ஒரு சப்ரூட்டின் (இவை அனைத்தும் மரத்தில் அண்டை நாடுகளாக இருக்காது) இந்த தகவலிலிருந்து மரத்தில் கொடுக்கப்பட்ட எந்த முனையின் குழந்தைகளையும் கண்டுபிடிக்க முடியும், பெற்றோர் சப்ரூட்டின் வழங்கிய இணைப்புகளை மாற்றியமைக்கிறதுஃ அவர்கள் வெறுமனே கொடுக்கப்பட்ட முனையாக இருக்கும் அண்டை நாடுகளே. குழந்தை முனைகளுக்கான இந்த தலைகீழ் இணைப்புகள்தான் வழிமுறை தேடுகிறது. இந்த பரவியிருக்கும் மரத்தின் கிளாசிக்கல் ஆழம்-முதல் தேடல் மரத்தை மீண்டும் மீண்டும் கடந்து செல்லும், வேரிலிருந்து தொடங்கி, ஒவ்வொரு முனையிலும் அனைத்து குழந்தைகளையும் பட்டியலிட்டு, ஒவ்வொன்றிற்கும் ஒரு தொடர்ச்சியான அழைப்பு செய்யும். சுழற்சிகளைக் கொண்ட ஒரு வரைபடத்தின் ஆழமான-முதல் தேடலைப் போலல்லாமல், மீண்டும் மீண்டும் வருகைகளைத் தவிர்க்க ஏற்கனவே பார்வையிடப்பட்ட முனைகளின் தொகுப்பை பராமரிக்க வேண்டிய அவசியமில்லை; அத்தகைய மறு செய்கை ஒரு மரத்தில் சாத்தியமில்லை. இருப்பினும், மரம் மிகவும் ஆழமாக இருக்கும் சந்தர்ப்பங்களில், இந்த தொடர்ச்சியான வழிமுறைக்கு அதன் அழைப்பு அடுக்குக்கு இன்னும் அதிக அளவு நினைவகம் தேவைப்படலாம். அதற்கு பதிலாக, தலைகீழ் தேடல் ஒரே வரிசையில் பரவியிருக்கும் மரத்தை கடந்து செல்கிறது, அதே நேரத்தில் இரண்டு பொருட்களை மட்டுமே சேமித்து வைக்கிறதுஃ பயணத்தின் தற்போதைய பொருள் மற்றும் முன்பு பயணித்த பொருள். ஆரம்பத்தில், தற்போதைய பொருள் மரத்தின் வேரில் அமைக்கப்பட்டுள்ளது, மேலும் முந்தைய பொருள் எதுவும் இல்லை. இந்தத் தகவல்களிலிருந்து, பின்வரும் வழக்கு பகுப்பாய்வு மூலம் பயணத்தின் அடுத்த கட்டத்தைத் தீர்மானிக்க முடியும்ஃ முந்தைய பொருள் எதுவும் இல்லையென்றால், அல்லது முந்தைய பொருள் தற்போதைய பொருளின் பெற்றோராக இருந்தால், பயணமானது தற்போதைய பொருளை அடைவது இதுவே முதல் முறை, எனவே இது தேடலின் வெளியீடாகும். அடுத்த பொருள் அதன் முதல் குழந்தை அல்லது, குழந்தைகள் இல்லையென்றால், அதன் பெற்றோர். மற்ற எல்லா நிகழ்வுகளிலும், முந்தைய பொருள் தற்போதைய பொருளின் குழந்தையாக இருக்க வேண்டும். இந்த வழிமுறை இந்த முந்தைய குழந்தையை அடையும் வரை குழந்தைகளை (அதாவது, தற்போதைய பொருளை தங்கள் பெற்றோராகக் கொண்ட தற்போதைய பொருளின் மாநில-விண்வெளி அண்டை நாடுகள்) ஒரு நேரத்தில் பட்டியலிடுகிறது, பின்னர் இந்த குழந்தைகளின் பட்டியலில் மேலும் ஒரு படி எடுக்கிறது. இந்த வழியில் மற்றொரு குழந்தை காணப்பட்டால், அது அடுத்த பொருளாகும். அடுத்த சைல்ட் இல்லை மற்றும் தற்போதைய பொருள் வேர் இல்லையென்றால், அடுத்த பொருள் தற்போதைய பொருளின் பெற்றோர். மீதமுள்ள வழக்கில், அடுத்த குழந்தை இல்லாதபோது மற்றும் தற்போதைய பொருள் மூலமாக இருக்கும்போது, தலைகீழ் தேடல் முடிவடைகிறது. இந்த வழிமுறை தேடலின் ஒவ்வொரு கட்டத்திற்கும் ஒரு பொருளின் அண்டை நாடுகளை ஒரு முறை பட்டியலிடுவதை உள்ளடக்கியது. இருப்பினும், பட்டியலிடப்பட வேண்டிய பொருள்கள் இருந்தால், தேடல் படிகளைச் செய்கிறது, எனவே அது பொருட்களின் அண்டை நாடுகளை உருவாக்கும் நேரங்களின் எண்ணிக்கை தொடர்ச்சியான ஆழம்-முதல் தேடல் அதே காரியத்தைச் செய்யும் எண்ணிக்கையில் இரண்டு மடங்கிற்குள் உள்ளது. பயன்பாடுகள் தலைகீழ் தேடல் பயன்படுத்தப்பட்ட சிக்கல்களின் எடுத்துக்காட்டுகளில் பின்வரும் ஒருங்கிணைந்த தலைமுறை சிக்கல்கள் அடங்கும்ஃ எளிய குவிந்த பாலிடோப்புகளின் செங்குத்துகள் ஒரு பரிமாண குவிந்த பாலிடோப் அரை இடைவெளிகளின் குறுக்குவெட்டு என்று வரையறுக்கப்பட்டால், அதன் செங்குத்துகளை அரை இடைவெளிகளின் குறுக்குவெட்டு புள்ளிகள் அல்லது அதிக ஹைப்பர்பிளேன்கள் என்று விவரிக்கலாம்; எந்த உச்சியும் இந்த ஹைப்பர்பிளேன்களின் குறுக்குவெட்டு இல்லையென்றால் அது ஒரு எளிய பாலிடோப் ஆகும். இந்த செங்குத்துகள் அனைத்தையும் பட்டியலிடுவதில் உள்ள சிக்கலே உச்சி கணக்கீட்டு சிக்கலாகும். பாலிடோப்பின் விளிம்புகள் பொதுவான ஹைப்பர்பிளேன்களைக் கொண்ட செங்குத்துகளின் ஜோடிகளை இணைக்கின்றன, எனவே செங்குத்துகள் மற்றும் விளிம்புகள் ஒவ்வொரு உச்சிக்கும் அண்டை நாடுகளைக் கொண்ட ஒரு நிலை இடத்தை உருவாக்குகின்றன. நேரியல் நிரலாக்கக் கோட்பாட்டின் சிம்ப்ளக்ஸ் வழிமுறை, முனையங்களின் கொடுக்கப்பட்ட நேரியல் செயல்பாட்டை அதிகரிப்பதன் மூலம், உச்சியிலிருந்து உச்சிக்கு நடந்து செல்வதன் மூலம், ஒவ்வொரு கட்டத்திலும் செயல்பாட்டின் அதிக மதிப்புடன் ஒரு உச்சியைத் தேர்ந்தெடுப்பதன் மூலம் ஒரு உச்சியைக் கண்டறிகிறது; எந்த உச்சியை தேர்வு செய்ய வேண்டும் என்பதை இன்னும் துல்லியமாகக் குறிப்பிடும் "மைய விதி" யின் பல நிலையான தேர்வுகள் உள்ளன. அத்தகைய எந்த மைய விதி பாலிடோப்பின் ஒரு பரவலான மரத்தின் தாய் செயல்பாட்டை வரையறுப்பதாக விளக்கப்படலாம், அதன் வேர் உகந்த உச்சியாகும். இந்தத் தரவுகளுக்கு தலைகீழ் தேடலைப் பயன்படுத்துவது பாலிடோப்பின் அனைத்து செங்குத்துகளையும் உருவாக்குகிறது. இதே போன்ற ஒரு வழிமுறை ஒரு நேரியல் நிரலின் அனைத்து தளங்களையும் கணக்கிட முடியும், இது ஒரு எளிய பாலிடோப்பை வரையறுக்க வேண்டிய அவசியமில்லை. ஹைப்பர்பிளேன் அமைப்புகளின் செல்கள் ஒரு ஹைப்பர்பிளேன் ஏற்பாடு யூக்ளிடியன் இடத்தை செல்களாக சிதைக்கிறது, ஒவ்வொன்றும் ஒரு "சைன் வெக்டர்" மூலம் விவரிக்கப்படுகிறது, இது அதன் புள்ளிகள் ஹைப்பர்பிளேன்களில் ஒன்றைச் சேர்ந்ததா (அடையாளம் 0), ஹைப்பர்பிளேனின் ஒரு பக்கத்தில் (அடையாளம் + 1) உள்ளதா அல்லது மறுபுறம் (அடையாளம்-1) உள்ளதா என்பதை விவரிக்கிறது. செல்கள் உள்ளூர் நகர்வுகளின் கீழ் ஒரு இணைக்கப்பட்ட நிலை இடத்தை உருவாக்குகின்றன, அவை ஒரு அடையாளத்தை ஒரு அலகு மூலம் மாற்றுகின்றன, மேலும் இந்த செயல்பாடு ஒரு நேரியல் நிரலாக்க சாத்தியக்கூறு சிக்கலைத் தீர்ப்பதன் மூலம் ஒரு செல்லுபடியாகும் கலத்தை உருவாக்குகிறது என்பதைச் சரிபார்க்க முடியும். அடையாளம் திசையனை வேருக்கு நெருக்கமாகக் கொண்டுவருவதற்கான முதல் சாத்தியமான மாற்றத்தை ஏற்படுத்தும் ஒரு பெற்றோர் ஆபரேட்டரை வரையறுப்பதன் மூலம் ரூட் செல்லின் எந்தவொரு தேர்வுக்கும் ஒரு பரவலான மரத்தை உருவாக்க முடியும். இந்த நிலை இடத்திற்கான தலைகீழ் தேடலைப் பயன்படுத்துதல் மற்றும் பெற்றோர் ஆபரேட்டர் ஒரு செல்லுக்கு பல்லுறுப்புக்கோவை நேரத்தில் அனைத்து செல்களையும் பட்டியலிடுவதற்கான ஒரு வழிமுறையை உருவாக்குகிறது. புள்ளி-தொகுப்பு முக்கோணங்கள் ஒரு பிளானர் புள்ளி தொகுப்பின் முக்கோணங்கள் "ஃபிளிப்" நகர்வுகளால் இணைக்கப்பட்டுள்ளன, அவை ஒரு முக்கோணத்திலிருந்து ஒரு மூலைவிட்டத்தை அகற்றி மற்றொரு மூலைவிட்டத்தால் மாற்றுகின்றன. டெலவுனே முக்கோணம் மூலமாகத் தேர்ந்தெடுக்கப்பட்டால், ஒவ்வொரு முக்கோணத்தையும் டெலவுனே முக்கோணத்திற்கு நான்கு புள்ளிகளின் சில துணைக்குழுவின் முக்கோணம் அதன் டெலவுனே முக்கோணத்தால் மாற்றப்படும் படிகளால் புரட்டலாம். ஒவ்வொரு முக்கோணத்தின் பெற்றோராக முதல் டெலானே ஃபிளிப் தேர்வு செய்து, உள்ளூர் தேடலைப் பயன்படுத்துவதன் மூலம், ஒரு முக்கோணத்திற்கு பல்லுறுப்புக்கோவை நேரத்தில் அனைத்து முக்கோணங்களையும் பட்டியலிடுவதற்கான ஒரு வழிமுறையை உருவாக்குகிறது. இணைக்கப்பட்ட துணை வரைபடங்கள் கொடுக்கப்பட்ட இணைக்கப்பட்ட வரைபடத்தின் இணைக்கப்பட்ட துணை வரைபடங்கள் மற்றும் இணைக்கப்பட்ட தூண்டப்பட்ட துணை வரைபடங்கள் ஒரு மாநில இடத்தை உருவாக்குகின்றன, அதன் உள்ளூர் நகர்வுகள் முறையே வரைபடத்தின் ஒரு விளிம்பு அல்லது உச்சியை சேர்ப்பது அல்லது அகற்றுவதாகும். இந்த நிலை இடத்தின் ஒரு பரவலான மரத்தை முதல் விளிம்பு அல்லது உச்சியை (விளிம்புகள் அல்லது செங்குத்துகளின் சில வரிசையில்) சேர்ப்பதன் மூலம் பெறலாம், அதன் கூட்டல் மற்றொரு இணைக்கப்பட்ட துணை வரைபடத்தை உருவாக்குகிறது; அதன் வேர் முழு வரைபடமாகும். இந்த நிலை இடத்திற்கும் தாய் இயக்குபவருக்கும் உள்ளூர் தேடலைப் பயன்படுத்துவது ஒரு துணை வரைபடத்திற்கு பல்லுறுப்புக்கோவை நேரத்தில் இணைக்கப்பட்ட அனைத்து துணை வரைபடங்களையும் பட்டியலிடுவதற்கான ஒரு வழிமுறையை உருவாக்குகிறது. பிற பயன்பாடுகளில் பின்வரும் கட்டமைப்புகளை உருவாக்குவதற்கான வழிமுறைகள் அடங்கும்ஃ பாலியோமினோஸ், பாலியாமண்ட் புரோட்டோடைல்கள் மற்றும் பாலிஹெக்ஸ் (கணிதம்) ஹைட்ரோகார்பன் மூலக்கூறுகள். இயக்கப்படும் அசைக்லிக் வரைபடங்களின் இடவியல் வரிசைமுறைகள், ஒரு நிலை இடத்தைப் பயன்படுத்தி, அதன் உள்ளூர் நகர்வுகள் இரண்டு கூறுகளின் வரிசையை மாற்றியமைக்கின்றன. வரைபடங்களின் பரவலான மரங்கள், பிளானர் பாயிண்ட் செட்டுகளின் பரவலான மரங்கள் மற்றும் பொதுவாக மேட்ராய்டுகளின் தளங்கள், ஒரு விளிம்பை மற்றொரு விளிம்பிற்கு மாற்றும் ஒரு மாநில இடத்தைப் பயன்படுத்துகின்றன. வரைபடங்களில் ஆய்லர் சுற்றுப்பயணங்கள். அரிதான வரைபடங்களின் அதிகபட்ச சுயாதீன தொகுப்புகள். அதிகபட்ச பிளானர் வரைபடங்கள் மற்றும் பாலிஹெட்ரல் வரைபடங்கள். கொடுக்கப்பட்ட புள்ளி தொகுப்பில் குறுக்காத குறைந்தபட்ச கடினமான வரைபடங்கள். சுற்றியுள்ள பலகோணங்கள், கொடுக்கப்பட்ட சில புள்ளிகளை செங்குத்துகளாகக் கொண்ட பலகோணங்கள் மற்றும் மீதமுள்ளவற்றைச் சுற்றி, பலகோணத்தின் ஒரு உச்சியை சேர்க்கும் அல்லது அகற்றும் நிலை இடத்தைப் பயன்படுத்துகின்றன. மின்காவ்ஸ்கியின் செங்குத்துகள் அல்லது அம்சங்கள் குவிந்த பாலிட்டோப்புகளின் கூட்டுத்தொகை. மோனோமியல் ஐடியல்களின் மூலைகள் (மல்டி டிகிரி). குறிப்புகள் தேடல் வழிமுறைகள் ஒருங்கிணைந்த வழிமுறைகள்