প্যারামিটারাইজড অ্যালগরিদমগুলির সাথে NP-হার্ড সমস্যাগুলি কীভাবে সমাধান করবেন

গবেষণার কাজ সম্ভবত আমাদের প্রশিক্ষণের সবচেয়ে আকর্ষণীয় অংশ। ধারণাটি হল বিশ্ববিদ্যালয়ে থাকাকালীন আপনার নির্বাচিত দিক থেকে নিজেকে চেষ্টা করা। উদাহরণস্বরূপ, সফ্টওয়্যার ইঞ্জিনিয়ারিং এবং মেশিন লার্নিং এর ছাত্ররা প্রায়শই কোম্পানিগুলিতে গবেষণা করতে যায় (প্রধানত জেটব্রেইন বা ইয়ানডেক্স, তবে কেবল নয়)।

এই পোস্টে আমি কম্পিউটার বিজ্ঞানে আমার প্রকল্প সম্পর্কে কথা বলব। আমার কাজের অংশ হিসাবে, আমি সবচেয়ে বিখ্যাত NP-হার্ড সমস্যাগুলির একটি সমাধানের জন্য অধ্যয়ন করেছি এবং অনুশীলন করেছি: শীর্ষবিন্দু আবরণ সমস্যা.

আজকাল, এনপি-হার্ড সমস্যার একটি আকর্ষণীয় পদ্ধতি খুব দ্রুত বিকাশ করছে - প্যারামিটারাইজড অ্যালগরিদম। আমি আপনাকে গতিতে নিয়ে যাওয়ার চেষ্টা করব, আপনাকে কিছু সাধারণ প্যারামিটারাইজড অ্যালগরিদম বলব এবং একটি শক্তিশালী পদ্ধতি বর্ণনা করব যা আমাকে অনেক সাহায্য করেছে। আমি PACE চ্যালেঞ্জ প্রতিযোগিতায় আমার ফলাফল উপস্থাপন করেছি: উন্মুক্ত পরীক্ষার ফলাফল অনুসারে, আমার সমাধানটি তৃতীয় স্থানে রয়েছে এবং চূড়ান্ত ফলাফল 1 জুলাই জানা যাবে।

আমার সম্পর্কে

আমার নাম ভ্যাসিলি আলফেরভ, আমি এখন ন্যাশনাল রিসার্চ ইউনিভার্সিটি হায়ার স্কুল অফ ইকোনমিক্স - সেন্ট পিটার্সবার্গে আমার তৃতীয় বর্ষ শেষ করছি। আমি আমার স্কুলের দিন থেকেই অ্যালগরিদমের প্রতি আগ্রহী ছিলাম, যখন আমি মস্কোর স্কুল নং 179 এ পড়াশোনা করেছি এবং সফলভাবে কম্পিউটার সায়েন্স অলিম্পিয়াডে অংশগ্রহণ করেছি।

প্যারামিটারাইজড অ্যালগরিদমের সীমিত সংখ্যক বিশেষজ্ঞ বারে প্রবেশ করেন...

বই থেকে নেওয়া উদাহরণ "প্যারামিটারাইজড অ্যালগরিদম"

কল্পনা করুন যে আপনি একটি ছোট শহরে একজন বারের নিরাপত্তা প্রহরী। প্রতি শুক্রবার, অর্ধেক শহর আপনার বারে বিশ্রাম নিতে আসে, যা আপনাকে অনেক কষ্ট দেয়: মারামারি প্রতিরোধ করার জন্য আপনাকে উত্তেজিত গ্রাহকদের বার থেকে বের করে দিতে হবে। অবশেষে, আপনি বিরক্ত হন এবং প্রতিরোধমূলক ব্যবস্থা নেওয়ার সিদ্ধান্ত নেন।

যেহেতু আপনার শহরটি ছোট, আপনি ঠিক জানেন যে কোন জোড়া পৃষ্ঠপোষকরা একসাথে একটি বারে শেষ হলে লড়াই করতে পারে। আপনি একটি তালিকা আছে n যারা আজ রাতে বারে আসবেন। আপনি কাউকে লড়াই না করেই কিছু নগরবাসীকে বার থেকে দূরে রাখার সিদ্ধান্ত নেন। একই সময়ে, আপনার কর্তারা লাভ হারাতে চান না এবং আপনি যদি এর বেশি না দেন তবে অসন্তুষ্ট হবেন k মানুষ।

