Quadratic assignment problem
குவாட்ராடிக் அசைன்மென்ட் சிக்கல் (கியூஏபி) என்பது கூப்மேன்ஸ் மற்றும் பெக்மேன் ஆகியோரால் முதன்முதலில் அறிமுகப்படுத்தப்பட்ட வசதிகளின் இருப்பிட சிக்கல்களின் வகையிலிருந்து, கணிதத்தில் உகப்பாக்கம் அல்லது செயல்பாட்டு ஆராய்ச்சியின் கிளையில் அடிப்படை ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்களில் ஒன்றாகும். சிக்கல் பின்வரும் நிஜ வாழ்க்கை சிக்கலை மாதிரியாகக் காட்டுகிறதுஃ n வசதிகளின் தொகுப்பு மற்றும் n இருப்பிடங்களின் தொகுப்பு உள்ளன. ஒவ்வொரு ஜோடி இடங்களுக்கும், ஒரு தூரம் குறிப்பிடப்படுகிறது மற்றும் ஒவ்வொரு ஜோடி வசதிகளுக்கும் ஒரு எடை அல்லது ஓட்டம் குறிப்பிடப்படுகிறது (எ. கா., இரண்டு வசதிகளுக்கு இடையில் கொண்டு செல்லப்படும் பொருட்களின் அளவு). தொடர்புடைய ஓட்டங்களால் பெருக்கப்படும் தூரங்களின் கூட்டுத்தொகையைக் குறைக்கும் குறிக்கோளுடன் வெவ்வேறு இடங்களுக்கு அனைத்து வசதிகளையும் ஒதுக்குவதே பிரச்சனை. உள்ளுணர்வாக, செலவு செயல்பாடு ஒருவருக்கொருவர் அதிக ஓட்டங்களைக் கொண்ட வசதிகளை நெருக்கமாக வைக்க ஊக்குவிக்கிறது. சிக்கல் அறிக்கை அசைன்மென்ட் சிக்கலை ஒத்திருக்கிறது, தவிர செலவு செயல்பாடு இருபடி ஏற்றத்தாழ்வுகளின் அடிப்படையில் வெளிப்படுத்தப்படுகிறது, எனவே பெயர். முறையான கணித வரையறை இருபடி அசைன்மென்ட் சிக்கலின் முறையான வரையறை பின்வருமாறுஃ கொடுக்கப்பட்ட இரண்டு தொகுப்புகள், P ("வசதிகள்") மற்றும் L ("இடங்கள்"), சம அளவு, ஒன்றாக ஒரு எடை செயல்பாடு w: P × P → R மற்றும் ஒரு தூர செயல்பாடு d: L × L → R. வழக்கமாக எடை மற்றும் தூர செயல்பாடுகள் சதுர உண்மையான மதிப்புள்ள மேட்ரிக்ஸ்களாக பார்க்கப்படுகின்றன, இதனால் செலவு செயல்பாடு பின்வருமாறு எழுதப்படுகிறதுஃ மேட்ரிக்ஸ் குறியீட்டில்ஃ வரிசைமாற்ற மேட்ரிக்ஸின் தொகுப்பு எங்கே, எடை மேட்ரிக்ஸ் மற்றும் தூர மேட்ரிக்ஸ் ஆகும். கணக்கீட்டு சிக்கலானது சிக்கல் NP-கடினமானது, எனவே இந்த சிக்கலை பல்லுறுப்புக்கோவை நேரத்தில் தீர்ப்பதற்கான அறியப்பட்ட வழிமுறை எதுவும் இல்லை, மேலும் சிறிய நிகழ்வுகளுக்கு கூட நீண்ட கணக்கீட்டு நேரம் தேவைப்படலாம். P = NP தவிர, எந்தவொரு (மாறிலி) காரணிக்கும் பல்லுறுப்புக்கோவை நேரத்தில் இயங்கும் தோராயமான வழிமுறை சிக்கலுக்கு இல்லை என்பதும் நிரூபிக்கப்பட்டது. ஓட்டங்கள் அனைத்து வசதிகளையும் ஒரே வளையத்தில் மட்டுமே இணைக்கின்றன, அனைத்து ஓட்டங்களும் ஒரே பூஜ்ஜியமற்ற (நிலையான) மதிப்பைக் கொண்டுள்ளன மற்றும் அனைத்து தூரங்களும் அந்தந்த தூரங்களுக்கு சமமாக உள்ளன என்று ஒருவர் கருதினால் பயண விற்பனையாளர் சிக்கல் (டிஎஸ்பி) கியூஏபி-இன் ஒரு சிறப்பு நிகழ்வாக பார்க்கப்படலாம். நிலையான ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்களின் பல சிக்கல்கள் இந்த வடிவத்தில் எழுதப்படலாம். பயன்பாடுகள் அசல் ஆலை இருப்பிட சூத்திரத்திற்கு கூடுதலாக, கியூஏபி என்பது ஒன்றோடொன்று இணைக்கப்பட்ட மின்னணு கூறுகளை அச்சிடப்பட்ட சர்க்யூட் போர்டில் அல்லது மைக்ரோசிப்பில் வைப்பதற்கான ஒரு கணித மாதிரியாகும், இது மின்னணுவியல் துறையில் கணினி உதவி வடிவமைப்பின் இடம் மற்றும் பாதை கட்டத்தின் ஒரு பகுதியாகும். மேலும் காண்கஃ நாற்கர இடையூறு ஒதுக்கீட்டு சிக்கல் குறிப்புகள் ஆதாரங்கள் A2.5: ND43, pg.218. வெளிப்புற இணைப்புகள் https://www.opt.math.tugraz.at/qaplib QAPLIB-ஒரு நாற்கர ஒதுக்கீடு சிக்கல் நூலகம் http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal MAOS-QAP-ஜாவா அடிப்படையிலான நாற்கர ஒதுக்கீடு சிக்கல் தீர்வு https://CRAN.R-project.org/package=qap-R தொகுப்பு qAP: நாற்கர ஒதுக்கீடு சிக்கலுக்கான ஆய்வுகள் https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ-விண்டோஸிற்கான மெட்டாஹியூரிஸ்டிக் QAP தீர்வு 10/11 NP-கடினமான சிக்கல்கள் ஒருங்கிணைந்த உகப்பாக்கம்