በParameterized Algorithms የ NP-Hard ችግሮችን እንዴት መፍታት እንደሚቻል

የምርምር ሥራ ምናልባት የሥልጠናችን በጣም አስደሳች ክፍል ነው። ሀሳቡ በዩኒቨርሲቲ ውስጥ እያለ እራስዎን በመረጡት አቅጣጫ መሞከር ነው. ለምሳሌ በሶፍትዌር ኢንጂነሪንግ እና በማሽን መማሪያ አካባቢ ያሉ ተማሪዎች ብዙ ጊዜ በኩባንያዎች ውስጥ ምርምር ለማድረግ ይሄዳሉ (በዋነኝነት JetBrains ወይም Yandex, ግን ብቻ አይደለም).

በዚህ ጽሑፍ ውስጥ በኮምፒተር ሳይንስ ውስጥ ስለ ፕሮጄክቴ እናገራለሁ. እንደ ሥራዬ አካል፣ በጣም ዝነኛ ከሆኑ የNP-Hard ችግሮች አንዱን ለመፍታት አቀራረቦችን አጥንቼ ወደ ተግባር ገባሁ። የ vertex ሽፋን ችግር.

በአሁኑ ጊዜ ለ NP-hard ችግሮች አስደሳች አቀራረብ በጣም በፍጥነት እያደገ ነው - parameterized ስልተ ቀመሮች። እርስዎን ለማፋጠን እሞክራለሁ ፣ አንዳንድ ቀላል ፓራሜትራዊ ስልተ ቀመሮችን እነግርዎታለሁ እና በጣም የረዳኝን አንድ ኃይለኛ ዘዴን ግለጽ። ውጤቶቼን በPACE ፈታኝ ውድድር ላይ አቅርቤ ነበር፡ በክፍት ፈተናዎች ውጤት መሰረት የእኔ መፍትሄ ሶስተኛ ደረጃን ይይዛል እና የመጨረሻው ውጤት ጁላይ 1 ላይ ይታወቃል።

ስለ እኔ

ስሜ ቫሲሊ አልፌሮቭ እባላለሁ፣ አሁን ሦስተኛ ዓመትዬን በብሔራዊ የምርምር ዩኒቨርሲቲ ከፍተኛ የኢኮኖሚክስ ትምህርት ቤት - ሴንት ፒተርስበርግ እያጠናቀቅኩ ነው። በሞስኮ ትምህርት ቤት ቁጥር 179 ስማር እና በኮምፒተር ሳይንስ ኦሊምፒያድስ በተሳካ ሁኔታ ስሳተፍ ከትምህርት ቀናቴ ጀምሮ በአልጎሪዝም ላይ ፍላጎት ነበረኝ።

በመለኪያ ስልተ ቀመሮች ውስጥ የተወሰኑ ልዩ ባለሙያዎች ወደ አሞሌው ውስጥ ይገባሉ…

ከመጽሐፉ የተወሰደ ምሳሌ "የተመጣጣኝ ስልተ ቀመሮች"

በአንዲት ትንሽ ከተማ ውስጥ የቡና ቤት ጠባቂ እንደሆንክ አድርገህ አስብ። በየሳምንቱ አርብ ግማሹ ከተማው ለመዝናናት ወደ ቡና ቤትዎ ይመጣል፣ ይህም ብዙ ችግር ይፈጥርብዎታል፡ ግጭቶችን ለመከላከል ጨካኝ ደንበኞችን ከባር ውስጥ ማስወጣት ያስፈልግዎታል። ውሎ አድሮ ጠግበዋል እና የመከላከያ እርምጃዎችን ለመውሰድ ይወስናሉ.

ከተማዎ ትንሽ ስለሆነች፣ አብረው ባር ውስጥ ከገቡ የትኞቹ ጥንዶች ደጋፊዎች ሊጣሉ እንደሚችሉ በትክክል ያውቃሉ። ዝርዝር አለህ n ዛሬ ማታ ወደ ቡና ቤት የሚመጡ ሰዎች. ማንም ሰው ሳይጣላ አንዳንድ የከተማ ነዋሪዎችን ከቡና ቤት ውጭ ለማድረግ ወስነሃል። በተመሳሳይ ጊዜ አለቆቻችሁ ትርፍ ማጣት አይፈልጉም እና ብዙ ካልፈቀዱ ደስተኛ አይሆኑም. k ሰዎች.