দুর্ভাগ্যবশত, আপনার সামনে সমস্যাটি একটি ক্লাসিক NP-হার্ড সমস্যা। আপনি তাকে চিনতে পারেন ভার্টেক্স কভার, অথবা একটি শীর্ষবিন্দু আচ্ছাদন সমস্যা হিসাবে. এই ধরনের সমস্যার জন্য, সাধারণ ক্ষেত্রে, গ্রহণযোগ্য সময়ে কাজ করে এমন কোনো অ্যালগরিদম নেই। সুনির্দিষ্টভাবে বলতে গেলে, অপ্রমাণিত এবং বেশ শক্তিশালী হাইপোথিসিস ETH (Exponential Time Hypothesis) বলে যে এই সমস্যাটি সময়মতো সমাধান করা যাবে না , অর্থাৎ, আপনি সম্পূর্ণ অনুসন্ধানের চেয়ে লক্ষণীয়ভাবে ভাল কিছু ভাবতে পারবেন না। উদাহরণস্বরূপ, ধরা যাক কেউ আপনার বারে আসতে চলেছে n = 1000 মানব. তাহলে সম্পূর্ণ অনুসন্ধান হবে প্রায় আছে যে অপশন - পাগল পরিমাণ। ভাগ্যক্রমে, আপনার ব্যবস্থাপনা আপনাকে একটি সীমা দিয়েছে কে = 10, তাই আপনার পুনরাবৃত্তি করার জন্য সংমিশ্রণের সংখ্যা অনেক কম: দশটি উপাদানের উপসেটের সংখ্যা হল . এটি আরও ভাল, তবে এটি এখনও একটি শক্তিশালী ক্লাস্টারেও এক দিনে গণনা করা হবে না।

বারের দর্শকদের মধ্যে টানাপোড়েন সম্পর্কের এই কনফিগারেশনে লড়াইয়ের সম্ভাবনা দূর করতে, আপনাকে বব, ড্যানিয়েল এবং ফেডরকে বাইরে রাখতে হবে। এমন কোনো সমাধান নেই যেখানে শুধু দুজনকে পেছনে ফেলে রাখা হবে।

এর মানে কি এখনই সময় দেওয়া এবং সবাইকে ঢুকতে দেওয়া? আসুন অন্যান্য বিকল্প বিবেচনা করা যাক। ঠিক আছে, উদাহরণস্বরূপ, আপনি কেবল তাদেরই প্রবেশ করতে দিতে পারবেন না যারা খুব বড় সংখ্যক লোকের সাথে লড়াই করার সম্ভাবনা রয়েছে। যদি কারো সাথে অন্তত লড়াই করা যায় k+1 অন্য ব্যক্তি, তাহলে আপনি অবশ্যই তাকে প্রবেশ করতে দিতে পারবেন না - অন্যথায় আপনাকে সবাইকে বাইরে রাখতে হবে k+1 শহরবাসী, যাদের সাথে তিনি লড়াই করতে পারেন, যা অবশ্যই নেতৃত্বকে বিচলিত করবে।

এই নীতি অনুসারে আপনি যা করতে পারেন সবাইকে তাড়িয়ে দিতে দিন। তখন আর সবাই লড়তে পারবে না k মানুষ তাদের ছুড়ে ফেলে দিচ্ছে k মানুষ, আপনি এর চেয়ে বেশি কিছু আটকাতে পারবেন না দ্বন্দ্ব এর মানে বেশি হলে যদি একজন ব্যক্তি অন্তত একটি সংঘাতে জড়িত থাকে, তাহলে আপনি অবশ্যই তাদের সবাইকে আটকাতে পারবেন না। যেহেতু, অবশ্যই, আপনি অবশ্যই সম্পূর্ণরূপে অ-সংঘাতহীন লোকেদের অনুমতি দেবেন, আপনাকে দুইশ জনের মধ্যে দশটি আকারের সমস্ত উপসেটের মধ্য দিয়ে যেতে হবে। আছে প্রায় , এবং অপারেশনের এই সংখ্যা ইতিমধ্যে ক্লাস্টারে বাছাই করা যেতে পারে।

