Closest string
கோட்பாட்டு கணினி அறிவியலில், மிக நெருக்கமான சரம் ஒரு NP-கடினமான கணக்கீட்டு சிக்கலாகும், இது உள்ளீட்டு சரங்களின் தொகுப்பின் வடிவியல் மையத்தைக் கண்டுபிடிக்க முயற்சிக்கிறது. "மையம்" என்ற வார்த்தையைப் புரிந்துகொள்ள, இரண்டு சரங்களுக்கு இடையிலான தூரத்தை வரையறுக்க வேண்டும். வழக்கமாக, இந்த சிக்கல் ஹாமிங் தூரத்தை மனதில் கொண்டு ஆய்வு செய்யப்படுகிறது. முறையான வரையறை மேலும் முறையாக, n நீளம்-m சரங்கள் s1, s2,., sn கொடுக்கப்பட்டால், மிக நெருக்கமான சரம் சிக்கல் ஒரு புதிய நீளம்-m சரம் s ஐ நாடுகிறது, அதாவது d (s, si) ≤ k அனைத்து i க்கும், அங்கு d என்பது ஹாமிங் தூரத்தைக் குறிக்கிறது, மேலும் k முடிந்தவரை சிறியதாக இருக்கும். NP-முழுமையான நெருக்கமான சரம் சிக்கலின் ஒரு முடிவு சிக்கல் பதிப்பு, அதற்கு பதிலாக k ஐ மற்றொரு உள்ளீடாக எடுத்து, அனைத்து உள்ளீட்டு சரங்களின் ஹேமிங் தூர k க்குள் ஒரு சரம் இருக்கிறதா என்று கேள்வி எழுப்புகிறது. மிக நெருக்கமான சரம் சிக்கலை பொதுவான 1-மைய சிக்கலின் ஒரு சிறப்பு நிகழ்வாகக் காணலாம், இதில் உறுப்புகளுக்கு இடையிலான தூரம் ஹாமிங் தூரத்தைப் பயன்படுத்தி அளவிடப்படுகிறது. உயிர் தகவலியலில், மிக நெருக்கமான சரம் சிக்கல் என்பது டி. என். ஏவில் சமிக்ஞைகளைக் கண்டுபிடிப்பதில் உள்ள சிக்கலின் தீவிரமான ஆய்வு அம்சமாகும். எளிமைப்படுத்தல்கள் மற்றும் தரவு குறைப்புகள் நெருங்கிய சரத்தின் நிகழ்வுகள் சிக்கலுக்கு அவசியமற்ற தகவல்களைக் கொண்டிருக்கலாம். ஏதோ ஒரு வகையில், நெருங்கிய சரத்தின் வழக்கமான உள்ளீடு தகவல்களைக் கொண்டுள்ளது, இது சிக்கலின் கடினத்தன்மைக்கு பங்களிக்காது. எடுத்துக்காட்டாக, சில சரங்களில் a என்ற எழுத்து இருந்தால், ஆனால் எதுவும் z என்ற எழுத்தைக் கொண்டிருக்கவில்லை என்றால், அனைத்தையும் zs உடன் மாற்றுவது அடிப்படையில் சமமான நிகழ்வை வழங்கும், அதாவதுஃ மாற்றியமைக்கப்பட்ட நிகழ்வின் தீர்விலிருந்து, அசல் தீர்வை மீட்டெடுக்க முடியும், மற்றும் நேர்மாறாகவும். உள்ளீட்டை இயல்பாக்குவது ஒரே நீளத்தைப் பகிர்ந்து கொள்ளும் அனைத்து உள்ளீட்டு சரங்களும் ஒன்றின் மேல் ஒன்று எழுதப்படும்போது, அவை ஒரு மேட்ரிக்ஸை உருவாக்குகின்றன. சில வரிசை வகைகள் அடிப்படையில் தீர்வுக்கு ஒரே மாதிரியான தாக்கங்களைக் கொண்டுள்ளன. எடுத்துக்காட்டாக, ஒரு நெடுவரிசையை உள்ளீடுகளுடன் (a, a, b) மற்றொரு நெடுவரிசையுடன் (x, x, y) மாற்றுவது வேறுபட்ட தீர்வு சரத்திற்கு வழிவகுக்கும், ஆனால் தீர்க்கக்கூடிய தன்மையை பாதிக்காது, ஏனெனில் இரண்டு நெடுவரிசைகளும் ஒரே கட்டமைப்பை வெளிப்படுத்துகின்றன, அதாவது. முதல் இரண்டு உள்ளீடுகள் சமமானவை, ஆனால் மூன்றாவது ஒன்றிலிருந்து வேறுபட்டவை. ஒவ்வொரு நெடுவரிசையிலும், பெரும்பாலும் a உடன் நிகழும் எழுத்து, b உடன் அடிக்கடி நிகழும் எழுத்து மற்றும் பலவற்றுடன் மாற்றுவதன் மூலம் ஒரு உள்ளீட்டு நிகழ்வை இயல்பாக்கலாம். இயல்பாக்கப்பட்ட நிகழ்வுக்கு ஒரு தீர்வு கொடுக்கப்பட்டால், ஒவ்வொரு நெடுவரிசையிலும் அதன் அசல் பதிப்பிற்கு தீர்வின் எழுத்துக்களை மறுவடிவமைப்பதன் மூலம் அசல் நிகழ்வைக் காணலாம். நெடுவரிசைகளின் வரிசை சிக்கலின் கடினத்தன்மைக்கு பங்களிக்காது. அதாவது, ஒரு குறிப்பிட்ட வரிசைமாற்றத்தின் படி அனைத்து உள்ளீட்டு சரங்களையும் நாம் வரிசைப்படுத்தி, அந்த மாற்றியமைக்கப்பட்ட நிகழ்வுக்கு ஒரு தீர்வு சரம் s ஐப் பெற்றால், π−1 (s) அசல் நிகழ்வுக்கு ஒரு தீர்வாக இருக்கும். எடுத்துக்காட்டு uvwx, xuwv மற்றும் xvwu ஆகிய மூன்று உள்ளீட்டு சரங்களைக் கொண்ட ஒரு எடுத்துக்காட்டு கொடுக்கப்பட்டுள்ளது. இதை இது போன்ற ஒரு மேட்ரிக்ஸாக எழுதலாம்ஃ முதல் நெடுவரிசையில் மதிப்புகள் (u, x, x) உள்ளன. x என்பது பெரும்பாலும் தோன்றும் எழுத்து என்பதால், நாம் அதை a ஆல் மாற்றுகிறோம், மேலும் இரண்டாவது எழுத்தான u ஐ b ஆல் மாற்றுகிறோம், புதிய முதல் நெடுவரிசையைப் பெறுகிறோம் (b, a, a). இரண்டாவது நெடுவரிசையில் மதிப்புகள் (v, u, v) உள்ளன. முதல் நெடுவரிசையைப் பொறுத்தவரை, v என்பது a ஆல் மாற்றப்படுகிறது மற்றும் u என்பது b ஆல் மாற்றப்படுகிறது, இது புதிய இரண்டாவது நெடுவரிசையைப் பெறுகிறது (a, b, a). அனைத்து நெடுவரிசைகளிலும் இதைச் செய்வது இயல்பாக்கப்பட்ட நிகழ்வை வழங்குகிறது இயல்பாக்குதலில் இருந்து பெறப்பட்ட தரவு குறைப்பு உள்ளீட்டை இயல்பாக்குவது எழுத்துக்களின் அளவை அதிகபட்சமாக உள்ளீட்டு சரங்களின் எண்ணிக்கையாக குறைக்கிறது. இது எழுத்துக்களின் அளவைப் பொறுத்து இயங்கும் நேரங்களைக் கொண்ட வழிமுறைகளுக்கு பயனுள்ளதாக இருக்கும். தோராயமான லி மற்றும் பலர். பெரிய மறைக்கப்பட்ட மாறிலிகள் காரணமாக நடைமுறையில் பயன்படுத்த முடியாத ஒரு பல்லுறுப்புக்கோவை-நேர தோராயமான திட்டத்தை உருவாக்கியது. நிலையான-அளவுரு டிராக்டபிலிட்டி நெருக்கமான சரத்தை இதில் தீர்க்க முடியும், இங்கு k என்பது உள்ளீட்டு சரங்களின் எண்ணிக்கை, L என்பது அனைத்து சரங்களின் நீளம் மற்றும் d என்பது தீர்வு சரத்திலிருந்து எந்த உள்ளீட்டு சரத்திற்கும் விரும்பிய அதிகபட்ச தூரமாகும். மற்ற சிக்கல்களுடனான உறவுகள் நெருக்கமான சரம் என்பது மிகவும் பொதுவான நெருக்கமான அடி மூலக்கூறு சிக்கலின் ஒரு சிறப்பு வழக்கு, இது கண்டிப்பாக மிகவும் கடினம். அருகிலுள்ள சரம் பல வழிகளில் நிலையான-அளவுரு டிராக்டபிள் என்று மாறினாலும், இந்த அளவுருக்களைப் பொறுத்தவரை மிக நெருக்கமான அடி மூலக்கூறு W [1]-கடினமானது. குறிப்புகள் NP-கடினமான சிக்கல்கள் முறையான மொழிகள்