ஆராய்ச்சி வேலை என்பது எங்கள் பயிற்சியின் மிகவும் சுவாரஸ்யமான பகுதியாக இருக்கலாம். பல்கலைக்கழகத்தில் இருக்கும்போதே நீங்கள் தேர்ந்தெடுத்த திசையில் உங்களை முயற்சிக்க வேண்டும் என்பதே இதன் யோசனை. எடுத்துக்காட்டாக, மென்பொருள் பொறியியல் மற்றும் இயந்திர கற்றல் பகுதிகளைச் சேர்ந்த மாணவர்கள் பெரும்பாலும் நிறுவனங்களில் (முக்கியமாக JetBrains அல்லது Yandex, ஆனால் மட்டும் அல்ல) ஆராய்ச்சி செய்யச் செல்கிறார்கள்.
இந்த இடுகையில் நான் கணினி அறிவியலில் எனது திட்டத்தைப் பற்றி பேசுவேன். எனது பணியின் ஒரு பகுதியாக, மிகவும் பிரபலமான NP-கடினமான பிரச்சனைகளில் ஒன்றைத் தீர்ப்பதற்கான அணுகுமுறைகளைப் படித்து நடைமுறைப்படுத்தினேன்: உச்சியை மூடும் பிரச்சனை.
இப்போதெல்லாம், NP-கடினமான சிக்கல்களுக்கான ஒரு சுவாரஸ்யமான அணுகுமுறை மிக விரைவாக உருவாகி வருகிறது - அளவுரு நெறிமுறைகள். நான் உங்களை வேகப்படுத்த முயற்சிப்பேன், சில எளிய அளவுருக்கள் அல்காரிதம்களைச் சொல்கிறேன் மற்றும் எனக்கு மிகவும் உதவிய ஒரு சக்திவாய்ந்த முறையை விவரிக்கிறேன். PACE சவால் போட்டியில் எனது முடிவுகளை வழங்கினேன்: திறந்த சோதனைகளின் முடிவுகளின்படி, எனது தீர்வு மூன்றாவது இடத்தைப் பிடித்தது, இறுதி முடிவுகள் ஜூலை 1 அன்று அறியப்படும்.
என்னைப் பற்றி
எனது பெயர் வாசிலி ஆல்ஃபெரோவ், நான் இப்போது தேசிய ஆராய்ச்சி பல்கலைக்கழக உயர்நிலைப் பொருளாதாரப் பள்ளியில் மூன்றாம் ஆண்டை முடித்துள்ளேன் - செயின்ட் பீட்டர்ஸ்பர்க். நான் மாஸ்கோ பள்ளி எண் 179 இல் படித்து கணினி அறிவியல் ஒலிம்பியாட்களில் வெற்றிகரமாக பங்கேற்றபோது, எனது பள்ளி நாட்களில் இருந்து அல்காரிதங்களில் ஆர்வமாக இருந்தேன்.
அளவுருவாக்கப்பட்ட அல்காரிதங்களில் குறிப்பிட்ட எண்ணிக்கையிலான வல்லுநர்கள் பட்டியில் நுழைகிறார்கள்...
புத்தகத்திலிருந்து எடுக்கப்பட்ட உதாரணம்
நீங்கள் ஒரு சிறிய நகரத்தில் பார் பாதுகாப்பு காவலராக இருப்பதாக கற்பனை செய்து பாருங்கள். ஒவ்வொரு வெள்ளிக்கிழமையும், பாதி நகரம் ஓய்வெடுக்க உங்கள் பட்டிக்கு வருகிறது, இது உங்களுக்கு நிறைய சிக்கல்களைத் தருகிறது: சண்டைகளைத் தடுக்க ரவுடி வாடிக்கையாளர்களை பட்டியில் இருந்து வெளியேற்ற வேண்டும். இறுதியில், நீங்கள் சோர்வடைந்து, தடுப்பு நடவடிக்கைகளை எடுக்க முடிவு செய்கிறீர்கள்.
உங்கள் நகரம் சிறியதாக இருப்பதால், எந்த ஜோடி புரவலர்கள் ஒன்றாக ஒரு பட்டியில் சென்றால் அவர்கள் சண்டையிடுவார்கள் என்பது உங்களுக்குத் தெரியும். என்ற பட்டியல் உங்களிடம் உள்ளதா n இன்றிரவு மதுக்கடைக்கு வரும் மக்கள். யாரும் சண்டையிடாமல் சில நகரவாசிகளை மதுக்கடைக்கு வெளியே வைத்திருக்க முடிவு செய்கிறீர்கள். அதே நேரத்தில், உங்கள் முதலாளிகள் லாபத்தை இழக்க விரும்பவில்லை, மேலும் நீங்கள் அனுமதிக்கவில்லை என்றால் மகிழ்ச்சியற்றவர்களாக இருப்பார்கள். k மக்கள்.
துரதிர்ஷ்டவசமாக, உங்களுக்கு முன் உள்ள பிரச்சனை ஒரு உன்னதமான NP-கடினமான பிரச்சனை. நீங்கள் அவளை அறிந்திருக்கலாம் , அல்லது உச்சியை மறைக்கும் பிரச்சனையாக. இத்தகைய பிரச்சனைகளுக்கு, பொது வழக்கில், ஏற்றுக்கொள்ளக்கூடிய நேரத்தில் வேலை செய்யும் வழிமுறைகள் எதுவும் இல்லை. துல்லியமாக, நிரூபிக்கப்படாத மற்றும் மிகவும் வலுவான கருதுகோள் ETH (அதிவேக நேர கருதுகோள்) இந்த சிக்கலை சரியான நேரத்தில் தீர்க்க முடியாது என்று கூறுகிறது. , அதாவது, முழுமையான தேடலைக் காட்டிலும் சிறப்பாக எதையும் நீங்கள் நினைக்க முடியாது. உதாரணமாக, உங்கள் மதுக்கடைக்கு ஒருவர் வரப்போகிறார் என்று வைத்துக்கொள்வோம் n = 1000 மனிதன். பின்னர் முழுமையான தேடல் இருக்கும் தோராயமாக இருக்கும் விருப்பங்கள் - பைத்தியம் அளவு. அதிர்ஷ்டவசமாக, உங்கள் நிர்வாகம் உங்களுக்கு வரம்பைக் கொடுத்துள்ளது கே = 10, எனவே நீங்கள் மீண்டும் மீண்டும் செய்ய வேண்டிய சேர்க்கைகளின் எண்ணிக்கை மிகவும் சிறியது: பத்து உறுப்புகளின் துணைக்குழுக்களின் எண்ணிக்கை . இது சிறந்தது, ஆனால் சக்திவாய்ந்த கிளஸ்டரில் கூட இது ஒரு நாளில் கணக்கிடப்படாது.
பட்டியின் பார்வையாளர்களுக்கு இடையே உள்ள இறுக்கமான உறவுகளின் இந்த கட்டமைப்பில் சண்டையின் சாத்தியத்தை அகற்ற, நீங்கள் பாப், டேனியல் மற்றும் ஃபெடரை வெளியே வைத்திருக்க வேண்டும். இதில் இரண்டு பேர் மட்டுமே எஞ்சுவார்கள் என்பதில் எந்தத் தீர்வும் இல்லை.
வளைந்து கொடுத்து அனைவரையும் உள்ளே அனுமதிக்க வேண்டிய நேரம் இது என்று அர்த்தமா? மற்ற விருப்பங்களைக் கருத்தில் கொள்வோம். சரி, எடுத்துக்காட்டாக, அதிக எண்ணிக்கையிலான மக்களுடன் சண்டையிடக்கூடியவர்களை மட்டும் நீங்கள் அனுமதிக்க முடியாது. யாராவது குறைந்தபட்சம் சண்டையிட முடியுமானால் கே + 1 மற்றொரு நபர், நீங்கள் நிச்சயமாக அவரை உள்ளே அனுமதிக்க முடியாது - இல்லையெனில் நீங்கள் அனைவரையும் வெளியே வைத்திருக்க வேண்டும் கே + 1 நகர மக்கள், அவர் யாருடன் சண்டையிட முடியும், இது நிச்சயமாக தலைமையை வருத்தப்படுத்தும்.
இந்தக் கொள்கையின்படி உங்களால் முடிந்த அனைவரையும் தூக்கி எறியட்டும். பின்னர் மற்ற அனைவரும் சண்டையிட முடியாது k மக்கள். அவர்களை வெளியே வீசுதல் k மனிதனே, உன்னால் எதையும் தடுக்க முடியாது மோதல்கள். அதிகமாக இருந்தால் என்று அர்த்தம் ஒரு நபர் குறைந்தபட்சம் ஒரு மோதலில் ஈடுபட்டிருந்தால், நீங்கள் நிச்சயமாக அனைத்தையும் தடுக்க முடியாது. நிச்சயமாக, நீங்கள் முற்றிலும் முரண்படாத நபர்களை நிச்சயமாக அனுமதிப்பீர்கள் என்பதால், இருநூறு பேரில் பத்து பேரின் அனைத்து துணைக்குழுக்களையும் நீங்கள் பார்க்க வேண்டும். தோராயமாக உள்ளன , மற்றும் இந்த எண்ணிக்கையிலான செயல்பாடுகளை ஏற்கனவே கிளஸ்டரில் வரிசைப்படுத்தலாம்.
மோதலே இல்லாத நபர்களை உங்களால் பாதுகாப்பாக அழைத்துச் செல்ல முடிந்தால், ஒரே ஒரு மோதலில் பங்கேற்பவர்களை என்ன செய்வது? உண்மையில், அவர்கள் எதிராளியின் கதவை மூடுவதன் மூலமும் அனுமதிக்கப்படலாம். உண்மையில், ஆலிஸ் பாப்புடன் மட்டுமே முரண்பட்டால், அவர்கள் இருவரில் இருந்து ஆலிஸை வெளியேற்றினால், நாங்கள் இழக்க மாட்டோம்: பாப் வேறு மோதல்களைக் கொண்டிருக்கலாம், ஆனால் ஆலிஸுக்கு நிச்சயமாக அவை இல்லை. மேலும், எங்கள் இருவரையும் உள்ளே விடாமல் இருப்பதில் அர்த்தமில்லை. அத்தகைய செயல்பாடுகளுக்குப் பிறகு, இனி எதுவும் இல்லை தீர்க்கப்படாத விதி கொண்ட விருந்தினர்கள்: எங்களிடம் மட்டுமே உள்ளது மோதல்கள், ஒவ்வொன்றும் இரண்டு பங்கேற்பாளர்கள் மற்றும் ஒவ்வொன்றும் குறைந்தது இருவரில் ஈடுபட்டுள்ளன. எனவே வரிசைப்படுத்துவதே எஞ்சியுள்ளது மடிக்கணினியில் அரை நாள் எளிதாகக் கருதக்கூடிய விருப்பங்கள்.
உண்மையில், எளிமையான பகுத்தறிவு மூலம் நீங்கள் இன்னும் கவர்ச்சிகரமான நிலைமைகளை அடைய முடியும். எல்லா சர்ச்சைகளையும் நாங்கள் நிச்சயமாக தீர்க்க வேண்டும் என்பதை நினைவில் கொள்க, அதாவது, ஒவ்வொரு முரண்பட்ட ஜோடியிலிருந்தும், நாங்கள் அனுமதிக்காத ஒருவரையாவது தேர்வு செய்யவும். பின்வரும் வழிமுறையைப் பரிசீலிப்போம்: எந்தவொரு மோதலையும் எடுத்துக்கொள்வோம், அதில் இருந்து ஒரு பங்கேற்பாளரை நீக்கிவிட்டு, மீதியில் இருந்து மீண்டும் மீண்டும் தொடங்குவோம், பிறகு மற்றவரை அகற்றிவிட்டு, மீண்டும் மீண்டும் தொடங்குவோம். ஒவ்வொரு அடியிலும் நாம் ஒருவரைத் தூக்கி எறிவதால், அத்தகைய வழிமுறையின் மறுநிகழ்வு மரம் ஆழத்தின் பைனரி மரமாகும். k, ஆக மொத்தத்தில் அல்காரிதம் வேலை செய்கிறது அங்கு n என்பது செங்குத்துகளின் எண்ணிக்கை, மற்றும் m - விலா எலும்புகளின் எண்ணிக்கை. எங்கள் எடுத்துக்காட்டில், இது சுமார் பத்து மில்லியன் ஆகும், இது ஒரு மடிக்கணினியில் மட்டுமல்ல, மொபைல் போனிலும் கூட ஒரு பிளவு நொடியில் கணக்கிடப்படலாம்.
மேலே உள்ள உதாரணம் ஒரு உதாரணம் அளவுருவாக்கப்பட்ட அல்காரிதம். பாராமீட்டரைஸ்டு அல்காரிதம்கள் என்பது சரியான நேரத்தில் இயங்கும் அல்காரிதம்கள் f(k) poly(n)அங்கு p - பல்லுறுப்புக்கோவை, f ஒரு தன்னிச்சையான கணக்கிடக்கூடிய செயல்பாடு, மற்றும் k - சில அளவுருக்கள், இது சிக்கலின் அளவை விட மிகவும் சிறியதாக இருக்கும்.
இந்த வழிமுறைக்கு முன் உள்ள அனைத்து தர்க்கங்களும் ஒரு உதாரணத்தைக் கொடுக்கிறது கர்னலைசேஷன் அளவுருவாக்கப்பட்ட அல்காரிதம்களை உருவாக்குவதற்கான பொதுவான நுட்பங்களில் ஒன்றாகும். கர்னலைசேஷன் என்பது ஒரு அளவுருவின் செயல்பாட்டால் வரையறுக்கப்பட்ட மதிப்பிற்கு சிக்கல் அளவைக் குறைப்பதாகும். இதன் விளைவாக ஏற்படும் சிக்கல் பெரும்பாலும் கர்னல் என்று அழைக்கப்படுகிறது. எனவே, செங்குத்துகளின் அளவைப் பற்றிய எளிய காரணத்தால், வெர்டெக்ஸ் கவர் சிக்கலுக்கான இருபடி கர்னலைப் பெற்றோம், பதிலின் அளவு அளவுருக்கள். இந்த பணிக்கு நீங்கள் தேர்வுசெய்யக்கூடிய பிற அமைப்புகள் உள்ளன (எல்பிக்கு மேலே உள்ள வெர்டெக்ஸ் கவர் போன்றவை), ஆனால் இது தான் நாங்கள் விவாதிக்கும் அமைப்பு.
வேக சவால்
போட்டி (The Parameterized Algorithms and Computational Experiments Challenge) 2015 இல் பிறந்தது, கணக்கீட்டுச் சிக்கல்களைத் தீர்க்க நடைமுறையில் பயன்படுத்தப்படும் அளவுரு வழிமுறைகள் மற்றும் அணுகுமுறைகளுக்கு இடையே ஒரு தொடர்பை ஏற்படுத்துவதற்காக. முதல் மூன்று போட்டிகள் ஒரு வரைபடத்தின் மர அகலத்தைக் கண்டறிவதற்காக அர்ப்பணிக்கப்பட்டன (), ஸ்டெய்னர் மரத்தைத் தேடுகிறது () மற்றும் சுழற்சிகளைக் குறைக்கும் செங்குத்துகளின் தொகுப்பைத் தேடுகிறது () இந்த ஆண்டு, நீங்கள் முயற்சி செய்யக்கூடிய சிக்கல்களில் ஒன்று மேலே விவரிக்கப்பட்ட உச்சியை மூடும் பிரச்சனை.
போட்டி ஒவ்வொரு ஆண்டும் பிரபலமடைந்து வருகிறது. பூர்வாங்க தரவுகளை நீங்கள் நம்பினால், இந்த ஆண்டு 24 அணிகள் உச்சி கவரிங் பிரச்சனையை மட்டும் தீர்க்கும் போட்டியில் பங்கேற்றன. போட்டி பல மணிநேரங்கள் அல்லது ஒரு வாரம் கூட நீடிக்கும், ஆனால் பல மாதங்கள் என்பது கவனிக்கத்தக்கது. அணிகள் இலக்கியத்தைப் படிக்கவும், தங்கள் சொந்த அசல் யோசனையைக் கொண்டு வந்து அதைச் செயல்படுத்த முயற்சிக்கவும் வாய்ப்பு உள்ளது. சாராம்சத்தில், இந்த போட்டி ஒரு ஆராய்ச்சி திட்டம். மிகவும் பயனுள்ள தீர்வுகளுக்கான யோசனைகள் மற்றும் வெற்றியாளர்களுக்கான விருதுகள் மாநாட்டுடன் இணைந்து நடைபெறும் ஐரோப்பாவில் நடைபெறும் மிகப்பெரிய வருடாந்திர அல்காரிதம் கூட்டத்தின் ஒரு பகுதியாக (அளவுருப்படுத்தப்பட்ட மற்றும் துல்லியமான கணக்கீடு பற்றிய சர்வதேச சிம்போசியம்) . போட்டி பற்றிய விரிவான தகவல்களை இங்கே காணலாம் , மற்றும் முந்தைய ஆண்டுகளின் முடிவுகள் பொய் .
தீர்வு வரைபடம்
வெர்டெக்ஸ் கவரிங் சிக்கலைத் தீர்க்க, அளவுருவாக்கப்பட்ட அல்காரிதம்களைப் பயன்படுத்த முயற்சித்தேன். அவை பொதுவாக இரண்டு பகுதிகளைக் கொண்டிருக்கின்றன: எளிமைப்படுத்துதல் விதிகள் (இது கர்னலைசேஷனுக்கு வழிவகுக்கும்) மற்றும் பிளவு விதிகள். எளிமைப்படுத்தல் விதிகள் என்பது பல்லுறுப்புக்கோவை நேரத்தில் உள்ளீட்டை முன்செயல்படுத்துவதாகும். அத்தகைய விதிகளைப் பயன்படுத்துவதன் நோக்கம் சிக்கலைச் சமமான சிறிய சிக்கலாகக் குறைப்பதாகும். எளிமைப்படுத்தல் விதிகள் அல்காரிதத்தின் மிகவும் விலையுயர்ந்த பகுதியாகும், மேலும் இந்த பகுதியைப் பயன்படுத்துவது மொத்த இயங்கும் நேரத்திற்கு வழிவகுக்கிறது எளிய பல்லுறுப்புக்கோவை நேரத்திற்கு பதிலாக. எங்கள் விஷயத்தில், பிளவு விதிகள் ஒவ்வொரு உச்சிக்கும் நீங்கள் அதை அல்லது அதன் அண்டை வீட்டாரை ஒரு பதிலாக எடுத்துக் கொள்ள வேண்டும் என்ற உண்மையை அடிப்படையாகக் கொண்டது.
பொதுவான திட்டம் இதுதான்: நாங்கள் எளிமைப்படுத்தல் விதிகளைப் பயன்படுத்துகிறோம், பின்னர் சில உச்சியைத் தேர்ந்தெடுத்து, இரண்டு சுழல்நிலை அழைப்புகளைச் செய்கிறோம்: முதலில் நாம் அதை பதிலளிக்கிறோம், மற்றொன்றில் அதன் அனைத்து அண்டை நாடுகளையும் எடுத்துக்கொள்கிறோம். இதைத்தான் இந்த உச்சியில் பிரித்தல் (கிளைத்தல்) என்கிறோம்.
அடுத்த பத்தியில் இந்த திட்டத்தில் சரியாக ஒன்று சேர்க்கப்படும்.
பிரித்தல் (பிரன்சிங்) விதிகளுக்கான யோசனைகள்
பிளவு ஏற்படும் ஒரு உச்சியை எவ்வாறு தேர்வு செய்வது என்று விவாதிப்போம்.
முக்கிய யோசனை அல்காரிதம் அர்த்தத்தில் மிகவும் பேராசை கொண்டது: அதிகபட்ச பட்டத்தின் உச்சியை எடுத்து அதனுடன் பிரிப்போம். அது ஏன் சிறப்பாக தெரிகிறது? ஏனெனில் சுழல்நிலை அழைப்பின் இரண்டாவது கிளையில் நாம் இந்த வழியில் நிறைய முனைகளை அகற்றுவோம். மீதமுள்ள சிறிய வரைபடத்தை நீங்கள் நம்பலாம், நாங்கள் அதை விரைவாகச் செய்யலாம்.
இந்த அணுகுமுறை, ஏற்கனவே விவாதிக்கப்பட்ட எளிய கர்னலைசேஷன் நுட்பங்களுடன், தன்னை நன்றாகக் காட்டுகிறது மற்றும் பல ஆயிரம் செங்குத்து அளவுகளின் சில சோதனைகளைத் தீர்க்கிறது. ஆனால், எடுத்துக்காட்டாக, க்யூபிக் கிராஃப்களுக்கு (அதாவது, ஒவ்வொரு உச்சியின் அளவும் மூன்றாக இருக்கும் வரைபடங்கள்) இது நன்றாக வேலை செய்யாது.
மிகவும் எளிமையான யோசனையின் அடிப்படையில் மற்றொரு யோசனை உள்ளது: வரைபடம் துண்டிக்கப்பட்டால், அதன் இணைக்கப்பட்ட கூறுகளின் சிக்கலை சுயாதீனமாக தீர்க்க முடியும், இறுதியில் பதில்களை இணைக்கலாம். இது, திட்டத்தில் ஒரு சிறிய வாக்குறுதியளிக்கப்பட்ட மாற்றமாகும், இது தீர்வை கணிசமாக விரைவுபடுத்தும்: முன்பு, இந்த விஷயத்தில், கூறுகளின் பதில்களைக் கணக்கிடுவதற்கான காலத்தின் தயாரிப்புக்காக நாங்கள் வேலை செய்தோம், ஆனால் இப்போது நாங்கள் வேலை செய்கிறோம். தொகை. மேலும் கிளைகளை விரைவுபடுத்த, இணைக்கப்பட்ட வரைபடத்தை துண்டிக்கப்பட்டதாக மாற்ற வேண்டும்.
அதை எப்படி செய்வது? வரைபடத்தில் ஒரு உச்சரிப்பு புள்ளி இருந்தால், நீங்கள் அதை எதிர்த்துப் போராட வேண்டும். ஒரு உச்சரிப்பு புள்ளி என்பது ஒரு உச்சியை அகற்றும் போது, வரைபடம் அதன் இணைப்பை இழக்கிறது. ஒரு வரைபடத்தில் உள்ள அனைத்து சந்திப்பு புள்ளிகளையும் நேரியல் நேரத்தில் ஒரு கிளாசிக்கல் அல்காரிதம் பயன்படுத்தி காணலாம். இந்த அணுகுமுறை கிளைகளை கணிசமாக துரிதப்படுத்துகிறது.
தேர்ந்தெடுக்கப்பட்ட செங்குத்துகள் ஏதேனும் அகற்றப்பட்டால், வரைபடம் இணைக்கப்பட்ட கூறுகளாகப் பிரிக்கப்படும்.
நாங்கள் இதைச் செய்வோம், ஆனால் எங்களுக்கு இன்னும் வேண்டும். எடுத்துக்காட்டாக, வரைபடத்தில் சிறிய உச்சி வெட்டுக்களைப் பார்த்து, அதிலிருந்து செங்குத்துகளுடன் பிரிக்கவும். க்யூபிக் நேரத்தில் கட்டப்பட்ட கோமோரி-ஹு மரத்தைப் பயன்படுத்துவதே குறைந்தபட்ச உலகளாவிய உச்சி வெட்டைக் கண்டறிய எனக்குத் தெரிந்த மிகச் சிறந்த வழி. PACE சவாலில், வழக்கமான வரைபட அளவு பல ஆயிரம் செங்குத்துகள் ஆகும். இந்த சூழ்நிலையில், ரிகர்ஷன் மரத்தின் ஒவ்வொரு முனையிலும் பில்லியன் கணக்கான செயல்பாடுகள் செய்யப்பட வேண்டும். ஒதுக்கப்பட்ட நேரத்தில் சிக்கலைத் தீர்ப்பது வெறுமனே சாத்தியமற்றது என்று மாறிவிடும்.
தீர்வை மேம்படுத்த முயற்சிப்போம். ஒரு ஜோடி செங்குத்துகளுக்கு இடையே உள்ள குறைந்தபட்ச உச்சியை அதிகபட்ச ஓட்டத்தை உருவாக்கும் எந்த வழிமுறையாலும் கண்டறிய முடியும். நீங்கள் அதை அத்தகைய நெட்வொர்க்கில் அனுமதிக்கலாம் , நடைமுறையில் இது மிக விரைவாக வேலை செய்கிறது. இயக்க நேரத்திற்கான மதிப்பீட்டை நிரூபிப்பது கோட்பாட்டளவில் சாத்தியமா என்ற சந்தேகம் எனக்கு உள்ளது , இது ஏற்கனவே ஏற்றுக்கொள்ளத்தக்கது.
சீரற்ற செங்குத்து ஜோடிகளுக்கு இடையில் வெட்டுக்களைக் காணவும், மிகவும் சமநிலையான ஒன்றை எடுக்கவும் நான் பல முறை முயற்சித்தேன். துரதிர்ஷ்டவசமாக, இது திறந்த PACE சவால் சோதனையில் மோசமான முடிவுகளைத் தந்தது. நான் அதை ஒரு அல்காரிதத்துடன் ஒப்பிட்டுப் பார்த்தேன், அது உச்சநிலை உச்சநிலையைப் பிரித்து, வம்சாவளியின் ஆழத்தில் ஒரு வரம்புடன் அவற்றை இயக்குகிறது. இந்த வழியில் ஒரு வெட்டு கண்டுபிடிக்க முயற்சிக்கும் ஒரு அல்காரிதம் பெரிய வரைபடங்களுக்குப் பின்னால் உள்ளது. வெட்டுக்கள் மிகவும் சமநிலையற்றதாக மாறியதே இதற்குக் காரணம்: 5-10 செங்குத்துகளை அகற்றியதால், 15-20 மட்டுமே பிரிக்க முடிந்தது.
கோட்பாட்டு ரீதியாக வேகமான வழிமுறைகளைப் பற்றிய கட்டுரைகள் பிரிப்பதற்கான செங்குத்துகளைத் தேர்ந்தெடுப்பதற்கு மிகவும் மேம்பட்ட நுட்பங்களைப் பயன்படுத்துகின்றன என்பது கவனிக்கத்தக்கது. இத்தகைய நுட்பங்கள் மிகவும் சிக்கலான செயலாக்கம் மற்றும் நேரம் மற்றும் நினைவகத்தின் அடிப்படையில் பெரும்பாலும் மோசமான செயல்திறன் கொண்டவை. நடைமுறைக்கு மிகவும் ஏற்றுக்கொள்ளக்கூடியவற்றை என்னால் அடையாளம் காண முடியவில்லை.
எளிமைப்படுத்தல் விதிகளை எவ்வாறு பயன்படுத்துவது
எங்களிடம் ஏற்கனவே கர்னலைசேஷன் யோசனைகள் உள்ளன. நான் உங்களுக்கு நினைவூட்டுகிறேன்:
- தனிமைப்படுத்தப்பட்ட உச்சி இருந்தால், அதை நீக்கவும்.
- பட்டம் 1 இன் உச்சியில் இருந்தால், அதை அகற்றி, அதற்குப் பதில் அண்டை வீட்டாரை எடுத்துக் கொள்ளுங்கள்.
- குறைந்தபட்சம் பட்டத்தின் உச்சி இருந்தால் கே + 1, அதை திரும்ப பெறு.
முதல் இரண்டில் எல்லாம் தெளிவாக உள்ளது, மூன்றாவதாக ஒரு தந்திரம் உள்ளது. ஒரு பார் பற்றிய நகைச்சுவைப் பிரச்சனையில் எங்களுக்கு அதிகபட்ச வரம்பு வழங்கப்பட்டது k, பின்னர் PACE சவாலில் நீங்கள் குறைந்தபட்ச அளவு ஒரு உச்சி அட்டையை கண்டுபிடிக்க வேண்டும். இது தேடல் சிக்கல்களை முடிவெடுக்கும் சிக்கல்களாக மாற்றும் ஒரு பொதுவான அம்சமாகும்; பெரும்பாலும் இரண்டு வகையான சிக்கல்களுக்கு இடையில் எந்த வித்தியாசமும் இல்லை. நடைமுறையில், உச்சியை மறைக்கும் பிரச்சனைக்கு நாம் ஒரு தீர்வை எழுதினால், வித்தியாசம் இருக்கலாம். உதாரணமாக, மூன்றாவது புள்ளியைப் போல.
செயல்படுத்தல் பார்வையில், தொடர இரண்டு வழிகள் உள்ளன. முதல் அணுகுமுறை இட்ரேடிவ் டீப்பனிங் என்று அழைக்கப்படுகிறது. இது பின்வருமாறு: பதிலில் கீழே இருந்து சில நியாயமான கட்டுப்பாடுகளுடன் தொடங்கலாம், பின்னர் இந்த தடையை மேலே இருந்து பதில் மீது ஒரு தடையாகப் பயன்படுத்தி எங்கள் வழிமுறையை இயக்கலாம், இந்த தடையை விட மறுநிகழ்வில் கீழே செல்லாமல். சில பதில்களைக் கண்டறிந்தால், அது உகந்ததாக இருக்கும் என்பது உறுதி, இல்லையெனில் இந்த வரம்பை ஒன்றால் அதிகரித்து மீண்டும் தொடங்கலாம்.
மற்றொரு அணுகுமுறை, சில தற்போதைய உகந்த பதிலைச் சேமித்து சிறிய பதிலைத் தேடுவது, இந்த அளவுருவைக் கண்டறிந்ததும் மாற்றுவது k தேடலில் தேவையற்ற கிளைகளை அதிக அளவில் வெட்டுவதற்கு.
பல இரவு நேர சோதனைகளை நடத்திய பிறகு, இந்த இரண்டு முறைகளின் கலவையில் நான் தீர்வு கண்டேன்: முதலில், எனது அல்காரிதத்தை தேடல் ஆழத்தில் ஒருவித வரம்புடன் இயக்குகிறேன் (இதைத் தேர்ந்தெடுப்பது, முக்கிய தீர்வுடன் ஒப்பிடும்போது மிகக் குறைவான நேரத்தை எடுக்கும்) மற்றும் சிறந்ததைப் பயன்படுத்துகிறேன். விடைக்கான உச்ச வரம்பாகக் காணப்படும் தீர்வு - அதாவது, அதே விஷயத்திற்கு k.
பட்டம் 2 இன் முனைகள்
பட்டம் 0 மற்றும் 1 இன் முனைகளை நாங்கள் கையாண்டுள்ளோம். இது பட்டம் 2 இன் செங்குத்துகளுடன் செய்யப்படலாம் என்று மாறிவிடும், ஆனால் இதற்கு வரைபடத்திலிருந்து மிகவும் சிக்கலான செயல்பாடுகள் தேவைப்படும்.
இதை விளக்க, நாம் எப்படியாவது செங்குத்துகளை குறிக்க வேண்டும். பட்டம் 2-ன் உச்சியை உச்சம் என்று அழைப்போம் v, மற்றும் அதன் அண்டை - vertices x и y. அடுத்து இரண்டு வழக்குகள் இருக்கும்.
- போது x и y - பக்கத்து. பிறகு பதில் சொல்லலாம் x и yமற்றும் v அழி. உண்மையில், இந்த முக்கோணத்திலிருந்து குறைந்தது இரண்டு செங்குத்துகளையாவது எடுக்க வேண்டும், நாம் எடுத்தால் நிச்சயமாக இழக்க மாட்டோம். x и y: அவர்களுக்கு மற்ற அண்டை வீட்டாரும் இருக்கலாம், மற்றும் v அவர்கள் இங்கு இல்லை.
- போது x и y - அயலவர்கள் அல்ல. பின்னர் மூன்று முனைகளையும் ஒன்றாக ஒட்டலாம் என்று கூறப்படுகிறது. யோசனை என்னவென்றால், இந்த விஷயத்தில் ஒரு உகந்த பதில் உள்ளது, அதில் ஒன்றை நாங்கள் எடுத்துக்கொள்கிறோம் v, அல்லது இரண்டு முனைகளும் x и y. மேலும், முதல் வழக்கில் நாம் பதில் அனைத்து அண்டை எடுக்க வேண்டும் x и y, ஆனால் இரண்டாவது அது அவசியம் இல்லை. பதிலுக்கு நாம் ஒட்டப்பட்ட உச்சியை எடுக்காதபோது மற்றும் நாம் செய்யும் போது இது சரியாக பொருந்தும். இரண்டு சந்தர்ப்பங்களிலும் அத்தகைய செயல்பாட்டின் பதில் ஒன்று குறைகிறது என்பதைக் கவனத்தில் கொள்ள வேண்டும்.
இந்த அணுகுமுறை நியாயமான நேரியல் நேரத்தில் துல்லியமாக செயல்படுத்த மிகவும் கடினம் என்பது கவனிக்கத்தக்கது. செங்குத்துகளை ஒட்டுவது ஒரு சிக்கலான செயல்; நீங்கள் அண்டை நாடுகளின் பட்டியல்களை நகலெடுக்க வேண்டும். இது கவனக்குறைவாகச் செய்தால், நீங்கள் அசிம்ப்டோடிக் சப்டிமல் இயங்கும் நேரத்துடன் முடிவடையும் (உதாரணமாக, ஒவ்வொரு ஒட்டுதலுக்குப் பிறகும் நிறைய விளிம்புகளை நகலெடுத்தால்). பட்டம் 2 இன் செங்குத்துகளிலிருந்து முழுப் பாதைகளையும் கண்டறிவதிலும், அத்தகைய முனைகளிலிருந்து சுழற்சிகள் அல்லது ஒன்றைத் தவிர மற்ற எல்லாச் செங்குத்துகளிலிருந்தும் சில சிறப்பு நிகழ்வுகளை பகுப்பாய்வு செய்வதிலும் நான் முடிவு செய்தேன்.
கூடுதலாக, இந்த செயல்பாடு மீளக்கூடியதாக இருப்பது அவசியம், இதனால் மறுநிகழ்வில் இருந்து திரும்பும் போது வரைபடத்தை அதன் அசல் வடிவத்திற்கு மீட்டெடுக்கிறோம். இதை உறுதிப்படுத்த, இணைக்கப்பட்ட முனைகளின் விளிம்புப் பட்டியலை நான் அழிக்கவில்லை, அதன்பின் எந்தெந்த விளிம்புகள் எங்கு செல்ல வேண்டும் என்று எனக்குத் தெரியும். வரைபடங்களின் இந்த செயலாக்கத்திற்கும் துல்லியம் தேவைப்படுகிறது, ஆனால் இது நியாயமான நேரியல் நேரத்தை வழங்குகிறது. பல பல்லாயிரக்கணக்கான விளிம்புகளின் வரைபடங்களுக்கு, இது செயலி தற்காலிக சேமிப்பில் பொருந்துகிறது, இது வேகத்தில் பெரும் நன்மைகளை அளிக்கிறது.
நேரியல் கர்னல்
இறுதியாக, கர்னலின் மிகவும் சுவாரஸ்யமான பகுதி.
தொடங்குவதற்கு, இருதரப்பு வரைபடங்களில் குறைந்தபட்ச உச்சி அட்டையைப் பயன்படுத்திக் காணலாம் என்பதை நினைவில் கொள்க . இதைச் செய்ய, நீங்கள் அல்காரிதத்தைப் பயன்படுத்த வேண்டும் அங்கு அதிகபட்ச பொருத்தத்தைக் கண்டறிய, பின்னர் தேற்றத்தைப் பயன்படுத்தவும் .
ஒரு நேரியல் கர்னலின் யோசனை இதுதான்: முதலில் நாம் வரைபடத்தை பிரிக்கிறோம், அதாவது ஒவ்வொரு உச்சிக்கும் பதிலாக v இரண்டு சிகரங்களைச் சேர்ப்போம் и , மற்றும் ஒவ்வொரு விளிம்பிற்கும் பதிலாக u - v இரண்டு விலா எலும்புகளை சேர்ப்போம் и . இதன் விளைவாக வரும் வரைபடம் இருதரப்பாக இருக்கும். அதில் குறைந்தபட்ச உச்சி அட்டையைக் கண்டுபிடிப்போம். அசல் வரைபடத்தின் சில செங்குத்துகள் இரண்டு முறை அங்கு வரும், சில ஒரு முறை மட்டுமே, சில ஒருபோதும் வராது. Nemhauser-Trotter தேற்றம் இந்த வழக்கில் ஒரு முறை கூட அடிக்காத முனைகளை அகற்றிவிட்டு இரண்டு முறை அடித்ததை திரும்பப் பெறலாம் என்று கூறுகிறது. மேலும், மீதமுள்ள செங்குத்துகளில் (ஒரு முறை அடித்தவை) நீங்கள் குறைந்தது பாதியையாவது பதிலாக எடுக்க வேண்டும் என்று அவர் கூறுகிறார்.
அதற்கு மேல் விட்டுவிடக் கற்றுக்கொண்டோம் 2k சிகரங்கள் உண்மையில், மீதமுள்ள பதில் அனைத்து செங்குத்துகளிலும் குறைந்தது பாதியாக இருந்தால், மொத்தத்தில் அதிகமான செங்குத்துகள் இல்லை 2k.
இங்கே நான் ஒரு சிறிய அடி எடுத்து வைக்க முடிந்தது. இந்த வழியில் கட்டப்பட்ட கர்னல் இருதரப்பு வரைபடத்தில் நாம் எந்த வகையான குறைந்தபட்ச வெர்டெக்ஸ் அட்டையை எடுத்தோம் என்பதைப் பொறுத்தது என்பது தெளிவாகிறது. மீதமுள்ள முனைகளின் எண்ணிக்கை குறைவாக இருக்கும் வகையில் ஒன்றை எடுக்க விரும்புகிறேன். முன்னதாக, அவர்களால் இதை சரியான நேரத்தில் மட்டுமே செய்ய முடிந்தது . நான் அந்த நேரத்தில் இந்த வழிமுறையை செயல்படுத்த கொண்டு வந்தேன் , எனவே, இந்த மையத்தை ஒவ்வொரு கிளை நிலையிலும் நூறாயிரக்கணக்கான செங்குத்துகளின் வரைபடங்களில் தேடலாம்.
விளைவாக
பல நூறு செங்குத்துகள் மற்றும் பல ஆயிரம் விளிம்புகளின் சோதனைகளில் எனது தீர்வு நன்றாக வேலை செய்கிறது என்பதை பயிற்சி காட்டுகிறது. இதுபோன்ற சோதனைகளில் அரை மணி நேரத்தில் தீர்வு கிடைக்கும் என்று எதிர்பார்க்கலாம். ஒரு ஏற்றுக்கொள்ளக்கூடிய நேரத்தில் ஒரு பதிலைக் கண்டுபிடிப்பதற்கான நிகழ்தகவு, கொள்கையளவில், வரைபடத்தில் போதுமான அளவு உயர் பட்டத்தின் செங்குத்துகள் இருந்தால், எடுத்துக்காட்டாக, பட்டம் 10 மற்றும் அதற்கு மேல் இருந்தால் அதிகரிக்கிறது.
போட்டியில் பங்கேற்க, தீர்வுகளை அனுப்ப வேண்டியிருந்தது . அங்கு வழங்கப்பட்ட தகவல்களின் அடிப்படையில் ஆராயப்படுகிறது , திறந்த சோதனைகளில் எனது தீர்வு இருபதுக்கு மூன்றாவது இடத்தில் உள்ளது, இரண்டாவது பெரிய இடைவெளியுடன். முற்றிலும் உண்மையைச் சொல்வதென்றால், போட்டியிலேயே தீர்வுகள் எவ்வாறு மதிப்பிடப்படும் என்பது முற்றிலும் தெளிவாகத் தெரியவில்லை: எடுத்துக்காட்டாக, எனது தீர்வு நான்காவது இடத்தில் உள்ள தீர்வை விட குறைவான சோதனைகளில் தேர்ச்சி பெறுகிறது, ஆனால் தேர்ச்சி பெற்றவற்றில், அது வேகமாக வேலை செய்கிறது.
மூடப்பட்ட சோதனைகளின் முடிவுகள் ஜூலை 1 ஆம் தேதி அறியப்படும்.
ஆதாரம்: www.habr.com