আপনি যদি এমন ব্যক্তিদের নিরাপদে নিতে পারেন যাদের কোনও বিরোধ নেই, তবে যারা শুধুমাত্র একটি সংঘর্ষে অংশ নেয় তাদের কী হবে? আসলে, তাদের প্রতিপক্ষের দরজা বন্ধ করেও তাদের প্রবেশ করানো যেতে পারে। প্রকৃতপক্ষে, যদি অ্যালিস শুধুমাত্র ববের সাথে দ্বন্দ্বে থাকে, তাহলে আমরা যদি তাদের দুজনের মধ্যে অ্যালিসকে ছেড়ে দিই, তাহলে আমরা হারব না: ববের অন্যান্য দ্বন্দ্ব থাকতে পারে, কিন্তু অ্যালিসের অবশ্যই সেগুলি নেই। তদুপরি, আমাদের উভয়কে প্রবেশ করতে না দেওয়ার আমাদের পক্ষে কোনও অর্থ নেই। এই ধরনের অপারেশন পরে আর কোন অবশিষ্ট থাকে একটি অমীমাংসিত ভাগ্য সঙ্গে গেস্ট: আমরা শুধুমাত্র আছে দ্বন্দ্ব, প্রত্যেকে দুইজন অংশগ্রহণকারী এবং প্রত্যেকে অন্তত দুইজনে জড়িত। তাই বাকি সব মাধ্যমে বাছাই করা হয় বিকল্প, যা সহজেই একটি ল্যাপটপে অর্ধেক দিন বিবেচনা করা যেতে পারে।

আসলে, সহজ যুক্তি দিয়ে আপনি আরও বেশি আকর্ষণীয় শর্ত অর্জন করতে পারেন। মনে রাখবেন যে আমাদের অবশ্যই সমস্ত বিরোধের সমাধান করতে হবে, অর্থাৎ, প্রতিটি বিবাদমান জুটি থেকে, অন্তত একজনকে বেছে নিন যাকে আমরা প্রবেশ করতে দেব না। আসুন নিম্নলিখিত অ্যালগরিদমটি বিবেচনা করি: যে কোনও দ্বন্দ্ব নিন, যেখান থেকে আমরা একটি অংশগ্রহণকারীকে সরিয়ে ফেলি এবং বাকি থেকে পুনরাবৃত্তিমূলকভাবে শুরু করি, তারপর অন্যটিকে সরিয়ে ফেলি এবং পুনরাবৃত্তিমূলকভাবে শুরু করি। যেহেতু আমরা প্রত্যেক ধাপে কাউকে বের করে দিই, তাই এই ধরনের অ্যালগরিদমের রিকারশন ট্রি হল গভীরতার বাইনারি ট্রি k, তাই মোট অ্যালগরিদম কাজ করে যেখানে n শীর্ষবিন্দু সংখ্যা, এবং m - পাঁজরের সংখ্যা। আমাদের উদাহরণে, এটি প্রায় দশ মিলিয়ন, যা শুধুমাত্র একটি ল্যাপটপে নয়, এমনকি একটি মোবাইল ফোনেও একটি বিভক্ত সেকেন্ডে গণনা করা যেতে পারে।

উপরের উদাহরণটি একটি উদাহরণ প্যারামিটারাইজড অ্যালগরিদম. প্যারামিটারাইজড অ্যালগরিদম হল অ্যালগরিদম যা সময়ের মধ্যে চলে f(k) পলি(n)যেখানে p - বহুপদ, f একটি নির্বিচারে গণনাযোগ্য ফাংশন, এবং k - কিছু প্যারামিটার, যা, সম্ভবত, সমস্যার আকারের তুলনায় অনেক ছোট হবে।