እንደ አለመታደል ሆኖ፣ ከእርስዎ በፊት ያለው ችግር የሚታወቀው NP-hard ችግር ነው። እንደ እሷ ልታውቋት ትችላላችሁ የቬርቴክስ ሽፋን, ወይም እንደ የአከርካሪ ሽፋን ችግር. ለእንደዚህ አይነት ችግሮች, በአጠቃላይ ሁኔታ, ተቀባይነት ባለው ጊዜ ውስጥ የሚሰሩ ስልተ ቀመሮች የሉም. በትክክል ለመናገር፣ ያልተረጋገጠው እና በጣም ጠንካራ መላምት ETH (Exponential Time hypothesis) ይህ ችግር በጊዜ ሊፈታ እንደማይችል ይናገራል። ፣ ማለትም ፣ ከተጠናቀቀ ፍለጋ በተሻለ ሁኔታ ምንም ነገር ማሰብ አይችሉም። ለምሳሌ፣ አንድ ሰው ወደ መጠጥ ቤትዎ ሊመጣ ነው እንበል n = 1000 ሰው። ከዚያ ሙሉ ፍለጋው ይሆናል በግምት ያሉ አማራጮች - እብድ መጠን. እንደ እድል ሆኖ፣ የእርስዎ አስተዳደር ገደብ ሰጥቶዎታል ኪ = 10, ስለዚህ እንደገና ለመድገም የሚያስፈልግዎ የጥምረቶች ብዛት በጣም ትንሽ ነው: የአስር ንጥረ ነገሮች ንዑስ ስብስቦች ብዛት ነው. . ይህ የተሻለ ነው, ነገር ግን አሁንም በኃይለኛ ክላስተር ላይ እንኳን በአንድ ቀን ውስጥ አይቆጠርም.

በቡና ቤት ጎብኝዎች መካከል ያለው የሻከረ ግንኙነት በዚህ ውቅር ውስጥ የውጊያ እድልን ለማስወገድ ቦብ፣ ዳንኤል እና ፌዶርን ማስወጣት ያስፈልግዎታል። ሁለት ብቻ የሚቀሩበት መፍትሄ የለም።

ይህ ማለት ሁሉም ሰው እንዲገባ ለማድረግ ጊዜው አሁን ነው ማለት ነው? ሌሎች አማራጮችን እንመልከት። ደህና ፣ ለምሳሌ ፣ ከብዙ ሰዎች ጋር ሊጣሉ የሚችሉትን ብቻ ማስገባት አይችሉም ። አንድ ሰው ቢያንስ መዋጋት ከቻለ ኪ + 1 ሌላ ሰው ፣ ከዚያ በእርግጠኝነት እሱን እንዲገባ መፍቀድ አይችሉም - አለበለዚያ ሁሉንም ሰው ማስወጣት አለብዎት ኪ + 1 የከተማ ነዋሪዎች፣ ከነሱ ጋር መታገል የሚችል፣ ይህም በእርግጠኝነት አመራሩን ያናድዳል።

በዚህ መርህ መሰረት የምትችለውን ሁሉ እንድትጥል እናድርግ። ከዚያ ሁሉም ሰው ከምንም በላይ ሊዋጋ አይችልም። k ሰዎች. እነሱን ወደ ውጭ መጣል k ሰው ፣ ከምንም በላይ መከላከል አይችሉም ግጭቶች. ይህ ማለት ብዙ ካለ አንድ ሰው ቢያንስ በአንድ ግጭት ውስጥ ከተሳተፈ በእርግጠኝነት ሁሉንም መከላከል አይችሉም። በእርግጥ እርስዎ ሙሉ በሙሉ ግጭት የሌላቸውን ሰዎች እንዲገቡ ስለሚያደርጉ ከሁለት መቶ ሰዎች ውስጥ አሥር ሁሉንም የመጠን ስብስቦችን ማለፍ ያስፈልግዎታል። በግምት አሉ። , እና ይህ የክዋኔዎች ብዛት ቀድሞውኑ በክላስተር ላይ ሊደረደር ይችላል.

ምንም ዓይነት ግጭት የሌላቸውን ግለሰቦች በጥንቃቄ መውሰድ ከቻሉ በአንድ ግጭት ውስጥ ብቻ የሚሳተፉትስ? እንደውም ተቀናቃኞቻቸውን በሩን በመዝጋት እንዲገቡ ሊፈቀድላቸው ይችላል። በእርግጥ አሊስ ከቦብ ጋር ብቻ ከተጋጨች አሊስን ከሁለቱ ካስወጣናቸው አንሸነፍም፡ ቦብ ሌሎች ግጭቶች ሊኖሩት ይችላል ነገር ግን አሊስ የላትም። ከዚህም በላይ ሁለታችንንም እንዳናስገባ ለኛ ምንም ትርጉም የለውም። ከእንደዚህ አይነት ስራዎች በኋላ ምንም ተጨማሪ ነገር አይኖርም ያልተፈታ ዕጣ ያላቸው እንግዶች: እኛ ብቻ ነን ግጭቶች, እያንዳንዳቸው ሁለት ተሳታፊዎች እና እያንዳንዳቸው ቢያንስ በሁለት ይሳተፋሉ. ስለዚህ የቀረው መደርደር ብቻ ነው። አማራጮች, በቀላሉ በላፕቶፕ ላይ ግማሽ ቀን ሊቆጠር ይችላል.

