বেশ কিছুদিন ডিপি নিয়ে লেখার পর আবার গ্রাফ থিওরিতে ফিরে এলাম। আজকে আমরা একটা সহজ কিন্তু ইন্টারেস্টিং প্রবলেম দেখবো। স্টেবল ম্যারিজ(Stable Marriage) প্রবলেম এক ধরনের বাইপারটাইট ম্যাচিং প্রবলেম,তবে এটা শেখার জন্য অন্য কোনো অ্যালগোরিদম জানার প্রয়োজন নেই।
মনে করি n টা ছেলে আর n টা মেয়ে আছে। এখন তাদের মধ্যে বিয়ে দিতে হবে এমন ভাবে যেনো বিয়ে “স্টেবল” হয়। প্রত্যেকের সাথেই প্রত্যেকের বিয়ে দেয়া সম্ভব তবে প্রতিটা ছেলে আর মেয়ের কিছু পছন্দ আছে,প্রত্যেকেই চাইবে তার পছন্দের মানুষকে বিয়ে করতে। যদি ছেলে ৩জনের নাম Tom,Bob,Peter , আর মেয়ে ৩জনের নাম Alice,Mary,Lucy হয় তাহলে ছেলেদের পছন্দের তালিকা হতে পারে এরকম:
তালিকাটা বেশি থেকে কম পছন্দের ক্রমে করা হয়েছে। যেমন টম এলিসকে বেশি পছন্দ করে, লুসিকে কম পছন্দ করে।
আবার মেয়েদের পছন্দের তালিকাটা হতে পারে এরকম:
এখন কিভাবে বিয়ে দিলে বিয়ে স্টেবল হবে? আগে বুঝা দরকার স্টেবল বলতে কি বুঝাচ্ছি। ধরো নিচের মতো করে বিয়ে দেয়া হলো:
এই ম্যাচিং/বিয়েটা স্টেবল না, কারণ টম লুসির থেকে মেরিকে বেশি পছন্দ করে,আবার মেরি পিটারের থেকে টমকে বেশি পছন্দ করে। তাই টম আর মেরি বিয়ে ভেঙে একসাথে চলে আসতে পারে। যদি A,B ছেলে আর C,D মেয়ে হয় আর A-C এবং B-D কে বিয়ে দেয়া হয় তাহলে বিয়ে স্টেবল হবেনা যদি নিচের দুটি স্টেটমেন্টই সত্য হয়:
১. A যদি C এর থেকে D কে বেশি পছন্দ করে।
২. D যদি B এর থেকে A কে বেশি পছন্দ করে।
২টি স্টেটমেন্ট সত্য হলে A আর D বিয়ে ভেঙে চলে আসবে! তবে যেকোনো একটা স্টেটমেন্ট মিথ্যা হলে বিয়ে স্টেবল হবে।
১৯৬২ সালে David Gale আর Lloyd Shapley প্রমাণ করেন, সমান সংখ্যক ছেলে আর মেয়ের জন্য সমসময় স্টেবল ম্যারেজ প্রবলেমের একটি সমাধান আছে। তারা খুব সহজ একটা অ্যালগোরিদম আবিষ্কার করেন সমস্যাটি সমাধানে জন্য। অ্যালগোরিদমটি এরকম:
১. প্রথমে প্রতিটি অবিবাহিত ছেলে তার সবথেকে পছন্দের মেয়েটাকে প্রস্তাব পাঠাবে যাকে সে এখনো প্রস্তাব পাঠায়নি, মেয়েটি অলরেডি এনগেজড হলেও সমস্যা নাই,একটি মেয়েকে একাধিক ছেলে প্রস্তাব পাঠাতে পারে। একটি ছেলে কখনো একটি মেয়েকে দুইবার প্রস্তাব পাঠাবেনা।
২. এবার প্রতিটা মেয়ে তাকে যারা প্রস্তাব পাঠিয়েছে তাদের মধ্যে থেকে যাকে সবথেকে পছন্দ তাকে নির্বাচিত করবে,বাকি সবাইকে বাতিল করে দিবে। মেয়েটি আগেই কাওকে পছন্দ করে থাকলে তাকেও বাতিল করে দিবে।
৩. এখনো কেও অবিবাহিত থাকলে ১ম ধাপের পুনরাবৃত্তি হবে।
অ্যালগোরিদমটি কেনো কাজ করে? ধরি A-C এবং B-D এর বিয়ে দেয়া হয়ছে। তাহলে বিয়ে ভাঙবে A যদি D কে বেশি পছন্দ করে এবং D যদি A কে বেশি পছন্দ করে। কিন্তু উপরের অ্যালগোরিমে সেটা সম্ভবনা। কারণ:
A যদি D কে বেশি পছন্দ করে তাহলে সে D কে আগে প্রস্তাব পাঠাবে,D রাজি না হলে বা ছেড়ে দিলেই একমাত্র C কে প্রস্তাব পাঠাবে।
D যদি A কে বেশি পছন্দ করে তাহলে সে অন্য যে কাওকে ছেড়ে দিয়ে A কে বিয়ে করবে।
আর D যদি A কে বিয়ে না করে অন্য কাওকে করে তারমানে সে অন্য কাওকেই বেশি পছন্দ করে,এক্ষেত্রে বিয়ে ভাঙার সম্ভাবনা নেই।
এই অ্যালগোরিমটা স্টেবল ম্যাচিং দিবে ঠিকই তবে অপটিমাল রেজাল্ট নাও দিতে পারে। প্রতিটি ছেলের জন্য রেজাল্ট অপটিমাল হবে,কিন্তু মেয়েদের জন্য অপটিমাল নাও হতে পারে,অর্থাৎ এমন স্টেবল ম্যাচিং থাকতে পারে যেটাও কোনো একটি মেয়ে আরো পছন্দের কাওকে বিয়ে করতে পারতো। অর্থাৎ যে প্রস্তাব পাঠাবে তার জন্য রেজাল্ট অপটিমাল হবে।
অ্যালগোরিদমটি কোডে ইমপ্লিমেন্ট করা খুব সহজ। preference লিস্ট তোমাকে ইনপুট দেয়া থাকবে। কে কাকে প্রস্তাব পাঠিয়েছে,কে কার সাথে এখন এনগেজড এই তথ্যগুলো অ্যারেতে রেখে সহজেই কোডটা লিখে ফেলতে পারবে। wikipedia তে দেয়া সুডোকোডটা এরকম:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function stableMatching { Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to { w = m's highest ranked such woman to whom he has not yet proposed if w is free (m, w) become engaged else some pair (m', w) already exists if w prefers m to m' (m, w) become engaged m' becomes free else (m', w) remain engaged } } |
প্রবলেম:
Light OJ: Employment
Codechef: Stable Marriage
Uva: Chemical Attraction
Codechef: Blocking
গ্রাফ থিওরি নিয়ে অন্যান্য লেখা
ফেসবুকে মন্তব্য
Powered by Facebook Comments
wikipedia এর লিঙ্ক টা দিলে ওখানের pseudo-code দেখে সবাই সহজেই কোড করতে পারবে। 🙂
ভাইয়া, আপনি যদি কষ্ট করে একটু নিয়মিত লিখতেন তাহলে আমাদের অনেক উপকার হত। আপনার নতুন নতুন পোষ্টের জন্য আমি সবসময় অপেক্ষা করে থাকি।
ভালো লাগলো শুনে। আমি চেষ্টা করবো আরো রেগুলার হতে,মাঝে মাঝে আমাকে টপিক সাজেস্ট করলে ভালো হয়।
ভাইয়া next_permutation অ্যালগরিদম নিয়ে যদি একটা পোস্ট দিতেন তাহলে আমার অনেক উপকার হত । এই topic টা আমার কিছুতেই clear হচ্ছে না ।
ভাইয়া, সুডোকোড এর সাথে একটা স্যাম্পল কোড দিয়ে দিলে হেল্পফুল হত।
আচ্ছা, এখানের স্যুডোকোডের ডিরেক্ট ইমপ্লিমেন্টেশনের কমপ্লেক্সিটি কত? O(n*n) ? আরো অপটিমাইজড কোনো প্রসেস কি আছে? নাকি এটাকেই অপটিমাল করার ট্রাই করতে হবে?
বাইপারটাইট ম্যাচিং দিয়ে সলভ করা যেতে পারে তবে n*n এর কমে হবেনা। আরো ভালো কিছু থাকতেই পারে তবে আমার জানা নেই।
“এই অ্যালগোরিমটা স্টেবল ম্যাচিং দিবে ঠিকই তবে অপটিমাল রেজাল্ট নাও দিতে পারে। প্রতিটি ছেলের জন্য রেজাল্ট অপটিমাল হবে,কিন্তু মেয়েদের জন্য অপটিমাল নাও হতে পারে,অর্থাৎ এমন স্টেবল ম্যাচিং থাকতে পারে যেটাও কোনো একটি মেয়ে আরো পছন্দের কাওকে বিয়ে করতে পারতো। অর্থাৎ যে প্রস্তাব পাঠাবে তার জন্য রেজাল্ট অপটিমাল হবে।”
please,give an example for this case