এই অ্যালগরিদমের আগে সমস্ত যুক্তি একটি উদাহরণ দেয় কার্নেলাইজেশন প্যারামিটারাইজড অ্যালগরিদম তৈরির সাধারণ কৌশলগুলির মধ্যে একটি। কার্নেলাইজেশন হল একটি প্যারামিটারের ফাংশন দ্বারা সীমিত একটি মান পর্যন্ত সমস্যার আকার হ্রাস করা। ফলস্বরূপ সমস্যাটিকে প্রায়শই কার্নেল বলা হয়। এইভাবে, শীর্ষবিন্দুর ডিগ্রী সম্পর্কে সহজ যুক্তির দ্বারা, আমরা উত্তরের আকার দ্বারা পরামিতিকৃত ভার্টেক্স কভার সমস্যার জন্য একটি দ্বিঘাত কার্নেল পেয়েছি। এই কাজের জন্য আপনি বেছে নিতে পারেন এমন অন্যান্য সেটিংস রয়েছে (যেমন LP এর উপরে ভার্টেক্স কভার), কিন্তু এটি সেই সেটিং যা আমরা আলোচনা করব।

পেস চ্যালেঞ্জ

প্রতিযোগিতা PACE চ্যালেঞ্জ (The Parameterized Algorithms and Computational Experiments Challenge) 2015 সালে কম্পিউটেশনাল সমস্যা সমাধানের জন্য প্যারামিটারাইজড অ্যালগরিদম এবং অনুশীলনে ব্যবহৃত পন্থাগুলির মধ্যে একটি সংযোগ স্থাপনের জন্য জন্মগ্রহণ করেছিল। প্রথম তিনটি প্রতিযোগিতা একটি গ্রাফের গাছের প্রস্থ খুঁজে বের করার জন্য নিবেদিত ছিল (গাছের প্রস্থ), একটি স্টেইনার গাছের সন্ধান করা হচ্ছে (স্টেইনার গাছ) এবং চক্কর কাটা (ফিডব্যাক ভার্টেক্স সেট) এই বছর, আপনি যে সমস্যাগুলিতে হাত দিয়ে চেষ্টা করতে পারেন তার মধ্যে একটি হল উপরে বর্ণিত শীর্ষবিন্দু আবরণ সমস্যা।

প্রতি বছর প্রতিযোগিতাটি জনপ্রিয়তা পাচ্ছে। আপনি যদি প্রাথমিক তথ্য বিশ্বাস করেন, এই বছর 24 টি দল একাই শীর্ষস্থান কভারিং সমস্যা সমাধানের জন্য প্রতিযোগিতায় অংশ নিয়েছিল। এটি লক্ষণীয় যে প্রতিযোগিতাটি কয়েক ঘন্টা বা এমনকি এক সপ্তাহ নয়, কয়েক মাস স্থায়ী হয়। দলগুলি সাহিত্য অধ্যয়ন করার সুযোগ পায়, তাদের নিজস্ব মূল ধারণা নিয়ে আসে এবং এটি বাস্তবায়নের চেষ্টা করে। সংক্ষেপে, এই প্রতিযোগিতাটি একটি গবেষণা প্রকল্প। সম্মেলনের সাথে একযোগে বিজয়ীদের সবচেয়ে কার্যকর সমাধান এবং পুরস্কার প্রদানের জন্য ধারনা করা হবে আইপিসি (আন্তর্জাতিক সিম্পোজিয়াম অন প্যারামিটারাইজড অ্যান্ড এক্সাক্ট কম্পিউটেশন) ইউরোপের বৃহত্তম বার্ষিক অ্যালগরিদমিক সভার অংশ হিসাবে ALGO. প্রতিযোগিতা সম্পর্কে আরও বিস্তারিত তথ্য এখানে পাওয়া যাবে ওয়েবসাইট, এবং আগের বছরের ফলাফল মিথ্যা এখানে.

সমাধান চিত্র