በእውነቱ ፣ በቀላል አመክንዮ የበለጠ ማራኪ ሁኔታዎችን ማግኘት ይችላሉ። ሁሉንም አለመግባባቶች በእርግጠኝነት መፍታት እንደሚያስፈልገን አስተውል፣ ማለትም፣ ከተጋጩ ባልና ሚስት መካከል ቢያንስ አንድ ሰው እንዲገባ የማንፈቅድለትን ይምረጡ። የሚከተለውን ስልተ-ቀመር እናስብ፡- ማንኛውንም ግጭት ወስደን አንዱን ተሳታፊ እናስወግደዋለን እና ከቀሪው ደጋግመን እንጀምራለን ከዚያም ሌላውን አስወግድ እና ደግሞ ደጋግመን እንጀምራለን። አንድን ሰው በእያንዳንዱ ደረጃ ላይ ስለምንጥል, የእንደዚህ አይነት ስልተ-ቀመር ድግግሞሽ ዛፍ ጥልቀት ያለው ሁለትዮሽ ዛፍ ነው k, ስለዚህ በአጠቃላይ ስልተ ቀመር በ ውስጥ ይሰራል የት n የመንገዶች ብዛት ነው, እና m - የጎድን አጥንት ቁጥር. በእኛ ምሳሌ, ይህ አሥር ሚሊዮን ገደማ ነው, ይህም በላፕቶፕ ላይ ብቻ ሳይሆን በሞባይል ስልክም እንኳን በሰከንድ ውስጥ ሊሰላ ይችላል.

ከላይ ያለው ምሳሌ ምሳሌ ነው። parameterized አልጎሪዝም. ፓራሜትራዊ ስልተ ቀመሮች በጊዜ ውስጥ የሚሰሩ ስልተ ቀመሮች ናቸው። f (k) ፖሊ(n)የት p - ፖሊኖሚል; f የዘፈቀደ ሊሰላ ተግባር ነው፣ እና k - አንዳንድ ግቤት ፣ ምናልባትም ፣ ከችግሩ መጠን በጣም ያነሰ ይሆናል።

ከዚህ ስልተ-ቀመር በፊት ያሉት ሁሉም ምክንያቶች ምሳሌ ይሰጣሉ ከርነልላይዜሽን ፓራሜትራዊ ስልተ ቀመሮችን ለመፍጠር ከአጠቃላይ ቴክኒኮች አንዱ ነው። ከርነልላይዜሽን የችግሩን መጠን በመለኪያ ተግባር ወደተገደበ እሴት መቀነስ ነው። የችግሩ መንስኤ ብዙውን ጊዜ ከርነል ይባላል. ስለዚህም ስለ የቁመት ደረጃዎች ቀላል ምክንያት በማድረግ ለቬርቴክስ ሽፋን ችግር ባለአራት ከርነል አግኝተናል፣ በመልሱ መጠን። ለዚህ ተግባር መምረጥ የምትችላቸው ሌሎች መቼቶች አሉ (እንደ ቬርቴክስ ሽፋን ከ LP በላይ)፣ ግን ይህ የምንወያይበት መቼት ነው።

የፍጥነት ፈተና

