పరిశోధన పని బహుశా మా శిక్షణలో అత్యంత ఆసక్తికరమైన భాగం. యూనివర్శిటీలో ఉన్నప్పుడు మీరు ఎంచుకున్న దిశలో మిమ్మల్ని మీరు ప్రయత్నించాలనే ఆలోచన ఉంది. ఉదాహరణకు, సాఫ్ట్‌వేర్ ఇంజినీరింగ్ మరియు మెషిన్ లెర్నింగ్ రంగాలకు చెందిన విద్యార్థులు తరచుగా కంపెనీలలో (ప్రధానంగా JetBrains లేదా Yandex, కానీ మాత్రమే కాదు) పరిశోధన చేయడానికి వెళతారు.
ఈ పోస్ట్‌లో నేను కంప్యూటర్ సైన్స్‌లో నా ప్రాజెక్ట్ గురించి మాట్లాడతాను. నా పనిలో భాగంగా, అత్యంత ప్రసిద్ధ NP-కఠిన సమస్యలలో ఒకదానిని పరిష్కరించడానికి నేను అధ్యయనం చేసాను మరియు ఆచరణలో పెట్టాను: శీర్ష కవరింగ్ సమస్య.
ఈ రోజుల్లో, NP-కఠిన సమస్యలకు ఆసక్తికరమైన విధానం చాలా త్వరగా అభివృద్ధి చెందుతోంది - పారామిటరైజ్డ్ అల్గోరిథంలు. నేను మిమ్మల్ని వేగవంతం చేయడానికి ప్రయత్నిస్తాను, కొన్ని సాధారణ పారామిటరైజ్డ్ అల్గారిథమ్‌లను మీకు చెప్తాను మరియు నాకు చాలా సహాయపడిన ఒక శక్తివంతమైన పద్ధతిని వివరిస్తాను. నేను PACE ఛాలెంజ్ పోటీలో నా ఫలితాలను అందించాను: బహిరంగ పరీక్షల ఫలితాల ప్రకారం, నా పరిష్కారం మూడవ స్థానంలో ఉంది మరియు తుది ఫలితాలు జూలై 1న తెలుస్తుంది.
నా గురించి
నా పేరు వాసిలీ అల్ఫెరోవ్, నేను ఇప్పుడు నేషనల్ రీసెర్చ్ యూనివర్శిటీ హయ్యర్ స్కూల్ ఆఫ్ ఎకనామిక్స్ - సెయింట్ పీటర్స్‌బర్గ్‌లో నా మూడవ సంవత్సరం పూర్తి చేస్తున్నాను. నేను మాస్కో స్కూల్ నం. 179లో చదువుకున్నప్పుడు మరియు కంప్యూటర్ సైన్స్ ఒలింపియాడ్స్‌లో విజయవంతంగా పాల్గొన్నప్పుడు నా పాఠశాల రోజుల నుండి నాకు అల్గోరిథంలపై ఆసక్తి ఉంది.
పరామితి చేయబడిన అల్గారిథమ్‌లలో పరిమిత సంఖ్యలో నిపుణులు బార్‌లోకి ప్రవేశిస్తారు...
పుస్తకం నుండి తీసుకున్న ఉదాహరణ
మీరు ఒక చిన్న పట్టణంలో బార్ సెక్యూరిటీ గార్డ్ అని ఊహించుకోండి. ప్రతి శుక్రవారం, సగం నగరం విశ్రాంతి తీసుకోవడానికి మీ బార్‌కి వస్తుంది, ఇది మీకు చాలా ఇబ్బందిని కలిగిస్తుంది: గొడవలను నివారించడానికి మీరు రౌడీ కస్టమర్‌లను బార్ నుండి బయటకు పంపాలి. చివరికి, మీరు విసుగు చెంది, నివారణ చర్యలు తీసుకోవాలని నిర్ణయించుకుంటారు.
మీ నగరం చిన్నది కాబట్టి, ఏ జంట పోషకులు కలిసి బార్‌లో చేరితే వారితో పోరాడే అవకాశం ఉందో మీకు ఖచ్చితంగా తెలుసు. మీ దగ్గర జాబితా ఉందా n ఈ రాత్రి బార్‌కి వచ్చే వ్యక్తులు. ఎవరూ గొడవ పడకుండా కొంతమంది పట్టణవాసులను బార్ నుండి దూరంగా ఉంచాలని మీరు నిర్ణయించుకుంటారు. అదే సమయంలో, మీ బాస్‌లు లాభాలను కోల్పోవడానికి ఇష్టపడరు మరియు మీరు అంతకు మించి ఇవ్వకపోతే అసంతృప్తిగా ఉంటారు k మానవుడు.
దురదృష్టవశాత్తూ, మీ ముందున్న సమస్య క్లాసిక్ NP-కఠిన సమస్య. మీకు ఆమె గురించి తెలిసి ఉండవచ్చు , లేదా శీర్ష కవరింగ్ సమస్యగా. అటువంటి సమస్యలకు, సాధారణ సందర్భంలో, ఆమోదయోగ్యమైన సమయంలో పనిచేసే అల్గోరిథంలు లేవు. ఖచ్చితంగా చెప్పాలంటే, నిరూపించబడని మరియు చాలా బలమైన పరికల్పన ETH (ఎక్స్‌పోనెన్షియల్ టైమ్ హైపోథెసిస్) ఈ సమస్యను సకాలంలో పరిష్కరించలేమని చెబుతోంది. , అంటే, మీరు పూర్తి శోధన కంటే మెరుగైనది ఏదైనా ఆలోచించలేరు. ఉదాహరణకు, మీ బార్‌కి ఎవరైనా రాబోతున్నారని అనుకుందాం n = 1000 మానవుడు. అప్పుడు పూర్తి శోధన ఉంటుంది సుమారుగా ఉన్న ఎంపికలు - వెర్రి మొత్తం. అదృష్టవశాత్తూ, మీ నిర్వహణ మీకు పరిమితిని ఇచ్చింది k = 10, కాబట్టి మీరు పునరావృతం చేయాల్సిన కలయికల సంఖ్య చాలా తక్కువగా ఉంటుంది: పది మూలకాల ఉపసమితుల సంఖ్య . ఇది ఉత్తమం, కానీ ఇది ఇప్పటికీ శక్తివంతమైన క్లస్టర్‌లో కూడా ఒక రోజులో లెక్కించబడదు.
బార్ యొక్క సందర్శకుల మధ్య ఉన్న సంబంధాల యొక్క ఈ కాన్ఫిగరేషన్‌లో పోరాటం యొక్క అవకాశాన్ని తొలగించడానికి, మీరు బాబ్, డేనియల్ మరియు ఫెడోర్‌లను దూరంగా ఉంచాలి. ఇద్దరు మాత్రమే మిగిలిపోయే పరిష్కారం లేదు.
అందరినీ లోపలికి అనుమతించే సమయం వచ్చిందని దీని అర్థం? ఇతర ఎంపికలను పరిశీలిద్దాం. బాగా, ఉదాహరణకు, మీరు చాలా పెద్ద సంఖ్యలో వ్యక్తులతో పోరాడటానికి అవకాశం ఉన్నవారిని మాత్రమే అనుమతించలేరు. ఎవరైనా కనీసం పోరాడగలిగితే k+1 మరొక వ్యక్తి, అప్పుడు మీరు ఖచ్చితంగా అతన్ని లోపలికి అనుమతించలేరు - లేకుంటే మీరు అందరినీ బయట ఉంచాలి k+1 పట్టణ ప్రజలు, ఎవరితో అతను పోరాడగలడు, ఇది ఖచ్చితంగా నాయకత్వాన్ని కలవరపెడుతుంది.
ఈ సూత్రం ప్రకారం మీరు చేయగలిగిన ప్రతి ఒక్కరినీ మీరు విసిరేయండి. అప్పుడు ప్రతి ఒక్కరూ అంతకు మించి పోరాడగలరు k ప్రజలు. వాటిని బయటకు విసిరేస్తున్నారు k మనిషి, మీరు మరేమీ నిరోధించలేరు గొడవలు. కంటే ఎక్కువ ఉంటే అని దీని అర్థం ఒక వ్యక్తి కనీసం ఒక సంఘర్షణలో పాల్గొన్నట్లయితే, మీరు ఖచ్చితంగా వాటన్నింటినీ నిరోధించలేరు. వాస్తవానికి, మీరు పూర్తిగా సంఘర్షణ లేని వ్యక్తులను ఖచ్చితంగా లోపలికి అనుమతిస్తారు కాబట్టి, మీరు రెండు వందల మందిలో పది మంది పరిమాణంలోని అన్ని ఉపసమితుల ద్వారా వెళ్లాలి. సుమారుగా ఉన్నాయి , మరియు ఈ సంఖ్యలో కార్యకలాపాలు ఇప్పటికే క్లస్టర్‌లో క్రమబద్ధీకరించబడతాయి.
ఎలాంటి వైరుధ్యం లేని వ్యక్తులను మీరు సురక్షితంగా తీసుకెళ్లగలిగితే, కేవలం ఒక వివాదంలో పాల్గొనే వారి సంగతేంటి? వాస్తవానికి, వారి ప్రత్యర్థిపై తలుపును మూసివేయడం ద్వారా కూడా వారిని అనుమతించవచ్చు. నిజానికి, ఆలిస్ బాబ్‌తో మాత్రమే వివాదంలో ఉంటే, మేము ఆలిస్‌ను వారిద్దరిలో నుండి బయటకు పంపితే, మనం ఓడిపోము: బాబ్‌కు ఇతర విభేదాలు ఉండవచ్చు, కానీ ఆలిస్‌కు ఖచ్చితంగా అవి ఉండవు. పైగా మా ఇద్దరినీ లోపలికి రానివ్వకపోవడంలో అర్థం లేదు. అటువంటి ఆపరేషన్ల తర్వాత ఇక మిగిలి ఉండదు అపరిష్కృత విధితో అతిథులు: మేము మాత్రమే కలిగి ఉన్నాము వైరుధ్యాలు, ఒక్కొక్కటి ఇద్దరు పాల్గొనేవారు మరియు ప్రతి ఒక్కరు కనీసం ఇద్దరిలో పాల్గొంటారు. కాబట్టి క్రమబద్ధీకరించడం మాత్రమే మిగిలి ఉంది ఎంపికలు, ల్యాప్‌టాప్‌లో సగం రోజును సులభంగా పరిగణించవచ్చు.
నిజానికి, సాధారణ తార్కికంతో మీరు మరింత ఆకర్షణీయమైన పరిస్థితులను సాధించవచ్చు. మేము ఖచ్చితంగా అన్ని వివాదాలను పరిష్కరించాల్సిన అవసరం ఉందని గుర్తుంచుకోండి, అంటే ప్రతి వైరుధ్య జంట నుండి, మేము అనుమతించని కనీసం ఒక వ్యక్తిని ఎంచుకోండి. కింది అల్గారిథమ్‌ను పరిశీలిద్దాం: ఏదైనా సంఘర్షణను తీసుకోండి, దాని నుండి మేము ఒక భాగస్వామిని తీసివేసి, మిగిలిన వారి నుండి పునరావృతంగా ప్రారంభించి, మరొకరిని తీసివేసి, పునరావృతంగా ప్రారంభించండి. మనం అడుగడుగునా ఒకరిని విసిరివేస్తాము కాబట్టి, అటువంటి అల్గోరిథం యొక్క రికర్షన్ ట్రీ లోతు యొక్క బైనరీ చెట్టు k, కాబట్టి మొత్తంగా అల్గోరిథం పని చేస్తుంది పేరు n శీర్షాల సంఖ్య, మరియు m - పక్కటెముకల సంఖ్య. మా ఉదాహరణలో, ఇది దాదాపు పది మిలియన్లు, ఇది ల్యాప్‌టాప్‌లో మాత్రమే కాకుండా, మొబైల్ ఫోన్‌లో కూడా స్ప్లిట్ సెకనులో లెక్కించబడుతుంది.
పై ఉదాహరణ ఒక ఉదాహరణ పారామితి చేయబడిన అల్గోరిథం. పారామీటరైజ్డ్ అల్గోరిథంలు సమయానుకూలంగా పనిచేసే అల్గారిథమ్‌లు f(k) పాలీ(n)పేరు p - బహుపది, f ఒక ఏకపక్ష కంప్యూటబుల్ ఫంక్షన్, మరియు k - కొన్ని పరామితి, ఇది సమస్య యొక్క పరిమాణం కంటే చాలా తక్కువగా ఉంటుంది.
ఈ అల్గోరిథం ముందు అన్ని తార్కికం ఒక ఉదాహరణ ఇస్తుంది కెర్నలైజేషన్ పారామిటరైజ్డ్ అల్గారిథమ్‌లను రూపొందించడానికి సాధారణ పద్ధతుల్లో ఒకటి. కెర్నలైజేషన్ అనేది పారామీటర్ యొక్క ఫంక్షన్ ద్వారా పరిమితం చేయబడిన విలువకు సమస్య పరిమాణాన్ని తగ్గించడం. ఫలితంగా వచ్చే సమస్యను తరచుగా కెర్నల్ అంటారు. ఈ విధంగా, శీర్షాల డిగ్రీల గురించి సరళమైన తార్కికం ద్వారా, మేము వెర్టెక్స్ కవర్ సమస్య కోసం క్వాడ్రాటిక్ కెర్నల్‌ను పొందాము, ఇది సమాధానం పరిమాణంతో పారామితి చేయబడింది. ఈ టాస్క్ కోసం మీరు ఎంచుకోగల ఇతర సెట్టింగ్‌లు ఉన్నాయి (LP పైన ఉన్న వెర్టెక్స్ కవర్ వంటివి), కానీ ఇదే మేము చర్చించబోతున్న సెట్టింగ్.
పేస్ ఛాలెంజ్
పోటీ (ది పారామీటరైజ్డ్ అల్గారిథమ్స్ అండ్ కంప్యూటేషనల్ ఎక్స్‌పెరిమెంట్స్ ఛాలెంజ్) పారామిటరైజ్డ్ అల్గారిథమ్‌లు మరియు గణన సమస్యలను పరిష్కరించడానికి ఆచరణలో ఉపయోగించే విధానాల మధ్య సంబంధాన్ని ఏర్పరచడానికి 2015లో పుట్టింది. మొదటి మూడు పోటీలు గ్రాఫ్ యొక్క చెట్టు వెడల్పును కనుగొనడానికి కేటాయించబడ్డాయి (), స్టైనర్ చెట్టు కోసం శోధించడం () మరియు చక్రాలను కత్తిరించే శీర్షాల సమితి కోసం శోధించడం () ఈ సంవత్సరం, పైన వివరించిన వెర్టెక్స్ కవరింగ్ సమస్య మీరు మీ చేతిని ప్రయత్నించగల సమస్యల్లో ఒకటి.
పోటీ ప్రతి సంవత్సరం ప్రజాదరణ పొందుతోంది. మీరు ప్రాథమిక డేటాను విశ్వసిస్తే, ఈ సంవత్సరం 24 జట్లు కేవలం శీర్ష కవరింగ్ సమస్యను పరిష్కరించడానికి పోటీలో పాల్గొన్నాయి. పోటీ చాలా గంటలు లేదా ఒక వారం కాదు, కానీ చాలా నెలలు ఉంటుందని గమనించాలి. బృందాలు సాహిత్యాన్ని అధ్యయనం చేయడానికి, వారి స్వంత అసలు ఆలోచనతో ముందుకు రావడానికి మరియు దానిని అమలు చేయడానికి ప్రయత్నించడానికి అవకాశం ఉంది. సారాంశంలో, ఈ పోటీ ఒక పరిశోధన ప్రాజెక్ట్. అత్యంత ప్రభావవంతమైన పరిష్కారాల కోసం ఆలోచనలు మరియు విజేతలకు అవార్డులు కాన్ఫరెన్స్‌తో పాటు నిర్వహించబడతాయి ఐరోపాలో అతిపెద్ద వార్షిక అల్గారిథమిక్ సమావేశంలో భాగంగా (పారామీటర్ మరియు ఖచ్చితమైన గణనపై అంతర్జాతీయ సింపోజియం) . పోటీ గురించి మరింత వివరణాత్మక సమాచారాన్ని ఇక్కడ చూడవచ్చు , మరియు మునుపటి సంవత్సరాల ఫలితాలు అబద్ధం .
పరిష్కార రేఖాచిత్రం
వెర్టెక్స్ కవరింగ్ సమస్యను పరిష్కరించడానికి, నేను పారామిటరైజ్డ్ అల్గారిథమ్‌లను ఉపయోగించి ప్రయత్నించాను. అవి సాధారణంగా రెండు భాగాలను కలిగి ఉంటాయి: సరళీకరణ నియమాలు (ఇది కెర్నలైజేషన్‌కు ఆదర్శంగా దారి తీస్తుంది) మరియు విభజన నియమాలు. సరళీకరణ నియమాలు బహుపది సమయంలో ఇన్‌పుట్‌ను ప్రీప్రాసెసింగ్ చేయడం. అటువంటి నియమాలను వర్తింపజేయడం యొక్క ఉద్దేశ్యం సమస్యను సమానమైన చిన్న సమస్యగా తగ్గించడం. సరళీకరణ నియమాలు అల్గారిథమ్‌లో అత్యంత ఖరీదైన భాగం, మరియు ఈ భాగాన్ని వర్తింపజేయడం మొత్తం రన్నింగ్ టైమ్‌కి దారి తీస్తుంది సాధారణ బహుపది సమయానికి బదులుగా. మా విషయంలో, విభజన నియమాలు ప్రతి శీర్షానికి మీరు దానిని లేదా దాని పొరుగువారిని సమాధానంగా తీసుకోవాలి.
సాధారణ పథకం ఇది: మేము సరళీకరణ నియమాలను వర్తింపజేస్తాము, ఆపై మేము కొన్ని శీర్షాలను ఎంచుకుంటాము మరియు రెండు పునరావృత కాల్‌లు చేస్తాము: మొదటిదానిలో మేము ప్రతిస్పందనగా తీసుకుంటాము మరియు మరొకదానిలో మేము దాని పొరుగువారిని తీసుకుంటాము. దీన్నే మనం ఈ శీర్షం వెంట విభజించడం (బ్రాంచింగ్) అంటాము.
తదుపరి పేరాలో ఈ స్కీమ్‌కి సరిగ్గా ఒక అదనం చేయబడుతుంది.
విభజన (బ్రంచింగ్) నియమాల కోసం ఆలోచనలు
విభజన సంభవించే శీర్షాన్ని ఎలా ఎంచుకోవాలో చర్చిద్దాం.
అల్గోరిథమిక్ కోణంలో ప్రధాన ఆలోచన చాలా అత్యాశతో కూడుకున్నది: గరిష్ట డిగ్రీ యొక్క శీర్షాన్ని తీసుకుందాం మరియు దానితో పాటు విభజించండి. ఎందుకు మంచిదనిపిస్తోంది? ఎందుకంటే రికర్సివ్ కాల్ యొక్క రెండవ శాఖలో మనం ఈ విధంగా చాలా శీర్షాలను తొలగిస్తాము. మీరు మిగిలి ఉన్న చిన్న గ్రాఫ్‌ను లెక్కించవచ్చు మరియు మేము దానిపై త్వరగా పని చేయవచ్చు.
ఈ విధానం, ఇప్పటికే చర్చించబడిన సాధారణ కెర్నలైజేషన్ టెక్నిక్‌లతో, దానికదే బాగా చూపిస్తుంది మరియు పరిమాణంలో అనేక వేల శీర్షాల యొక్క కొన్ని పరీక్షలను పరిష్కరిస్తుంది. కానీ, ఉదాహరణకు, క్యూబిక్ గ్రాఫ్‌లకు (అంటే, ప్రతి శీర్షం యొక్క డిగ్రీ మూడు ఉన్న గ్రాఫ్‌లు) ఇది బాగా పని చేయదు.
చాలా సరళమైన ఆలోచన ఆధారంగా మరొక ఆలోచన ఉంది: గ్రాఫ్ డిస్‌కనెక్ట్ చేయబడితే, దాని కనెక్ట్ చేయబడిన భాగాలపై సమస్య స్వతంత్రంగా పరిష్కరించబడుతుంది, చివరిలో సమాధానాలను కలపడం. ఇది, మార్గం ద్వారా, పథకంలో వాగ్దానం చేసిన చిన్న సవరణ, ఇది పరిష్కారాన్ని గణనీయంగా వేగవంతం చేస్తుంది: ఇంతకుముందు, ఈ సందర్భంలో, భాగాల ప్రతిస్పందనలను లెక్కించడానికి మేము సమయ ఉత్పత్తి కోసం పని చేసాము, కానీ ఇప్పుడు మేము దీని కోసం పని చేస్తాము మొత్తం. మరియు శాఖలను వేగవంతం చేయడానికి, మీరు కనెక్ట్ చేయబడిన గ్రాఫ్‌ను డిస్‌కనెక్ట్ చేయబడినదిగా మార్చాలి.
ఇది ఎలా చెయ్యాలి? గ్రాఫ్‌లో ఉచ్చారణ పాయింట్ ఉంటే, మీరు దానితో పోరాడాలి. ఒక ఉచ్చారణ బిందువు అనేది ఒక శీర్షం అంటే తీసివేయబడినప్పుడు, గ్రాఫ్ దాని కనెక్టివిటీని కోల్పోతుంది. గ్రాఫ్‌లోని అన్ని జంక్షన్ పాయింట్‌లను లీనియర్ టైమ్‌లో క్లాసికల్ అల్గోరిథం ఉపయోగించి కనుగొనవచ్చు. ఈ విధానం శాఖలను గణనీయంగా వేగవంతం చేస్తుంది.
ఎంచుకున్న శీర్షాలలో ఏదైనా తీసివేయబడినప్పుడు, గ్రాఫ్ కనెక్ట్ చేయబడిన భాగాలుగా విభజించబడుతుంది.
మేము దీన్ని చేస్తాము, కానీ మాకు మరింత కావాలి. ఉదాహరణకు, గ్రాఫ్‌లో చిన్న వెర్టెక్స్ కట్‌ల కోసం చూడండి మరియు దాని నుండి శీర్షాల వెంట విభజించండి. కనిష్ట గ్లోబల్ వెర్టెక్స్ కట్‌ను కనుగొనడానికి నాకు తెలిసిన అత్యంత ప్రభావవంతమైన మార్గం క్యూబిక్ సమయంలో నిర్మించబడిన గోమోరి-హు చెట్టును ఉపయోగించడం. PACE ఛాలెంజ్‌లో, సాధారణ గ్రాఫ్ పరిమాణం అనేక వేల శీర్షాలు. ఈ పరిస్థితిలో, రికర్షన్ ట్రీ యొక్క ప్రతి శీర్షం వద్ద బిలియన్ల ఆపరేషన్లు చేయవలసి ఉంటుంది. నిర్ణీత సమయంలో సమస్యను పరిష్కరించడం అసాధ్యం అని తేలింది.
పరిష్కారాన్ని ఆప్టిమైజ్ చేయడానికి ప్రయత్నిద్దాం. గరిష్ట ప్రవాహాన్ని నిర్మించే ఏదైనా అల్గోరిథం ద్వారా ఒక జత శీర్షాల మధ్య కత్తిరించిన కనిష్ట శీర్షాన్ని కనుగొనవచ్చు. మీరు దానిని అటువంటి నెట్‌వర్క్‌లోకి అనుమతించవచ్చు , ఆచరణలో ఇది చాలా త్వరగా పని చేస్తుంది. ఆపరేటింగ్ సమయానికి ఒక అంచనాను నిరూపించడం సిద్ధాంతపరంగా సాధ్యమేనా అని నాకు అనుమానం ఉంది , ఇది ఇప్పటికే చాలా ఆమోదయోగ్యమైనది.
యాదృచ్ఛిక శీర్షాల జతల మధ్య కట్‌ల కోసం నేను చాలాసార్లు ప్రయత్నించాను మరియు అత్యంత బ్యాలెన్స్‌డ్‌ను తీసుకోవాలనుకుంటున్నాను. దురదృష్టవశాత్తూ, ఇది ఓపెన్ PACE ఛాలెంజ్ టెస్టింగ్‌లో పేలవమైన ఫలితాలను అందించింది. నేను గరిష్ట స్థాయి శీర్షాలను విభజించే అల్గారిథమ్‌తో పోల్చాను, వాటిని అవరోహణ లోతుపై పరిమితితో అమలు చేసాను. ఈ విధంగా కట్‌ను కనుగొనడానికి ప్రయత్నిస్తున్న అల్గారిథమ్ పెద్ద గ్రాఫ్‌లను వదిలివేస్తుంది. కోతలు చాలా అసమతుల్యతగా మారిన వాస్తవం దీనికి కారణం: 5-10 శీర్షాలను తొలగించిన తరువాత, 15-20 మాత్రమే విభజించడం సాధ్యమైంది.
సిద్ధాంతపరంగా వేగవంతమైన అల్గారిథమ్‌ల గురించిన కథనాలు విభజన కోసం శీర్షాలను ఎంచుకోవడానికి చాలా అధునాతన పద్ధతులను ఉపయోగిస్తాయని గమనించాలి. ఇటువంటి పద్ధతులు చాలా క్లిష్టమైన అమలును కలిగి ఉంటాయి మరియు సమయం మరియు జ్ఞాపకశక్తి పరంగా తరచుగా పేలవమైన పనితీరును కలిగి ఉంటాయి. అభ్యాసానికి చాలా ఆమోదయోగ్యమైన వాటిని నేను గుర్తించలేకపోయాను.
సరళీకరణ నియమాలను ఎలా వర్తింపజేయాలి
కెర్నలైజేషన్ కోసం మాకు ఇప్పటికే ఆలోచనలు ఉన్నాయి. నేను మీకు గుర్తు చేస్తాను:
- వివిక్త శీర్షం ఉంటే, దాన్ని తొలగించండి.
- డిగ్రీ 1 యొక్క శీర్షం ఉన్నట్లయితే, దానిని తీసివేసి, ప్రతిస్పందనగా దాని పొరుగువారిని తీసుకోండి.
- కనీసం డిగ్రీ యొక్క శీర్షం ఉంటే k+1, తిరిగి వెనక్కి తీసుకోరా.
మొదటి రెండింటితో ప్రతిదీ స్పష్టంగా ఉంది, మూడవదానితో ఒక ఉపాయం ఉంది. బార్ గురించిన హాస్య సమస్య ఉన్నట్లయితే, మాకు గరిష్ట పరిమితి ఇవ్వబడింది k, PACE ఛాలెంజ్‌లో మీరు కనిష్ట పరిమాణంలో ఉన్న శీర్ష కవర్‌ను కనుగొనవలసి ఉంటుంది. ఇది శోధన సమస్యలను నిర్ణయ సమస్యలుగా మార్చడం; తరచుగా రెండు రకాల సమస్యల మధ్య తేడా ఉండదు. ఆచరణలో, మనం శీర్ష కవరింగ్ సమస్య కోసం పరిష్కరిణిని వ్రాస్తున్నట్లయితే, తేడా ఉండవచ్చు. ఉదాహరణకు, మూడవ పాయింట్ వలె.
అమలు కోణం నుండి, కొనసాగడానికి రెండు మార్గాలు ఉన్నాయి. మొదటి విధానాన్ని ఇటరేటివ్ డీపెనింగ్ అంటారు. ఇది క్రింది విధంగా ఉంది: మేము సమాధానంపై దిగువ నుండి కొంత సహేతుకమైన పరిమితితో ప్రారంభించవచ్చు, ఆపై ఈ ప్రతిబంధకం కంటే తక్కువ పునరావృతం కాకుండా పై నుండి సమాధానంపై ప్రతిబంధకంగా ఈ పరిమితిని ఉపయోగించి మా అల్గోరిథంను అమలు చేయవచ్చు. మేము కొంత సమాధానాన్ని కనుగొన్నట్లయితే, అది సరైనదని హామీ ఇవ్వబడుతుంది, లేకుంటే మనం ఈ పరిమితిని ఒకటి పెంచి మళ్లీ ప్రారంభించవచ్చు.
మరొక విధానం ఏమిటంటే, ప్రస్తుత సరైన సమాధానాన్ని నిల్వ చేయడం మరియు చిన్న సమాధానం కోసం వెతకడం, దొరికినప్పుడు ఈ పరామితిని మార్చడం k శోధనలో అనవసరమైన శాఖలను ఎక్కువగా కత్తిరించడం కోసం.
అనేక రాత్రిపూట ప్రయోగాలు చేసిన తర్వాత, నేను ఈ రెండు పద్ధతుల కలయికపై స్థిరపడ్డాను: మొదట, నేను శోధన లోతుపై ఒక రకమైన పరిమితితో నా అల్గారిథమ్‌ను నడుపుతున్నాను (దీనిని ఎంచుకోవడం వలన ప్రధాన పరిష్కారంతో పోలిస్తే ఇది చాలా తక్కువ సమయం పడుతుంది) మరియు ఉత్తమమైనదాన్ని ఉపయోగిస్తాను సమాధానానికి ఎగువ పరిమితిగా పరిష్కారం కనుగొనబడింది - అంటే, అదే విషయానికి k.
డిగ్రీ 2 యొక్క శీర్షాలు
మేము డిగ్రీ 0 మరియు 1 యొక్క శీర్షాలను పరిష్కరించాము. ఇది డిగ్రీ 2 యొక్క శీర్షాలతో చేయవచ్చని తేలింది, అయితే దీనికి గ్రాఫ్ నుండి మరింత క్లిష్టమైన కార్యకలాపాలు అవసరం.
దీన్ని వివరించడానికి, మనం ఏదో ఒకవిధంగా శీర్షాలను గుర్తించాలి. డిగ్రీ 2 యొక్క శీర్షాన్ని శీర్షం అని పిలుద్దాం v, మరియు దాని పొరుగు - శీర్షాలు x и y. తరువాత మనకు రెండు కేసులు ఉంటాయి.
- ఉన్నప్పుడు x и y - పొరుగువారు. అప్పుడు మీరు సమాధానం చెప్పగలరు x и yమరియు v తొలగించు. నిజానికి, ఈ త్రిభుజం నుండి కనీసం రెండు శీర్షాలను ప్రతిఫలంగా తీసుకోవాలి మరియు మనం తీసుకుంటే మనం ఖచ్చితంగా ఓడిపోము. x и y: వారు బహుశా ఇతర పొరుగువారిని కలిగి ఉంటారు, మరియు v వారు ఇక్కడ లేరు.
- ఉన్నప్పుడు x и y - పొరుగువారు కాదు. అప్పుడు మూడు శీర్షాలను ఒకటిగా అంటించవచ్చని పేర్కొంది. ఆలోచన ఏమిటంటే, ఈ సందర్భంలో సరైన సమాధానం ఉంది, దీనిలో మనం దేనినైనా తీసుకుంటాము v, లేదా రెండు శీర్షాలు x и y. అంతేకాక, మొదటి సందర్భంలో మేము ప్రతిస్పందనగా అన్ని పొరుగువారిని తీసుకోవలసి ఉంటుంది x и y, కానీ రెండవ లో అది అవసరం లేదు. మేము ప్రతిస్పందనగా అతుక్కొని ఉన్న శీర్షాన్ని తీసుకోనప్పుడు మరియు మనం చేసినప్పుడు ఇది సరిగ్గా సందర్భాలకు అనుగుణంగా ఉంటుంది. రెండు సందర్భాల్లోనూ అటువంటి ఆపరేషన్ నుండి ప్రతిస్పందన ఒకటి తగ్గుతుందని గమనించడం మాత్రమే మిగిలి ఉంది.
ఈ విధానాన్ని సరసమైన సరళ సమయంలో ఖచ్చితంగా అమలు చేయడం చాలా కష్టమని గమనించాలి. శీర్షాలను అతుక్కోవడం సంక్లిష్టమైన ఆపరేషన్; మీరు పొరుగువారి జాబితాలను కాపీ చేయాలి. ఇది అజాగ్రత్తగా జరిగితే, మీరు అసింప్టోటిక్‌గా సబ్‌ప్టిమల్ రన్నింగ్ టైమ్‌తో ముగించవచ్చు (ఉదాహరణకు, మీరు ప్రతి గ్లైయింగ్ తర్వాత చాలా అంచులను కాపీ చేస్తే). నేను డిగ్రీ 2 యొక్క శీర్షాల నుండి మొత్తం మార్గాలను కనుగొనడం మరియు అటువంటి శీర్షాల నుండి లేదా అలాంటి అన్ని శీర్షాల నుండి చక్రాల వంటి ప్రత్యేక సందర్భాల సమూహాన్ని విశ్లేషించడంపై స్థిరపడ్డాను.
అదనంగా, ఈ ఆపరేషన్ రివర్సిబుల్ కావడం అవసరం, తద్వారా పునరావృతం నుండి తిరిగి వచ్చినప్పుడు మేము గ్రాఫ్‌ను దాని అసలు రూపానికి పునరుద్ధరిస్తాము. దీన్ని నిర్ధారించడానికి, నేను విలీనం చేయబడిన శీర్షాల అంచుల జాబితాలను క్లియర్ చేయలేదు, ఆపై ఏ అంచులు ఎక్కడికి వెళ్లాలో నాకు తెలుసు. గ్రాఫ్‌ల యొక్క ఈ అమలుకు కూడా ఖచ్చితత్వం అవసరం, కానీ ఇది సరసమైన సరళ సమయాన్ని అందిస్తుంది. మరియు అనేక పదుల వేల అంచుల గ్రాఫ్‌ల కోసం, ఇది ప్రాసెసర్ కాష్‌కి సరిపోతుంది, ఇది వేగంలో గొప్ప ప్రయోజనాలను ఇస్తుంది.
లీనియర్ కెర్నల్
చివరగా, కెర్నల్ యొక్క అత్యంత ఆసక్తికరమైన భాగం.
ప్రారంభించడానికి, బైపార్టైట్ గ్రాఫ్‌లలో కనీస శీర్ష కవర్‌ను ఉపయోగించి కనుగొనవచ్చని గుర్తుచేసుకోండి . దీన్ని చేయడానికి మీరు అల్గోరిథం ఉపయోగించాలి అక్కడ గరిష్ట సరిపోలికను కనుగొనడానికి, ఆపై సిద్ధాంతాన్ని ఉపయోగించండి .
లీనియర్ కెర్నల్ యొక్క ఆలోచన ఇది: మొదట మనం గ్రాఫ్‌ను విభజించాము, అంటే ప్రతి శీర్షానికి బదులుగా v రెండు శిఖరాలను జోడిద్దాం и , మరియు ప్రతి అంచుకు బదులుగా u - v రెండు పక్కటెముకలు కలుపుదాం и . ఫలితంగా గ్రాఫ్ ద్వైపాక్షికంగా ఉంటుంది. అందులో కనీస శీర్ష కవర్‌ను కనుగొనండి. ఒరిజినల్ గ్రాఫ్‌లోని కొన్ని శీర్షాలు రెండుసార్లు అక్కడకు వస్తాయి, కొన్ని ఒక్కసారి మాత్రమే, మరియు కొన్ని ఎప్పుడూ ఉండవు. ఈ సందర్భంలో ఒక్కసారి కూడా తగలని శీర్షాలను తొలగించి రెండుసార్లు కొట్టిన వాటిని వెనక్కి తీసుకోవచ్చని నెమ్‌హౌజర్-ట్రాటర్ సిద్ధాంతం పేర్కొంది. అంతేకాకుండా, మిగిలిన శీర్షాలలో (ఒకసారి కొట్టినవి) మీరు సమాధానంగా కనీసం సగం తీసుకోవాలని ఆమె చెప్పింది.
అంతకు మించి వదిలేయడం ఇప్పుడే నేర్చుకున్నాం 2k శిఖరాలు నిజానికి, మిగిలిన సమాధానం అన్ని శీర్షాలలో కనీసం సగం అయితే, మొత్తంగా అంతకంటే ఎక్కువ శీర్షాలు లేవు 2k.
ఇక్కడ నేను ఒక చిన్న అడుగు ముందుకు వేయగలిగాను. ఈ విధంగా నిర్మించబడిన కెర్నల్ బైపార్టైట్ గ్రాఫ్‌లో మనం ఎలాంటి కనిష్ట శీర్ష కవర్‌ని తీసుకున్నామో దానిపై ఆధారపడి ఉంటుందని స్పష్టమవుతుంది. మిగిలిన శీర్షాల సంఖ్య తక్కువగా ఉండేలా నేను ఒకదాన్ని తీసుకోవాలనుకుంటున్నాను. ఇంతకుముందు, వారు దీన్ని సమయానికి మాత్రమే చేయగలిగారు . నేను ఈ సమయంలో ఈ అల్గోరిథం యొక్క అమలుతో ముందుకు వచ్చాను , అందువలన, ఈ కోర్ని ప్రతి శాఖా దశలో వందల వేల శీర్షాల గ్రాఫ్‌లలో శోధించవచ్చు.
ఫలితంగా
అనేక వందల శీర్షాలు మరియు అనేక వేల అంచుల పరీక్షలపై నా పరిష్కారం బాగా పనిచేస్తుందని ప్రాక్టీస్ చూపిస్తుంది. అటువంటి పరీక్షలలో అరగంటలో పరిష్కారం కనుగొనబడుతుందని ఆశించడం చాలా సాధ్యమే. ఆమోదయోగ్యమైన సమయంలో సమాధానాన్ని కనుగొనే సంభావ్యత, సూత్రప్రాయంగా, గ్రాఫ్ తగినంత పెద్ద సంఖ్యలో అధిక స్థాయి శీర్షాలను కలిగి ఉంటే పెరుగుతుంది, ఉదాహరణకు, డిగ్రీ 10 మరియు అంతకంటే ఎక్కువ.
పోటీలో పాల్గొనడానికి, పరిష్కారాలను పంపవలసి ఉంటుంది . అక్కడ అందించిన సమాచారాన్ని బట్టి చూస్తే , ఓపెన్ టెస్ట్‌లలో నా సొల్యూషన్ ఇరవైలో మూడవ స్థానంలో ఉంది, రెండవ నుండి పెద్ద గ్యాప్‌తో. పూర్తిగా నిజాయితీగా ఉండాలంటే, పోటీలోనే పరిష్కారాలు ఎలా మూల్యాంకనం చేయబడతాయో పూర్తిగా స్పష్టంగా తెలియదు: ఉదాహరణకు, నా పరిష్కారం నాల్గవ స్థానంలో ఉన్న పరిష్కారం కంటే తక్కువ పరీక్షలలో ఉత్తీర్ణత సాధిస్తుంది, కానీ ఉత్తీర్ణత సాధించిన వాటిపై, ఇది వేగంగా పని చేస్తుంది.
క్లోజ్డ్ పరీక్షల ఫలితాలు జూలై XNUMXవ తేదీన తెలుస్తాయి.
మూలం: www.habr.com