শীর্ষবিন্দু কভারিং সমস্যা সমাধানের জন্য, আমি প্যারামিটারাইজড অ্যালগরিদম ব্যবহার করার চেষ্টা করেছি। এগুলি সাধারণত দুটি অংশ নিয়ে গঠিত: সরলীকরণ নিয়ম (যা আদর্শভাবে কার্নেলাইজেশনের দিকে পরিচালিত করে) এবং বিভক্ত করার নিয়ম। সরলীকরণ নিয়ম হল বহুপদী সময়ে ইনপুট প্রিপ্রসেসিং। এই ধরনের নিয়ম প্রয়োগের উদ্দেশ্য হল সমস্যাটিকে একটি সমতুল্য ছোট সমস্যায় কমিয়ে আনা। সরলীকরণ নিয়মগুলি অ্যালগরিদমের সবচেয়ে ব্যয়বহুল অংশ, এবং এই অংশটি প্রয়োগ করা মোট চলমান সময়কে নিয়ে যায় সহজ বহুপদী সময়ের পরিবর্তে। আমাদের ক্ষেত্রে, বিভক্ত করার নিয়মগুলি এই সত্যের উপর ভিত্তি করে যে প্রতিটি শীর্ষের জন্য আপনাকে এটি বা এর প্রতিবেশীকে উত্তর হিসাবে নিতে হবে।

সাধারণ স্কিমটি হল: আমরা সরলীকরণের নিয়মগুলি প্রয়োগ করি, তারপরে আমরা কিছু শিরোনাম নির্বাচন করি এবং দুটি পুনরাবৃত্তিমূলক কল করি: প্রথমটিতে আমরা এটিকে প্রতিক্রিয়া হিসাবে গ্রহণ করি এবং অন্যটিতে আমরা এর সমস্ত প্রতিবেশীকে গ্রহণ করি। একে আমরা এই শীর্ষবিন্দু বরাবর বিভাজন (শাখা) বলি।

পরবর্তী অনুচ্ছেদে এই স্কিমটিতে ঠিক একটি সংযোজন করা হবে।

বিভক্ত করার জন্য ধারণা (ব্রঞ্চিং) নিয়ম

আসুন আলোচনা করা যাক কিভাবে একটি শীর্ষবিন্দু নির্বাচন করবেন যার সাথে বিভাজন ঘটবে।
মূল ধারণাটি অ্যালগরিদমিক অর্থে খুব লোভী: আসুন সর্বোচ্চ ডিগ্রীর একটি শীর্ষবিন্দু নিন এবং এটি বরাবর বিভক্ত করি। কেন এটা ভাল মনে হচ্ছে? কারণ রিকার্সিভ কলের দ্বিতীয় শাখায় আমরা এভাবে অনেকগুলো শীর্ষবিন্দু মুছে ফেলব। আপনি অবশিষ্ট একটি ছোট গ্রাফের উপর নির্ভর করতে পারেন এবং আমরা এটিতে দ্রুত কাজ করতে পারি।

এই পদ্ধতিটি, ইতিমধ্যে আলোচিত সহজ কার্নেলাইজেশন কৌশলগুলির সাথে, নিজেকে ভালভাবে দেখায় এবং আকারে কয়েক হাজার শীর্ষবিন্দুর কিছু পরীক্ষা সমাধান করে। কিন্তু, উদাহরণস্বরূপ, এটি ঘন গ্রাফের জন্য ভাল কাজ করে না (অর্থাৎ, গ্রাফ যার প্রতিটি শীর্ষবিন্দুর ডিগ্রী তিনটি)।
একটি মোটামুটি সহজ ধারণার উপর ভিত্তি করে আরেকটি ধারণা রয়েছে: যদি গ্রাফটি সংযোগ বিচ্ছিন্ন হয়, তবে এর সংযুক্ত উপাদানগুলির সমস্যাটি স্বাধীনভাবে সমাধান করা যেতে পারে, শেষে উত্তরগুলি একত্রিত করে। এটি, যাইহোক, স্কিমের একটি ছোট প্রতিশ্রুত পরিবর্তন, যা উল্লেখযোগ্যভাবে সমাধানটিকে দ্রুততর করবে: পূর্বে, এই ক্ষেত্রে, আমরা উপাদানগুলির প্রতিক্রিয়া গণনা করার জন্য সময়ের পণ্যের জন্য কাজ করেছি, কিন্তু এখন আমরা কাজ করি যোগফল. এবং ব্রাঞ্চিংয়ের গতি বাড়ানোর জন্য, আপনাকে একটি সংযুক্ত গ্রাফটিকে একটি সংযোগ বিচ্ছিন্ন গ্রাফে পরিণত করতে হবে।