ውድድር የPACE ፈተና (The Parameterized Algorithms and Computitional Experiments Challenge) በ 2015 ተወለደ በተለዋዋጭ ስልተ ቀመሮች እና በስሌት ችግሮችን ለመፍታት በተግባር ጥቅም ላይ በሚውሉ አቀራረቦች መካከል ግንኙነት ለመፍጠር። የመጀመሪያዎቹ ሶስት ውድድሮች የአንድን ግራፍ የዛፍ ስፋት ለመፈለግ ያተኮሩ ነበሩ (የዛፍ ስፋትየስታይነር ዛፍ መፈለግ (የስታይነር ዛፍ) እና ዑደቶችን የሚቆርጡ ጫፎችን በመፈለግ (የግብረመልስ Vertex አዘጋጅ). በዚህ አመት, እጅዎን መሞከር ከሚችሉት ችግሮች አንዱ ከላይ የተገለፀው የአከርካሪ ሽፋን ችግር ነው.

ውድድሩ በየዓመቱ ተወዳጅነት እያገኘ ነው. የቅድሚያ መረጃውን የምታምን ከሆነ በዚህ አመት 24 ቡድኖች ውድድሩን በመሸፈን ላይ ያለውን ችግር ብቻ ለመፍታት ተሳትፈዋል። ውድድሩ ለብዙ ሰዓታት ወይም ለአንድ ሳምንት ሳይሆን ለብዙ ወራት እንደሚቆይ ልብ ሊባል ይገባል ። ቡድኖች ጽሑፎቹን ለማጥናት, የራሳቸውን ኦሪጅናል ሀሳብ ይዘው ለመምጣት እና ተግባራዊ ለማድረግ እድሉ አላቸው. በመሠረቱ, ይህ ውድድር የምርምር ፕሮጀክት ነው. በጣም ውጤታማ የመፍትሄ ሃሳቦች እና አሸናፊዎች ሽልማት ከጉባኤው ጋር በመተባበር ይካሄዳሉ አይ.ፒ.አይ. (አለምአቀፍ ሲምፖዚየም በፓራሜትሪዝድ እና ትክክለኛ ስሌት) በአውሮፓ ትልቁ ዓመታዊ የአልጎሪዝም ስብሰባ አካል ሆኖ ALGO. ስለ ውድድሩ ራሱ የበለጠ ዝርዝር መረጃ በ ላይ ይገኛል። ጣቢያ, እና ያለፉት ዓመታት ውጤቶች ውሸት ናቸው እዚህ.

የመፍትሄው ንድፍ

የቬርቴክስ መሸፈኛ ችግርን ለመፍታት, parameterized ስልተ ቀመሮችን ለመጠቀም ሞከርኩ. እነሱ በተለምዶ ሁለት ክፍሎችን ያቀፈ ነው-የማቅለል ህጎች (በጥሩ ሁኔታ ወደ ከርነልነት የሚመሩ) እና የመከፋፈል ህጎች። የማቅለል ህጎች በፖሊኖሚል ጊዜ ውስጥ የመግቢያውን ቅድመ-ሂደት ናቸው። እንደነዚህ ያሉትን ደንቦች የመተግበር ዓላማ ችግሩን ወደ ተመጣጣኝ አነስተኛ ችግር ለመቀነስ ነው. የማቅለል ደንቦች የአልጎሪዝም በጣም ውድ ክፍል ናቸው, እና ይህን ክፍል መተግበር ወደ አጠቃላይ የሩጫ ጊዜ ይመራል ከቀላል ፖሊኖሚል ጊዜ ይልቅ። በእኛ ሁኔታ, የመከፋፈያ ደንቦች በእያንዳንዱ ጫፍ ላይ ወይም ጎረቤቱን እንደ መልስ መውሰድ ያስፈልግዎታል በሚለው እውነታ ላይ የተመሰረተ ነው.

አጠቃላይ መርሃግብሩ ይህ ነው-የማቅለል ደንቦችን እንተገብራለን, ከዚያም የተወሰነውን ጫፍ እንመርጣለን እና ሁለት ተደጋጋሚ ጥሪዎችን እናደርጋለን-በመጀመሪያው ምላሽ እንወስዳለን, በሌላኛው ደግሞ ሁሉንም ጎረቤቶቹን እንወስዳለን. በዚህ አከርካሪ ላይ መሰንጠቅ (ቅርንጫፍ) የምንለው ይህ ነው።

በትክክል አንድ ተጨማሪ በዚህ እቅድ በሚቀጥለው አንቀጽ ላይ ይደረጋል.

የመከፋፈያ (ብሩሽ) ደንቦች ሀሳቦች

መከፋፈሉ የሚፈጠርበትን ጫፍ እንዴት እንደሚመርጡ እንወያይ።
ዋናው ሃሳብ በአልጎሪዝም መልኩ በጣም ስግብግብ ነው፡ የከፍተኛውን ዲግሪ ጫፍ ወስደን እንከፋፍለው። ለምን የተሻለ ይመስላል? ምክንያቱም በሁለተኛው የድግግሞሽ ጥሪ ቅርንጫፍ ውስጥ በዚህ መንገድ ብዙ ጫፎችን እናስወግዳለን. በቀሪው ትንሽ ግራፍ ላይ መቁጠር ይችላሉ እና በፍጥነት ልንሰራበት እንችላለን.

ይህ አካሄድ ቀደም ሲል ከተነጋገርነው ቀላል የከርነልላይዜሽን ቴክኒኮች ጋር ራሱን በጥሩ ሁኔታ ያሳየናል እና በመጠን መጠናቸው የበርካታ ሺህ ጫፎችን አንዳንድ ሙከራዎችን ይፈታል። ነገር ግን, ለምሳሌ, ለክዩቢክ ግራፎች (ይህም የእያንዳንዱ ጫፍ ደረጃ ሶስት ዲግሪ ያላቸው ግራፎች) ጥሩ አይሰራም.
በቀላል ቀላል ሀሳብ ላይ የተመሠረተ ሌላ ሀሳብ አለ-ግራፉ ከተቋረጠ ፣ በተያያዙት ክፍሎቹ ላይ ያለው ችግር በመጨረሻው ላይ መልሶቹን በማጣመር በተናጥል ሊፈታ ይችላል። ይህ በነገራችን ላይ በእቅዱ ውስጥ ትንሽ የተስፋ ቃል ማሻሻያ ነው ፣ ይህም መፍትሄውን በከፍተኛ ሁኔታ ያፋጥናል-ቀደም ሲል ፣ በዚህ ሁኔታ ፣ የክፍለ-ነገሮችን ምላሾች ለማስላት ለዘመናት ምርት እንሰራለን ፣ አሁን ግን እንሰራለን ። ድምር. እና ቅርንጫፉን ለማፋጠን የተገናኘውን ግራፍ ወደ ተቋረጠ መለወጥ ያስፈልግዎታል።

እንዴት ማድረግ ይቻላል? በግራፉ ውስጥ የንግግር ነጥብ ካለ, በእሱ ላይ መዋጋት ያስፈልግዎታል. የሥዕል ነጥብ ነጥብ (vertex) ሲሆን ይህም ሲወገድ ግራፉ ግንኙነቱን ያጣል። በግራፍ ውስጥ ያሉ ሁሉም የማገናኛ ነጥቦች በመስመር ጊዜ ውስጥ ክላሲካል አልጎሪዝምን በመጠቀም ሊገኙ ይችላሉ። ይህ አቀራረብ የቅርንጫፍ ክፍሎችን በከፍተኛ ሁኔታ ያፋጥናል.

ከተመረጡት ጫፎች ውስጥ ማንኛቸውም ሲወገዱ ግራፉ ወደ ተያያዥ ክፍሎች ይከፈላል.

ይህንን እናደርጋለን, ግን የበለጠ እንፈልጋለን. ለምሳሌ ፣ በግራፉ ውስጥ ትናንሽ የአከርካሪ መቁረጫዎችን ይፈልጉ እና ከሱ ጫፎች ጋር ይከፋፈሉ ። ዝቅተኛውን አለም አቀፋዊ የቬርቴክስ መቁረጥን ለማግኘት የማውቀው በጣም ቀልጣፋ መንገድ በኪዩቢክ ጊዜ የተሰራውን የጎሞሪ-ሁ ዛፍ መጠቀም ነው። በPACE ፈተና፣ የተለመደው የግራፍ መጠን ብዙ ሺህ ጫፎች ነው። በዚህ ሁኔታ በቢሊዮኖች የሚቆጠሩ ክዋኔዎች በእያንዳንዱ የእንደገና ዛፍ ጫፍ ላይ መደረግ አለባቸው. በተመደበው ጊዜ ውስጥ ችግሩን ለመፍታት በቀላሉ የማይቻል ነው ።

መፍትሄውን ለማመቻቸት እንሞክር. በጥንድ ጫፎች መካከል ያለው ዝቅተኛው ጫፍ ከፍተኛ ፍሰት በሚገነባ በማንኛውም ስልተ ቀመር ሊገኝ ይችላል። እንዲህ ባለው አውታረ መረብ ላይ እንዲገባ መፍቀድ ትችላለህ Dinitz አልጎሪዝም, በተግባር በጣም በፍጥነት ይሰራል. ለቀዶ ጥገና ጊዜ ግምትን ማረጋገጥ በንድፈ ሀሳብ ይቻላል የሚል ጥርጣሬ አለኝ , ይህም ቀድሞውኑ ተቀባይነት ያለው ነው.

በጥንድ የዘፈቀደ ጫፎች መካከል መቆራረጥን ለመፈለግ እና በጣም ሚዛናዊ የሆነውን ለመውሰድ ብዙ ጊዜ ሞከርኩ። እንደ አለመታደል ሆኖ ይህ በክፍት የPACE ፈተና ሙከራ ላይ ደካማ ውጤቶችን አስገኝቷል። ከፍተኛውን የዲግሪ ጫፎችን ከሚከፋፈለው ስልተ ቀመር ጋር አነጻጽሬዋለሁ፣ ይህም የቁልቁለት ጥልቀት ላይ ካለው ገደብ ጋር ነው። በዚህ መንገድ መቁረጥን ለማግኘት የሚሞክር አልጎሪዝም ትላልቅ ግራፎችን ትቶ ወጥቷል። ይህ የሆነበት ምክንያት ቁርጥራጮቹ በጣም ሚዛናዊ ያልሆኑ በመሆናቸው ነው-5-10 ጫፎችን ካስወገዱ በኋላ 15-20 ብቻ መከፋፈል ተችሏል ።

ስለ ንድፈ-ሀሳብ በጣም ፈጣን ስልተ ቀመሮች መጣጥፎች ለመከፋፈል ጫፎችን ለመምረጥ በጣም የላቀ ቴክኒኮችን እንደሚጠቀሙ ልብ ሊባል ይገባል። እንደነዚህ ያሉ ዘዴዎች በጣም ውስብስብ አተገባበር እና ብዙውን ጊዜ በጊዜ እና በማስታወስ ረገድ ደካማ አፈፃፀም አላቸው. ለልምምድ በጣም ተቀባይነት ያላቸውን መለየት አልቻልኩም።

የማቅለል ደንቦችን እንዴት እንደሚተገበሩ

አስቀድመን የከርነል ማድረጊያ ሃሳቦች አሉን። ላስታውስህ፡-

1. የተገለለ ጫፍ ካለ ይሰርዙት።
2. የዲግሪ 1 ጫፍ ካለ, ያስወግዱት እና ጎረቤቱን በምላሹ ይውሰዱ.
3. ቢያንስ የዲግሪ ወርድ ካለ ኪ + 1, መልሰህ ውሰደው.

በመጀመሪያዎቹ ሁለት ሁሉም ነገር ግልጽ ነው, ከሦስተኛው ጋር አንድ ብልሃት አለ. ስለ መጠጥ ቤት የኮሚክ ችግር ውስጥ ከሆነ ከፍተኛ ገደብ ተሰጥቶናል። k, ከዚያ በPACE ፈተና ውስጥ አነስተኛውን መጠን ያለው የወርድ ሽፋን ማግኘት ብቻ ያስፈልግዎታል። ይህ የተለመደ የፍለጋ ችግሮችን ወደ ውሳኔ ችግሮች መቀየር ነው፡ ብዙ ጊዜ በሁለቱ የችግሮች አይነቶች መካከል ምንም ልዩነት የለም። በተግባር፣ ለቬርቴክስ ሽፋን ችግር ፈቺ የምንጽፍ ከሆነ፣ ልዩነት ሊኖር ይችላል። ለምሳሌ, እንደ ሦስተኛው ነጥብ.

ከአተገባበር እይታ አንጻር ለመቀጠል ሁለት መንገዶች አሉ. የመጀመሪያው አቀራረብ ተደጋጋሚ ጥልቀት ይባላል. እንደሚከተለው ነው-በመልሱ ላይ ከአንዳንድ ምክንያታዊ እገዳዎች እንጀምራለን, ከዚያም ይህን ገደብ ተጠቅመን ስልተ-ቀመርያችንን ከላይ ለተሰጠው መልስ እንደ እገዳ, ከዚህ ገደብ ያነሰ ድግግሞሽ ሳንሄድ. የተወሰነ መልስ ካገኘን, ጥሩ እንደሚሆን የተረጋገጠ ነው, አለበለዚያ ይህንን ገደብ በአንድ ጨምር እና እንደገና መጀመር እንችላለን.

ሌላው አቀራረብ አንዳንድ የአሁኑን ምርጥ መልስ ማከማቸት እና ትንሽ መልስ መፈለግ ነው, ሲገኝ ይህን ግቤት መቀየር k በፍለጋ ውስጥ አላስፈላጊ ቅርንጫፎችን ለበለጠ መቁረጥ.

ብዙ የምሽት ሙከራዎችን ካደረግኩ በኋላ በእነዚህ ሁለት ዘዴዎች ጥምረት ላይ ወሰንኩ-በመጀመሪያ ፣ የእኔን ስልተ-ቀመር በፍለጋ ጥልቀት ላይ በተወሰነ ገደብ (ከዋናው መፍትሄ ጋር ሲነፃፀር ትንሽ ጊዜ እንዲወስድ መርጫለሁ) እና ምርጡን እጠቀማለሁ። ለመልሱ እንደ ከፍተኛ ገደብ የተገኘ መፍትሔ - ማለትም ለተመሳሳይ ነገር k.

የዲግሪ ጫፎች 2

ከዲግሪ 0 እና 1 ጫፎች ጋር ተነጋግረናል። ይህ በዲግሪ 2 ጫፎች ሊከናወን ይችላል ፣ ግን ይህ ከግራፉ የበለጠ ውስብስብ ስራዎችን ይፈልጋል ።

ይህንን ለማብራራት እንደምንም ጫፎችን መሰየም አለብን። የዲግሪ 2 ወርድ ወርድ እንበለው። v, እና ጎረቤቶቹ - ጫፎች x и y. በመቀጠል ሁለት ጉዳዮች ይኖሩናል.

1. መቼ x и y - ጎረቤቶች. ከዚያ መልስ መስጠት ይችላሉ x и yና v ሰርዝ። በእርግጥ ከዚህ ትሪያንግል ቢያንስ ሁለት ጫፎች በምላሹ መወሰድ አለባቸው ፣ እና በእርግጠኝነት ከወሰድን አንሸነፍም። x и y: ምናልባት ሌሎች ጎረቤቶች አሏቸው, እና v እነሱ አይደሉም.
2. መቼ x и y - ጎረቤቶች አይደሉም. ከዚያም ሶስቱም ጫፎች ወደ አንድ ሊጣበቁ እንደሚችሉ ይገለጻል. ሃሳቡ በዚህ ጉዳይ ላይ አንድ ጥሩ መልስ አለ, በዚህ ውስጥ አንዱን እንወስዳለን v, ወይም ሁለቱም ጫፎች x и y. ከዚህም በላይ በመጀመሪያው ሁኔታ ሁሉንም ጎረቤቶች በምላሹ መውሰድ አለብን x и y, ግን በሁለተኛው ውስጥ አስፈላጊ አይደለም. ይህ በምላሽ እና በምንሰራበት ጊዜ የተጣበቀውን ወርድ ካልወሰድንባቸው ጉዳዮች ጋር በትክክል ይዛመዳል። በሁለቱም ሁኔታዎች ከእንደዚህ አይነት ቀዶ ጥገና የሚሰጠው ምላሽ በአንድ እንደሚቀንስ ብቻ ልብ ሊባል ይገባል.

ይህ አካሄድ በትክክል በተመጣጣኝ የመስመር ጊዜ ውስጥ በትክክል መተግበር በጣም ከባድ መሆኑን ልብ ሊባል ይገባል። የማጣበጃ ጫፎች ውስብስብ አሠራር ነው, የጎረቤቶችን ዝርዝሮች መቅዳት ያስፈልግዎታል. ይህ በግዴለሽነት ከተሰራ ፣በአሲምፕቲካል ዝቅተኛ የሩጫ ጊዜ (ለምሳሌ ፣ ከእያንዳንዱ ማጣበቂያ በኋላ ብዙ ጠርዞችን ከገለበጡ) ማጠናቀቅ ይችላሉ ። ከዲግሪ 2 ጫፎች ሙሉ ዱካዎችን ለማግኘት እና እንደ ከእንደዚህ ያሉ ጫፎች ወይም ከሁሉም እንደዚህ ካሉ ጫፎች ያሉ ዑደቶችን የመሰሉ ልዩ ጉዳዮችን ለመተንተን ወሰንኩ።

በተጨማሪም, ይህ ክዋኔ እንዲቀለበስ አስፈላጊ ነው, ስለዚህም ከተደጋጋሚ ሲመለሱ ግራፉን ወደ መጀመሪያው መልክ እንመልሰዋለን. ይህንን ለማረጋገጥ፣ የተቀላቀሉትን ጫፎች የጠርዝ ዝርዝሮችን አላጸዳሁም፣ ስለዚህ የትኛዎቹ ጠርዞች የት እንደሚሄዱ ብቻ አውቃለሁ። ይህ የግራፎች አተገባበርም ትክክለኛነትን ይጠይቃል፣ነገር ግን ፍትሃዊ የመስመር ጊዜን ይሰጣል። እና ለብዙ በአስር ሺዎች ለሚቆጠሩ ጠርዞች ግራፎች ፣ ወደ ፕሮሰሰር መሸጎጫ ውስጥ ይገባል ፣ ይህም በፍጥነት ውስጥ ትልቅ ጥቅሞችን ይሰጣል።

መስመራዊ ከርነል

በመጨረሻም ፣ በጣም አስደሳች የሆነው የከርነል ክፍል።

ለመጀመር ፣ በሁለትዮሽ ግራፎች ውስጥ ዝቅተኛው የወርድ ሽፋን በመጠቀም ሊገኝ እንደሚችል ያስታውሱ . ይህንን ለማድረግ አልጎሪዝምን መጠቀም ያስፈልግዎታል ሆፕክሮፍት-ካርፕ እዚያ ከፍተኛውን ተዛማጅ ለማግኘት እና ከዚያ ቲዎሪውን ይጠቀሙ ኮንግ-ኤገርቫሪ.

የመስመራዊ ከርነል ሀሳብ ይህ ነው-መጀመሪያ ግራፉን እንከፋፍለን ፣ ማለትም ከእያንዳንዱ ጫፍ ይልቅ v ሁለት ጫፎችን እንጨምር и , እና በእያንዳንዱ ጠርዝ ፋንታ u - v ሁለት የጎድን አጥንቶች እንጨምር и . የተገኘው ግራፍ የሁለትዮሽ ይሆናል. በውስጡ ያለውን ዝቅተኛውን የቬርቴክ ሽፋን እናገኝ. የዋናው ግራፍ አንዳንድ ጫፎች ሁለት ጊዜ፣ አንዳንዶቹ አንድ ጊዜ ብቻ፣ እና አንዳንዶቹ በጭራሽ አይደርሱም። የ Nemhauser-Trotter ቲዎሬም በዚህ ሁኔታ አንድ ሰው አንድ ጊዜ እንኳን ያልመታ ጫፎችን በማንሳት ሁለት ጊዜ የተጎዱትን መልሶ ሊወስድ ይችላል ይላል። ከዚህም በላይ ከቀሪዎቹ ጫፎች (አንድ ጊዜ የሚመታ) ቢያንስ ግማሹን እንደ መልስ መውሰድ እንዳለቦት ትናገራለች.

አሁን ከዚህ በላይ መተውን ተምረናል። 2k ጫፎች በእርግጥ ፣ የቀረው መልስ ከሁሉም ጫፎች ውስጥ ቢያንስ ግማሽ ከሆነ ፣ ከዚያ በጠቅላላው ምንም ተጨማሪ ጫፎች የሉም። 2k.

እዚህ ትንሽ እርምጃ ወደፊት መሄድ ችያለሁ። በዚህ መንገድ የተገነባው ከርነል በሁለትዮሽ ግራፍ ውስጥ ምን ዓይነት ዝቅተኛ የቬርቴክ ሽፋን እንደወሰድን ይወሰናል. የተቀሩት ጫፎች ብዛት አነስተኛ እንዲሆን አንዱን መውሰድ እፈልጋለሁ። ከዚህ በፊት ይህንን ማድረግ የሚችሉት በጊዜ ውስጥ ብቻ ነበር . በጊዜው የዚህ ስልተ ቀመር አተገባበር አወጣሁ , ስለዚህ, ይህ እምብርት በእያንዳንዱ የቅርንጫፍ ደረጃ በመቶ ሺዎች የሚቆጠሩ ጫፎች በግራፎች ውስጥ መፈለግ ይቻላል.

ውጤት

ልምምድ እንደሚያሳየው የእኔ መፍትሔ በብዙ መቶ ጫፎች እና በብዙ ሺህ ጫፎች ላይ በጥሩ ሁኔታ ይሰራል። በእንደዚህ ዓይነት ሙከራዎች ውስጥ በግማሽ ሰዓት ውስጥ መፍትሄ እንደሚገኝ መጠበቅ በጣም ይቻላል. ተቀባይነት ባለው ጊዜ ውስጥ መልስ የማግኘት እድሉ, በመርህ ደረጃ, ግራፉ በቂ የሆነ ከፍተኛ የከፍተኛ ደረጃ ጫፎች ካሉት, ለምሳሌ, ዲግሪ 10 እና ከዚያ በላይ ከሆነ.

በውድድሩ ለመሳተፍ መፍትሄዎች መላክ ነበረባቸው optil.io. እዚያ በቀረበው መረጃ በመመዘን ምልክት፣ በክፍት ፈተናዎች ውስጥ የእኔ መፍትሄ ከሃያ ሶስተኛውን ደረጃ ይይዛል ፣ ከሴኮንድ ትልቅ ክፍተት ጋር። ሙሉ በሙሉ እውነቱን ለመናገር በውድድሩ በራሱ የመፍትሄ ሃሳቦች እንዴት እንደሚገመገሙ ሙሉ በሙሉ ግልጽ አይደለም፡ ለምሳሌ የእኔ መፍትሄ በአራተኛ ደረጃ ከመፍትሔው ያነሱ ፈተናዎችን ያልፋል፣ በሚያልፉት ላይ ግን በፍጥነት ይሰራል።

የተዘጉ ፈተናዎች ውጤቶች በጁላይ XNUMX ላይ ይታወቃሉ.

ምንጭ: hab.com