Recursive largest first algorithm
রিকার্সিভ লার্জেস্ট ফার্স্ট (আর. এল. এফ) অ্যালগরিদম এন. পি-হার্ড গ্রাফ কালারিং সমস্যার জন্য একটি অনুসন্ধানমূলক। এটি মূলত 1979 সালে ফ্রাঙ্ক লেইটন দ্বারা প্রস্তাবিত হয়েছিল। আর. এল. এফ অ্যালগরিদম প্রতিটি রঙের শ্রেণীকে একবারে তৈরি করে গ্রাফের শীর্ষে রঙ বরাদ্দ করে। এটি গ্রাফের শীর্ষগুলির একটি সর্বাধিক স্বাধীন সেট চিহ্নিত করে, এগুলিকে একই রঙে বরাদ্দ করে এবং তারপরে গ্রাফ থেকে এই শীর্ষগুলি সরিয়ে দিয়ে এটি করে। এই ক্রিয়াগুলি অবশিষ্ট সাবগ্রাফে পুনরাবৃত্তি করা হয় যতক্ষণ না কোনও শীর্ষ থাকে। উচ্চমানের সমাধান তৈরি করতে (কয়েকটি রঙ ব্যবহার করে সমাধান), আরএলএফ অ্যালগরিদম "ভাল মানের" স্বাধীন সেটগুলি সনাক্ত করার চেষ্টা করার জন্য বিশেষ অনুসন্ধানমূলক নিয়ম ব্যবহার করে। এই অনুসন্ধানগুলি দ্বিদলীয়, চক্র এবং চাকা গ্রাফের জন্য আরএলএফ অ্যালগরিদমকে সঠিক করে তোলে। সাধারণভাবে, তবে, অ্যালগরিদমটি আনুমানিক এবং গ্রাফের ক্রোমাটিক সংখ্যার চেয়ে বেশি রঙ ব্যবহার করে এমন সমাধানগুলি ভালভাবে ফেরত দিতে পারে। বর্ণনা অ্যালগরিদমটি নিম্নলিখিত তিনটি ধাপ দ্বারা বর্ণনা করা যেতে পারে। এই প্রক্রিয়াটির শেষে, গ্রাফের একটি সম্ভাব্য-রঙের প্রতিনিধিত্বকারী শীর্ষগুলির একটি বিভাজন দেয়। একটি ফাঁকা সমাধান হতে দিন। এছাড়াও, একটি ভার্টেক্স সেট এবং একটি প্রান্ত সেট সমন্বিত গ্রাফটি আমরা রঙ করতে চাই। একটি সর্বাধিক স্বাধীন সেট চিহ্নিত করুন। এটি করার জন্যঃ যোগ করা প্রথম শীর্ষটি হওয়া উচিত যেটির শীর্ষে সবচেয়ে বেশি সংখ্যক প্রতিবেশী রয়েছে। যোগ করা পরবর্তী শীর্ষগুলি এমনভাবে বেছে নেওয়া উচিত যেগুলি (ক) বর্তমানে কোনও শীর্ষের সংলগ্ন নয় এবং (খ) শীর্ষগুলির সংলগ্ন সর্বাধিক সংখ্যক প্রতিবেশী রয়েছে। শর্তযুক্ত বন্ধনগুলি (খ) সর্বনিম্ন সংখ্যক প্রতিবেশী না থাকা শীর্ষবিন্দু নির্বাচন করে ভাঙা যেতে পারে। এইভাবে ভার্টিসগুলি যোগ করা হয় যতক্ষণ না আরও ভার্টিসগুলি যোগ করা অসম্ভব হয়। এখন থেকে এর শীর্ষগুলি সেট করুন এবং সরিয়ে ফেলুন। যদি এখনও শীর্ষস্থান থাকে, তাহলে দ্বিতীয় ধাপে ফিরে যান; অন্যথায় শেষ করুন। উদাহরণ ডানদিকে দেখানো গ্রাফটি বিবেচনা করুন। এটি একটি চাকা গ্রাফ এবং তাই আর. এল. এফ দ্বারা সর্বোত্তমভাবে রঙ করা হবে। অ্যালগরিদমটি কার্যকর করার ফলে শীর্ষগুলি নির্বাচন করা হয় এবং নিম্নলিখিত ক্রমে রঙ করা হয়ঃ ভার্টেক্স (রঙ 1) ভার্টেক্স, এবং তারপর (রঙ 2) ভার্টেক্স, এবং তারপর (রঙ 3) এটি চূড়ান্ত তিন রঙের সমাধান দেয়। কর্মক্ষমতা গ্রাফের শীর্ষগুলির সংখ্যা এবং প্রান্তের সংখ্যা ধরা যাক। বিগ ও নোটেশন ব্যবহার করে, তাঁর মূল প্রকাশনা লেইটন আরএলএফ-এর জটিলতার কথা উল্লেখ করেছেন; তবে, এটি উন্নত করা যেতে পারে। এই অ্যালগরিদমের বেশিরভাগ ব্যয় দ্বিতীয় ধাপের কারণে হয়, যেখানে উপরে বর্ণিত অনুসন্ধানমূলক নিয়ম অনুসারে শীর্ষ নির্বাচন করা হয়। প্রকৃতপক্ষে, প্রতিবার স্বাধীন সেট যোগ করার জন্য একটি শীর্ষ নির্বাচন করা হয়, প্রতিটি রঙহীন শীর্ষের জন্য প্রতিবেশী সম্পর্কিত তথ্য পুনরায় গণনা করা প্রয়োজন। এই গণনাগুলি সময়মতো করা যেতে পারে, যার অর্থ হল আরএলএফ-এর সামগ্রিক জটিলতা হল। যদি দ্বিতীয় ধাপের অনুসন্ধানগুলি এলোমেলো নির্বাচনের দ্বারা প্রতিস্থাপিত হয়, তবে এই অ্যালগরিদমের জটিলতা হ্রাস পায়; তবে, ফলস্বরূপ অ্যালগরিদম সাধারণত আর. এল. এফ-এর তুলনায় কম মানের সমাধান প্রদান করে। এটি এখন দ্বিদলীয়, চক্র এবং চাকা গ্রাফের জন্যও সঠিক হবে না। 2021 সালে লুইসের একটি অভিজ্ঞতাগত তুলনায়, আরএলএফকে লোভী অ্যালগরিদম এবং এলোমেলো গ্রাফের ডি-স্যাটুর অ্যালগরিদমের মতো বিকল্প হিউরিস্টিক্সের তুলনায় উল্লেখযোগ্যভাবে ভাল ভার্টেক্স রঙ তৈরি করতে দেখা গেছে। যাইহোক, উচ্চতর সামগ্রিক জটিলতার কারণে আরএলএফের সাথে রানটাইমও এই বিকল্পগুলির চেয়ে বেশি দেখা গেছে। এ গাইড টু গ্রাফ কালারিংঃ অ্যালগরিদমস অ্যান্ড অ্যাপ্লিকেশনস (স্প্রিংগার ইন্টারন্যাশনাল পাবলিশার্স, 2021) বইটিতে ব্যবহৃত হাই-পারফরম্যান্স গ্রাফ কালারিং অ্যালগরিদমস স্যুট অফ গ্রাফ কালারিং অ্যালগরিদমস (সি + +-এ বাস্তবায়িত)। 1979 ইন কম্পিউটিং গ্রাফ অ্যালগরিদম গ্রাফ কালারিং