এটা কিভাবে করতে হবে? যদি গ্রাফে একটি উচ্চারণ বিন্দু থাকে তবে আপনাকে এটিতে লড়াই করতে হবে। একটি উচ্চারণ বিন্দু হল এমন একটি শীর্ষবিন্দু যা সরানো হলে গ্রাফটি তার সংযোগ হারায়। একটি গ্রাফের সমস্ত জংশন পয়েন্টগুলি রৈখিক সময়ে ক্লাসিক্যাল অ্যালগরিদম ব্যবহার করে পাওয়া যেতে পারে। এই পদ্ধতি উল্লেখযোগ্যভাবে শাখা বৃদ্ধির গতি বাড়ায়।

যখন নির্বাচিত শীর্ষবিন্দুগুলি সরানো হয়, গ্রাফটি সংযুক্ত উপাদানগুলিতে বিভক্ত হবে।

আমরা এটি করব, তবে আমরা আরও চাই। উদাহরণস্বরূপ, গ্রাফে ছোট শীর্ষবিন্দুর কাটগুলি দেখুন এবং এটি থেকে শীর্ষবিন্দু বরাবর বিভক্ত করুন। ন্যূনতম গ্লোবাল ভার্টেক্স কাটা খুঁজে বের করার সবচেয়ে কার্যকর উপায় হল একটি গোমোরি-হু গাছ ব্যবহার করা, যা ঘন সময়ে নির্মিত। PACE চ্যালেঞ্জে, সাধারণ গ্রাফের আকার কয়েক হাজার শীর্ষবিন্দু। এই পরিস্থিতিতে, পুনরাবৃত্তি গাছের প্রতিটি শীর্ষে কোটি কোটি অপারেশন করতে হবে। দেখা যাচ্ছে যে বরাদ্দকৃত সময়ে সমস্যার সমাধান করা অসম্ভব।

এর সমাধান অপ্টিমাইজ করার চেষ্টা করা যাক. এক জোড়া শীর্ষবিন্দুর মধ্যে ন্যূনতম শীর্ষবিন্দু কাটা যে কোনো অ্যালগরিদম দ্বারা পাওয়া যেতে পারে যা সর্বাধিক প্রবাহ তৈরি করে। আপনি যেমন একটি নেটওয়ার্ক সম্মুখের এটি দিতে পারেন ডিনিটজ অ্যালগরিদম, বাস্তবে এটি খুব দ্রুত কাজ করে। আমার সন্দেহ আছে যে অপারেটিং সময়ের জন্য একটি অনুমান প্রমাণ করা তাত্ত্বিকভাবে সম্ভব , যা ইতিমধ্যে বেশ গ্রহণযোগ্য।

আমি বেশ কয়েকবার চেষ্টা করেছি র্যান্ডম শীর্ষবিন্দুর জোড়ার মধ্যে কাটা দেখার জন্য এবং সবচেয়ে ভারসাম্যপূর্ণ একটি নিতে। দুর্ভাগ্যবশত, এটি উন্মুক্ত PACE চ্যালেঞ্জ পরীক্ষায় খারাপ ফলাফল তৈরি করেছে। আমি এটিকে একটি অ্যালগরিদমের সাথে তুলনা করেছি যা সর্বোচ্চ ডিগ্রির শীর্ষবিন্দুকে বিভক্ত করে, তাদের বংশোদ্ভূত গভীরতার সীমাবদ্ধতার সাথে চালায়। একটি অ্যালগরিদম এইভাবে একটি কাটা খুঁজে বের করার চেষ্টা করছে বড় গ্রাফগুলি পিছনে ফেলেছে৷ এটি এই কারণে যে কাটগুলি খুব ভারসাম্যহীন বলে প্রমাণিত হয়েছিল: 5-10 টি শীর্ষবিন্দু মুছে ফেলার পরে, শুধুমাত্র 15-20টি বিভক্ত করা সম্ভব হয়েছিল।

