د څیړنې کار شاید زموږ د روزنې ترټولو زړه پورې برخه وي. نظر دا دی چې خپل ځان په خپل ټاکل شوي لوري کې هڅه وکړئ پداسې حال کې چې لاهم په پوهنتون کې یاست. د مثال په توګه ، د سافټویر انجینرۍ او ماشین زده کړې برخو زده کونکي اکثرا په شرکتونو کې د څیړنې لپاره ځي (په عمده ډول JetBrains یا Yandex ، مګر نه یوازې).
پدې پوسټ کې به زه د کمپیوټر ساینس کې زما د پروژې په اړه وغږیږم. زما د کار د یوې برخې په توګه، ما د یوې خورا مشهور NP-سخت ستونزو د حل کولو لپاره طریقې مطالعه کړې او عملي کړي: د عمودی پوښ کولو ستونزه.
نن ورځ، د NP-سخت ستونزو لپاره په زړه پورې طریقه په چټکۍ سره وده کوي - parameterized algorithms. زه به هڅه وکړم چې تاسو سرعت ته ورسوم، تاسو ته ځینې ساده پیرامیټریز شوي الګوریتمونه ووایم او یو پیاوړی میتود تشریح کړم چې زما سره ډیره مرسته وکړه. ما خپلې پایلې د 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 - ځینې پیرامیټرونه، کوم چې، احتمال لري، د ستونزې د اندازې په پرتله خورا کوچنی وي.
د دې الګوریتم څخه وړاندې ټول استدلال یو مثال وړاندې کوي kernelization د پیرامیټریز شوي الګوریتمونو رامینځته کولو لپاره یو له عمومي تخنیکونو څخه دی. Kernelization د یوې پیرامیټر د فعالیت لخوا محدود ارزښت ته د ستونزې اندازې کمول دي. پایله شوې ستونزه اکثرا د کرنل په نوم یادیږي. په دې توګه، د عمودی درجو په اړه د ساده استدلال په واسطه، موږ د Vertex Cover ستونزې لپاره څلور اړخیز کرنل ترلاسه کړ، د ځواب د اندازې سره سم پیرامیټ شوی. نور ترتیبات شتون لري چې تاسو یې د دې دندې لپاره غوره کولی شئ (لکه د 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 درجې او لوړ.
په سیالۍ کې د ګډون لپاره، حلونه باید واستول شي . هلته د وړاندې شوي معلوماتو له مخې قضاوت ، زما حل په خلاص ازموینو کې له شلو څخه دریم ځای لري ، له دوهم څخه لوی تشې سره. په بشپړ ډول صادق اوسئ ، دا په بشپړ ډول روښانه نده چې حلونه به پخپله سیالۍ کې څنګه ارزول کیږي: د مثال په توګه ، زما حل په څلورم ځای کې د حل په پرتله لږ ازموینې تیریږي ، مګر په هغه چا چې تیریږي ، دا ګړندي کار کوي.
د تړلو ازموینو پایلې به د جولای په لومړۍ نیټه معلومه شي.
سرچینه: www.habr.com