Mixed Chinese postman problem
கலப்பு சீன தபால்காரர் சிக்கல் (எம். சி. பி. பி அல்லது எம். சி. பி) என்பது V உச்சிகளின் தொகுப்புடன் ஒரு வரைபடத்தின் குறுகிய பயணத்தைத் தேடுவது, நேர்மறை பகுத்தறிவு எடைகளுடன் திசைதிருப்பப்படாத விளிம்புகள் E இன் தொகுப்பு மற்றும் நேர்மறை பகுத்தறிவு எடைகளுடன் இயக்கப்படும் வளைவுகளின் தொகுப்பு A ஒவ்வொரு விளிம்பையும் அல்லது வளைவையும் குறைந்தபட்ச செலவில் ஒரு முறையாவது உள்ளடக்கியது. இந்த சிக்கல் NP-முழுமையானது என்று பாப்படிமிட்ரியோவால் நிரூபிக்கப்பட்டுள்ளது. கலப்பு சீன தபால்காரர் சிக்கல் பெரும்பாலும் பனி உழுதல் போன்ற வளைவு ரூட்டிங் சிக்கல்களில் எழுகிறது, அங்கு சில தெருக்கள் இரு திசைகளிலும் பயணிக்க மிகவும் குறுகலானவை, மற்ற தெருக்கள் இருதரப்பு மற்றும் இரு திசைகளிலும் உழப்படலாம். கலப்பு வரைபடம் வலுவாக இணைக்கப்பட்டுள்ளதா என்பதைச் சரிபார்ப்பதன் மூலம் ஒரு கலப்பு வரைபடத்தில் எந்த அளவிலும் தபால்காரர் சுற்றுப்பயணம் உள்ளதா என்பதைச் சரிபார்க்க எளிதானது. சரகோசா மார்டினெஸ் நிரூபித்தபடி, தபால்காரர் சுற்றுப்பயணத்தை ஒவ்வொரு வளைவையும் சரியாக ஒரு முறை கடக்க நாம் கட்டுப்படுத்தியாலோ அல்லது ஒவ்வொரு விளிம்பையும் சரியாக ஒரு முறை கடக்க நாம் கட்டுப்படுத்தியாலோ சிக்கல் NP கடினமாக உள்ளது. கணித வரையறை கணித வரையறைஃ உள்ளீடுஃ ஒவ்வொரு விளிம்பிற்கும் செலவு மற்றும் அதிகபட்ச செலவுடன் வலுவாக இணைக்கப்பட்ட, கலப்பு வரைபடம். கேள்விஃ ஒவ்வொரு விளிம்பையும் ஒவ்வொரு வளைவையும் குறைந்தபட்சம் ஒரு முறையாவது கடந்து செல்லும் ஒரு (இயக்கப்பட்ட) சுற்றுப்பயணம் உள்ளதா மற்றும் அதிகபட்ச செலவைக் கொண்டதா? கலப்பு சீன தபால்காரர் சிக்கலைத் தீர்ப்பதில் உள்ள முக்கிய சிரமம், எங்கள் சுற்றுப்பயணத்திற்கு ஒரு இறுக்கமான பட்ஜெட் வழங்கப்படும் போது (திசைதிருப்பப்படாத) விளிம்புகளுக்கான நோக்குநிலைகளைத் தேர்ந்தெடுப்பதில் உள்ளது, மேலும் ஒவ்வொரு விளிம்பையும் ஒரு முறை மட்டுமே கடக்க முடியும். பின்னர் நாம் விளிம்புகளை நோக்கித் திருப்பி, மேலும் சில வளைவுகளைச் சேர்க்க வேண்டும், இதனால் இயக்கப்பட்ட யூலேரியன் வரைபடத்தைப் பெறலாம், அதாவது ஒவ்வொரு முனையையும் சமநிலைப்படுத்த வேண்டும். ஒரு முனையில் பல விளிம்புகள் இருந்தால், ஒவ்வொரு விளிம்பின் சரியான நோக்குநிலையையும் தீர்மானிப்பது எளிதான பணி அல்ல. கணிதவியலாளர் பாப்பாடிமிட்ரியோ இந்த சிக்கலை மேலும் கட்டுப்பாடுகளுடன் பகுப்பாய்வு செய்தார்; "கலப்பு சீன போஸ்ட்மேன் NP-முழுமையானது, உள்ளீட்டு வரைபடம் சமதளமாக இருந்தாலும், ஒவ்வொரு உச்சிக்கும் அதிகபட்சம் மூன்று டிகிரி உள்ளது, மேலும் ஒவ்வொரு விளிம்பு மற்றும் வளைவுக்கும் ஒரு செலவு உள்ளது". யூலேரியன் வரைபடம் ஒரு கலப்பு வரைபடம் யூலேரியன் என்பதைச் சரிபார்க்கும் செயல்முறை கலப்பு சீன தபால்காரர் சிக்கலைத் தீர்ப்பதற்கான ஒரு வழிமுறையை உருவாக்குவதற்கு முக்கியமானது. ஒரு கலப்பு வரைபடத்தின் டிகிரி ஜி ஒரு யூலேரியன் சுழற்சியைக் கொண்டிருக்க சமமாக இருக்க வேண்டும், ஆனால் இது போதாது. கலப்பு சீன தபால்காரர் NP-கடினமானவர் என்ற உண்மை, நியாயமான வரம்பிற்கு உகந்த தீர்வை அணுகும் பல்லுறுப்புக்கோவை நேர வழிமுறைகளைத் தேடுவதற்கு வழிவகுத்தது. ஃப்ரெடெரிக்சன் பிளானர் வரைபடங்களுக்கு பயன்படுத்தக்கூடிய 3/2 காரணி கொண்ட ஒரு முறையை உருவாக்கினார், மேலும் ராகவச்சாரியும் வீரசாமியும் பிளானராக இருக்க வேண்டிய அவசியமில்லாத ஒரு முறையைக் கண்டுபிடித்தனர். இருப்பினும், பல்லுறுப்புக்கோவை நேரத்தால் தலை துண்டிக்கப்படுவதற்கான செலவைக் கண்டுபிடிக்க முடியாது, ஒரு பனி கலப்பை தெருக்களை அடைய எடுக்கும் நேரம் அது உழுது அல்லது ஒரு தெரு துப்புரவாளரை தெருக்களை அடைய எடுக்கும். முறையான வரையறை ஒரு உச்சி தொகுப்புடன் வலுவாக இணைக்கப்பட்ட கலப்பு வரைபடம் மற்றும் விளிம்பு தொகுப்பு, ஒரு வளைவு தொகுப்பு மற்றும் ஒவ்வொன்றிற்கும் எதிர்மறை அல்லாத செலவு ஆகியவற்றைக் கருத்தில் கொண்டு, எம். சி. பி. பி ஒவ்வொரு இணைப்பிலும் குறைந்தபட்சம் ஒரு முறையாவது கடந்து செல்லும் குறைந்த கட்டண சுற்றுப்பயணத்தைக் கண்டுபிடிப்பதைக் கொண்டுள்ளது. கொடுக்கப்பட்ட,,, சரியாக ஒரு இறுதிப் புள்ளியைக் கொண்ட விளிம்புகளின் தொகுப்பைக் குறிக்கிறது, மற்றும். ஒரு உச்சியில் கொடுக்கப்பட்டால், (இன்டெக்ரி) என்பது நுழையும் வளைவுகளின் எண்ணிக்கையைக் குறிக்கிறது, (அவுட் டிகிரி) என்பது வெளியேறும் வளைவுகளின் எண்ணிக்கை, மற்றும் (டிகிரி) என்பது இணைப்புகளின் எண்ணிக்கை. என்பதைக் கவனத்தில் கொள்ளுங்கள். ஒரு கலப்பு வரைபடம் அதன் அனைத்து செங்குத்துகளும் சம டிகிரியைக் கொண்டிருந்தாலும், அது ஒவ்வொரு உச்சிக்கும் சமச்சீர் என்று அழைக்கப்படுகிறது, மேலும் செங்குத்துகளின் ஏதேனும் துணைக்குழுவைக் கொடுத்தால், வளைவுகளின் எண்ணிக்கைக்கு இடையிலான வேறுபாடு, மற்றும் திசை திருப்பப்பட்ட வளைவுகளின் எண்ணிக்கை, இணைக்கும் திசையற்ற விளிம்புகளின் எண்ணிக்கையை விட அதிகமாக இருக்காது மற்றும்,. சமமாகவும் சமநிலையாகவும் இருந்தால் மட்டுமே கலப்பு வரைபடம் யூலேரியன் என்பது அனைவரும் அறிந்த உண்மை. சம மற்றும் சமச்சீர் என்றால், G சமச்சீர் (மற்றும் யூலேரியன்) என்பதைக் கவனியுங்கள். மேலும், சமமாக இருந்தால், பல்லுறுப்புக்கோவை நேரத்தில் சரியாக தீர்க்கப்படலாம். எம். சி. பி. பி அல்காரிதம் கூட சமமான மற்றும் வலுவாக இணைக்கப்பட்ட கலப்பு வரைபடத்தைக் கொடுத்தால், ஒரே மாதிரியான செலவுகளுடன் விளிம்புகளுக்கு தோராயமாக ஒரு திசையை ஒதுக்குவதன் மூலம் பெறப்பட்ட வளைவுகளின் தொகுப்பாக இருக்கட்டும். இயக்கப்பட்ட வரைபடத்தில் உள்ள ஒவ்வொரு உச்சிக்கும் i ஐக் கணக்கிடுங்கள். ஒரு உச்சி வழங்கல் தேவையுடன் ஒரு ஆதாரமாக (மூழ்கி) கருதப்படும். ஒரு சமமான வரைபடத்தைப் போலவே, அனைத்து வழங்கல்களும் கோரிக்கைகளும் சம எண்கள் என்பதை நினைவில் கொள்க (பூஜ்ஜியம் ஒரு சமமான எண்ணாக கருதப்படுகிறது). அந்த தொடர்புடைய விளிம்புகளின் செலவுகளுடன் எதிர் திசையில் வளைவுகளின் தொகுப்பாக இருக்கட்டும், பூஜ்ஜிய செலவில் இணையாக வளைவுகளின் தொகுப்பாக இருக்கட்டும். அனைத்து செங்குத்துகளின் தேவைகளையும் பூர்த்தி செய்ய, வரைபடத்தில் குறைந்தபட்ச செலவு ஓட்ட சிக்கலைத் தீர்க்கவும், இதில் ஒவ்வொரு வளைவிலும் எல்லையற்ற திறன் உள்ளது மற்றும் ஒவ்வொரு வளைவிலும் திறன் 2 உள்ளது. உகந்த ஓட்டமாக இருக்கட்டும். செய்ய வேண்டிய ஒவ்வொரு வளைவுக்கும்ஃ என்றால், அதனுடன் தொடர்புடைய விளிம்பை இருந்து நோக்கி (படி 1 இல் தொடர்புடைய விளிம்பிற்கு ஒதுக்கப்பட்ட திசை, "தவறானது"); என்றால், G இல் உள்ள தொடர்புடைய விளிம்பை நோக்கி (இந்த விஷயத்தில், படி 1 இல் உள்ள நோக்குநிலை "சரியானது"). இந்த வழக்கு சாத்தியமற்றது என்பதை நினைவில் கொள்க, ஏனெனில் வளைவுகளின் வழியாக அனைத்து ஓட்ட மதிப்புகளும் சம எண்கள். ஒவ்வொரு வளைவின் நகல்களையும் சேர்ப்பதன் மூலம் அதிகரிக்கவும். இதன் விளைவாக வரும் வரைபடம் சமமாகவும் சமச்சீராகவும் உள்ளது. கலப்பு வரைபடம் சமமாக இல்லாதபோது மற்றும் முனைகள் அனைத்தும் சமமாக இல்லாதபோது, வரைபடத்தை சமமான வரைபடமாக மாற்றலாம். வலுவாக இணைக்கப்பட்ட ஒரு கலப்பு வரைபடமாக இருக்கட்டும். வளைவு திசைகளை புறக்கணிப்பதன் மூலம் ஒற்றைப்படை டிகிரி முனைகளைக் கண்டறிந்து குறைந்தபட்ச செலவு பொருத்தத்தைப் பெறுங்கள். சமமான வரைபடத்தை உருவாக்க குறைந்தபட்ச செலவு பொருத்தத்திலிருந்து விளிம்புகளுடன் வரைபடத்தை அதிகரிக்கவும். வரைபடம் சமமானது ஆனால் சமச்சீர் அல்ல மற்றும் ஒரு யூலேரியன் கலப்பு வரைபடம் சம மற்றும் சமச்சீர் ஆகும். சமமாக இல்லாத ஒரு சமச்சீர் வரைபடத்தைப் பெற குறைந்தபட்ச செலவு ஓட்ட சிக்கலைத் தீர்க்கவும். இறுதி கட்டம் சமச்சீர் வரைபடத்தை சமமாக்குவதை உள்ளடக்கியது. ஒற்றைப்படை டிகிரி முனைகளை பெயரிடுங்கள். வளைவு தொகுப்பில் உள்ள கோடுகள் மற்றும் விளிம்பில் உள்ள கோடுகளுக்கு இடையில் மாறி மாறி வரும் சுழற்சிகளைக் கண்டறியவும், அவை புள்ளிகளில் தொடங்கி முடிவடையும். வளைவுகள் திசைதிருப்பப்படாத விளிம்புகளாகக் கருதப்பட வேண்டும், திசைதிருப்பப்பட்ட வளைவுகளாக அல்ல. மரபணு வழிமுறை ஹுவா ஜியாங் மற்றும் பலர் வெளியிட்ட ஒரு ஆய்வுக் கட்டுரை. மக்கள் தொகையில் செயல்படுவதன் மூலம் கலப்பு சீன தபால்காரர் சிக்கலைத் தீர்க்க ஒரு மரபணு வழிமுறையை ஆல் அமைத்தார். எம். சி. பி. பி. க்கான பிற தோராயமான வழிமுறைகளுடன் ஒப்பிடும்போது இந்த வழிமுறை சிறப்பாக செயல்பட்டது. மேலும் காண்க கேபசிட்டட் ஆர்க் ரூட்டிங் சிக்கல் குறிப்புகள் வரைபடக் கோட்பாட்டில் உள்ள கணக்கீட்டு சிக்கல்கள்