এটি লক্ষণীয় যে তাত্ত্বিকভাবে দ্রুততম অ্যালগরিদম সম্পর্কিত নিবন্ধগুলি বিভাজনের জন্য শীর্ষবিন্দু নির্বাচন করার জন্য আরও উন্নত কৌশল ব্যবহার করে। এই ধরনের কৌশলগুলির খুব জটিল বাস্তবায়ন এবং প্রায়ই সময় এবং মেমরির দিক থেকে দুর্বল কর্মক্ষমতা রয়েছে। যেগুলো অনুশীলনের জন্য বেশ গ্রহণযোগ্য সেগুলো আমি চিহ্নিত করতে পারিনি।

সরলীকরণ নিয়ম কিভাবে প্রয়োগ করবেন

আমরা ইতিমধ্যে কার্নেলাইজেশন জন্য ধারণা আছে. আমাকে আপনাকে মনে করিয়ে দিতে দিন:

1. যদি একটি বিচ্ছিন্ন শীর্ষবিন্দু আছে, এটি মুছে ফেলুন.
2. ডিগ্রি 1 এর একটি শীর্ষবিন্দু থাকলে, এটি সরিয়ে ফেলুন এবং প্রতিক্রিয়া হিসাবে তার প্রতিবেশীকে নিন।
3. অন্তত ডিগ্রির শীর্ষবিন্দু থাকলে k+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 এর শীর্ষবিন্দু থেকে সম্পূর্ণ পথ খুঁজে বের করতে এবং একগুচ্ছ বিশেষ ক্ষেত্রে বিশ্লেষণ করার বিষয়ে স্থির হয়েছি, যেমন এই ধরনের শীর্ষবিন্দু থেকে চক্র বা একটি ছাড়া এই ধরনের সমস্ত শীর্ষবিন্দু থেকে।

উপরন্তু, এটি প্রয়োজনীয় যে এই অপারেশনটি বিপরীত হতে পারে, যাতে পুনরাবৃত্তি থেকে ফিরে আসার সময় আমরা গ্রাফটিকে তার আসল আকারে পুনরুদ্ধার করি। এটি নিশ্চিত করার জন্য, আমি একত্রিত শীর্ষবিন্দুগুলির প্রান্ত তালিকাগুলি সাফ করিনি এবং তারপরে আমি জানতাম কোন প্রান্তগুলি কোথায় যেতে হবে। গ্রাফের এই বাস্তবায়নের জন্যও নির্ভুলতা প্রয়োজন, কিন্তু এটি ন্যায্য রৈখিক সময় প্রদান করে। এবং কয়েক হাজার প্রান্তের গ্রাফের জন্য, এটি প্রসেসর ক্যাশে ফিট করে, যা গতিতে দুর্দান্ত সুবিধা দেয়।

লিনিয়ার কার্নেল

অবশেষে, কার্নেলের সবচেয়ে আকর্ষণীয় অংশ।

শুরু করার জন্য, মনে রাখবেন যে দ্বিপক্ষীয় গ্রাফে ন্যূনতম শীর্ষবিন্দু কভারটি ব্যবহার করে পাওয়া যেতে পারে . এটি করার জন্য আপনাকে অ্যালগরিদম ব্যবহার করতে হবে হপক্রফট-কার্প সেখানে সর্বোচ্চ মিল খুঁজে পেতে এবং তারপর উপপাদ্যটি ব্যবহার করুন König-Egervari.

