Stacker crane problem
ஒருங்கிணைந்த உகப்பாக்கத்தில், ஸ்டேக்கர் கிரேன் சிக்கல் என்பது பயண விற்பனையாளர் சிக்கலுடன் நெருக்கமாக தொடர்புடைய ஒரு உகப்பாக்கம் சிக்கலாகும். அதன் உள்ளீடு ஒரு மெட்ரிக் இடத்தில் வரிசைப்படுத்தப்பட்ட ஜோடி புள்ளிகளின் தொகுப்பைக் கொண்டுள்ளது, மேலும் இந்த புள்ளிகளை குறைந்தபட்ச மொத்த நீளத்தின் சுழற்சியில் இணைப்பதே குறிக்கோள், இதில் அனைத்து ஜோடிகளும் ஒருவருக்கொருவர் தொடர்ந்து நோக்கமாக உள்ளன. ஒரு ஸ்டேக்கர் கிரேன், கட்டுமான கிரேன் அல்லது (டிரேஜில்) ஒரு டிரக் மூலம் தனிப்பட்ட சரக்குகளை எடுத்துச் செல்வதற்கும் வழங்குவதற்கும் திட்டமிடுவதில் உள்ள சிக்கல்களை இது மாதிரியாகக் கொண்டுள்ளது, இந்த விநியோகங்களின் நேரத்திற்கு தடைகள் இல்லாமல் எளிமைப்படுத்தப்பட்ட வடிவத்தில். இது கலப்பு வரைபடங்களின் அடிப்படையில் சமமான சூத்திரத்துடன் அறிமுகப்படுத்தப்பட்டது, இயக்கப்படும் விளிம்புகள் உள்ளீட்டு ஜோடிகள் மற்றும் திசைதிருப்பப்படாத விளிம்புகள் அவற்றின் தூரங்களை மாதிரியாக்குகின்றன. ஃபிரடெரிக்சன் மற்றும் பலர். டேனியல் ஜே. ரோசென்கிராண்ட்சின் தனிப்பட்ட தகவல்தொடர்புக்கு அதன் சூத்திரத்தை பாராட்டுங்கள். ஸ்டேக்கர் கிரேன் சிக்கலை மெட்ரிக் இடங்களில் பயண விற்பனையாளர் சிக்கலின் பொதுமைப்படுத்தலாகக் காணலாம்ஃ பயண விற்பனையாளர் சிக்கலின் எந்தவொரு நிகழ்வையும் ஸ்டேக்கர் கிரேன் சிக்கலின் ஒரு நிகழ்வாக மாற்றலாம், பயண விற்பனையாளர் நிகழ்வில் ஒவ்வொரு புள்ளிக்கும் ஒரு ஜோடி இருக்கும். மறுபுறம், ஸ்டேக்கர் கிரேன் சிக்கலை சமச்சீரற்ற பயண விற்பனையாளர் சிக்கலின் ஒரு சிறப்பு நிகழ்வாகக் காணலாம், அங்கு சமச்சீரற்ற பயண விற்பனையாளர் சிக்கலின் புள்ளிகள் ஒரு ஸ்டேக்கர் கிரேன் நிகழ்வின் ஜோடிகள் மற்றும் ஒரு ஜோடியின் தூரம் மற்றொரு ஜோடிக்கு முதல் ஜோடியின் டெலிவரி புள்ளியிலிருந்து, அதன் பிக்அப் பாயிண்ட் வழியாக, இரண்டாவது ஜோடியின் டெலிவரி பாயிண்டிற்கு செல்லும் தூரமாக எடுத்துக் கொள்ளப்படுகிறது. இது பயண விற்பனையாளர் சிக்கலை பொதுமைப்படுத்துவதால், அது அதே கணக்கீட்டு சிக்கலைப் பெறுகிறதுஃ இது NP-கடினமானது, குறைந்தபட்சம் தோராயமாக மதிப்பிடுவது கடினம். பயண விற்பனையாளர் சிக்கலுக்கான கிறிஸ்டோஃபைட்ஸ் வழிமுறையை அடிப்படையாகக் கொண்ட ஒரு தோராயமான வழிமுறை ஸ்டேக்கர் கிரேன் சிக்கலின் தீர்வை 9/5 என்ற தோராய விகிதத்திற்குள் தோராயமாக மதிப்பிட முடியும். பயன்படுத்தப்படும் நூலின் மொத்த அளவைக் குறைக்க ஒரு எம்பிராய்டரி வடிவத்தின் பின்புறத்தை வடிவமைப்பதில் உள்ள சிக்கல் ஸ்டேக்கர் கிரேன் சிக்கலுடன் நெருக்கமாக தொடர்புடையது, ஆனால் இது அதன் ஒவ்வொரு ஜோடி புள்ளிகளையும் (வடிவத்தின் முன் பக்கத்தில் புலப்படும் தையல்களின் முனைகள்) அனுமதிக்கிறது. பயண விற்பனையாளர் சிக்கலில் இருந்து அதே மாற்றத்தால் இது NP-கடினமானது, மேலும் 2 என்ற தோராய விகிதத்திற்குள் தோராயமாக மதிப்பிடப்படலாம். ஸ்டேக்கர் கிரேன் சிக்கலின் மற்றொரு மாறுபாடு, டயல்-ஏ-ரைட் சிக்கல் என்று அழைக்கப்படுகிறது, ஒரு வாகனம் அதன் பாதையில் எந்த நேரத்திலும் சில சுமைகளை வைத்திருக்க அனுமதிக்கும் அதே நேரத்தில் பிக்அப்கள் மற்றும் டெலிவரிகளின் தொகுப்பைச் செய்ய குறைந்தபட்ச பாதையைக் கேட்கிறது. குறிப்புகள் பயண விற்பனையாளர் சிக்கல்