একটি রৈখিক কার্নেলের ধারণাটি হল: প্রথমে আমরা গ্রাফটিকে বিভক্ত করি, অর্থাৎ প্রতিটি শীর্ষবিন্দুর পরিবর্তে v এর দুটি শিখর যোগ করা যাক и এবং প্রতিটি প্রান্তের পরিবর্তে u - v এর দুটি পাঁজর যোগ করা যাক и . ফলস্বরূপ গ্রাফ দ্বিপক্ষীয় হবে। আসুন এটিতে ন্যূনতম শীর্ষবিন্দুর কভারটি খুঁজে বের করি। মূল গ্রাফের কিছু শিরোনাম সেখানে দুবার, কিছু শুধুমাত্র একবার, এবং কিছু কখনও না। Nemhauser-Trotter থিওরেম বলে যে এই ক্ষেত্রে কেউ এমন শীর্ষস্থানগুলি সরিয়ে ফেলতে পারে যেগুলি একবারও আঘাত করেনি এবং যেগুলিকে দুইবার আঘাত করেছিল তা ফিরিয়ে নিতে পারে। তদুপরি, তিনি বলেছেন যে অবশিষ্ট শীর্ষবিন্দুগুলির (যেগুলি একবার আঘাত করে) আপনাকে উত্তর হিসাবে কমপক্ষে অর্ধেক নিতে হবে।

আমরা সবেমাত্র ছেড়ে যেতে শিখেছি 2k চূড়া প্রকৃতপক্ষে, যদি অবশিষ্ট উত্তরটি সমস্ত শীর্ষবিন্দুর অন্তত অর্ধেক হয়, তাহলে মোট এর চেয়ে বেশি শীর্ষবিন্দু নেই 2k.

এখানে আমি একটি ছোট পদক্ষেপ এগিয়ে নিতে পেরেছি। এটা স্পষ্ট যে এইভাবে নির্মিত কার্নেলটি নির্ভর করে আমরা দ্বিপক্ষীয় গ্রাফে কি ধরনের ন্যূনতম শীর্ষবিন্দু কভার নিয়েছি তার উপর। আমি একটি নিতে চাই যাতে অবশিষ্ট শীর্ষবিন্দুর সংখ্যা ন্যূনতম হয়। পূর্বে, তারা শুধুমাত্র সময়ে এটি করতে সক্ষম ছিল . আমি সময়ে এই অ্যালগরিদমের একটি বাস্তবায়ন নিয়ে এসেছি , এইভাবে, প্রতিটি শাখার পর্যায়ে এই কোরটি কয়েক হাজার শীর্ষবিন্দুর গ্রাফে অনুসন্ধান করা যেতে পারে।

ফল

অনুশীলন দেখায় যে আমার সমাধান কয়েকশ শীর্ষবিন্দু এবং কয়েক হাজার প্রান্তের পরীক্ষায় ভাল কাজ করে। এই ধরনের পরীক্ষায় এটি আশা করা সম্ভব যে আধা ঘন্টার মধ্যে একটি সমাধান পাওয়া যাবে। একটি গ্রহণযোগ্য সময়ে উত্তর খোঁজার সম্ভাবনা, নীতিগতভাবে, যদি গ্রাফটিতে যথেষ্ট পরিমাণে উচ্চ ডিগ্রির শীর্ষবিন্দু থাকে, উদাহরণস্বরূপ, ডিগ্রি 10 এবং উচ্চতর।

প্রতিযোগিতায় অংশগ্রহণের জন্য সমাধান পাঠাতে হতো optil.io. সেখানে উপস্থাপিত তথ্য বিচার করে ড চিহ্ন, খোলা পরীক্ষায় আমার সমাধান বিশটির মধ্যে তৃতীয়, দ্বিতীয় থেকে একটি বড় ব্যবধান সহ। সম্পূর্ণরূপে সৎ হতে, প্রতিযোগিতায় সমাধানগুলি কীভাবে মূল্যায়ন করা হবে তা সম্পূর্ণরূপে পরিষ্কার নয়: উদাহরণস্বরূপ, আমার সমাধানটি চতুর্থ স্থানে থাকা সমাধানের চেয়ে কম পরীক্ষায় উত্তীর্ণ হয়, তবে যারা পাস করে তাদের ক্ষেত্রে এটি দ্রুত কাজ করে।

ক্লোজড টেস্টের ফলাফল জানা যাবে ১লা জুলাই।

উত্স: www.habr.com