বাঘ, পান আর ছাগলের গল্প

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

সমাধান হতে পারে এ ভাবে। ১) বাঘ আর পান এ পারে রেখে, মাঝি ও পারে নিয়ে গেলেন ছাগল; ২) দ্বিতীয় বার ও পারে নিয়ে গেলেন বাঘ, কিন্তু এ বার আর খালি হাতে ফিরলেন না, ও পার থেকে এ পারে নিয়ে এলেন ছাগল; ৩) তৃতীয় বার ও পারে নিয়ে গেলেন পান, ফিরলেন খালি হাতে; ৪) চতুর্থ বারে ও পারে নিয়ে গেলেন ছাগল। পারাপারের এই ফর্মুলার রকমফের হতে পারে। যেমন, দ্বিতীয় বার বাঘ ও পারে না নিয়ে, পানও নিয়ে যাওয়া যায়। তা হলেও ফিরতি পথে সেই ছাগলকেই এ পারে আনতে হবে। তৃতীয় ও চতুর্থ বারে যথাক্রমে বাঘ ও ছাগলকে ও পারে নিয়ে গেলেই হবে।

ওই যে বাঘ, ছাগল আর পান পর পর ও পারে নিয়ে যাওয়া যাবে না, নিয়ে যেতে হবে লাভ-ক্ষতি বিবেচনা করে— এটা হল অপটিমাইজ়েশন। সবচেয়ে লাভজনক পন্থা নির্ণয়। পর পর বাঘ, ছাগল আর পান ও পারে নিয়ে যাওয়াও কিন্তু একটা পন্থা। তবে সে পন্থায় সমূহ ক্ষতি। এক-একটা পন্থা মানে এক-এক কম্বিনেশন। বহু রকম কম্বিনেশন থেকে সর্বশ্রেষ্ঠটি নির্বাচন করাকে বলে কম্বিনেটরিয়াল অপটিমাইজ়েশন। এই কম্বিনেটরিয়াল অপটিমাইজ়েশন গণিতশাস্ত্রে একটা বড় জায়গা দখল করে আছে। জায়গাটার নাম কম্বিনেটরিক্স।

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

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

তিন বঙ্গসন্তান যে বিষয়ে কাজ করেছেন, তাতে বেশ কিছু ধাঁধা বিখ্যাত হয়ে আছে। যেমন, ট্রাভেলিং সেলসম্যান প্রবলেম। এক কোম্পানির সেলসম্যান। ধরা যাক, তাঁকে যেতে হবে ৩০টা শহরে। এ দিকে কোম্পানির হুকুম, টিএ বিল বেশি করা চলবে না। তো বেচারা সেলসম্যান কোন শহরের পর কোন শহরে যাবেন, যাতে তাঁর যাত্রাপথ হবে সংক্ষিপ্ততম? বলা কঠিন। অথবা, সেই ধাঁধা, যা একদা এসেছিল প্রুশিয়ার শহর কনিগসবার্গ-এর অধিবাসীদের মনে। শহরের মধ্যে দিয়ে বয়ে চলেছে প্রেগেল নদী। ঘুরিয়ে-পেঁচিয়ে এমন ভাবে, যাতে তৈরি হয়েছে দুটো দ্বীপ। নদীর ওপর শহরবাসী বানিয়েছে সাতটা সেতু। ধাঁধা এই যে, শহরের এক দিক থেকে শুরু করে মাত্র একটা সেতু পেরিয়ে কি কেউ শহর ঘুরে ফিরে আসতে পারবে শুরুর জায়গাটিতে? কাজটা কি সম্ভব? ১৭৩৫ খ্রিস্টাব্দে যুক্তিজাল বিস্তার করে উত্তর দিলেন গণিতজ্ঞ লিয়োনার্ড অয়লার। বললেন, কাজটা সম্ভব নয়। ধাঁধা সমাধান করতে গিয়ে অয়লার কম্বিনেটরিক্স-এর নতুন শাখা খুলে দিলেন। শাখাটির নাম গ্রাফ থিয়োরি। শঙ্কর, অভিরূপ আর অমিতের কাজ ওই গ্রাফ থিয়োরি বিষয়েই।

১৮৫২ খ্রিস্টাব্দে ব্রিটিশ গণিতজ্ঞ ফ্রান্সিস গাথরি ইংল্যান্ডের কাউন্টিগুলোর মানচিত্র আঁকতে গিয়ে এক বিচিত্র ব্যাপার লক্ষ করেন। মানচিত্রে ভিন্ন এলাকা (দেশ, রাজ্য বা জেলা) বোঝাতে আলাদা রং ব্যবহার করতে হয়। গাথরি দেখেন, মাত্র চারটে রং দিয়েই ইংল্যান্ডের সব কাউন্টি আলাদা চিহ্নিত করা যাচ্ছে। সব মানচিত্র তো ইংল্যান্ডের কাউন্টিগুলোর মতো না-ও হতে পারে। হতে পারে ঢের বেশি জটিল। সে রকম মানচিত্রে আলাদা এলাকা বোঝাতেও কি মাত্র চারটে রং যথেষ্ট? অনেক দেশ-মহাদেশের মানচিত্র নিয়ে পরীক্ষা করেও গাথরি দেখলেন, চারটের বেশি রং দরকার হচ্ছে না। ওটা তো পর্যবেক্ষণ। মানচিত্র যতই জটিল হোক, বাস্তব বা কাল্পনিক, তা রাঙাতে কেন মাত্র চারটের বেশি রং লাগে না? জন্ম নিল কঠিন প্রশ্ন।

কঠিনই বটে। যুক্তিতর্কে প্রশ্নের উত্তর পেতে গড়াল ১২৪ বছর। ১৯৭৬ সালে ইলিনয় বিশ্ববিদ্যালয়ের দুই গণিতজ্ঞ কেনেথ অ্যাপেল এবং হোলফগাং হাকেন প্রমাণ করলেন, মানচিত্র যত জটিলই হোক, তা রাঙাতে কেন মাত্র চারটে রংই যথেষ্ট।

ম্যাপ কালারিং প্রবলেম থেকে গ্রাফ কালারিং প্রবলেম। ম্যাপ থেকে গ্রাফ। মানচিত্রে একটা এলাকাকে (দেশ, রাজ্য বা জেলা) যদি একটা বিন্দু কল্পনা করা যায়, তা হলে মানচিত্র বদলে বনে যায় ছড়ানো-ছিটানো বিন্দু। গ্রাফে ওগুলোকে বলে ‘নোড’ বা ‘ভার্টেক্স’। এ বার, যদি ওই বিন্দুগুলোকে পর পর যুক্ত করা যায় রেখা (‘লিংক’ বা ‘এজ’) দিয়ে, তবে সবটা দেখায় একটা জালের মতো। ওটাই গ্রাফ। এখন, কী নিয়মে নোডগুলোকে রং করলে পর পর দুটো বিন্দু (একটা এজ-এর দু’প্রান্তে দুটো নোড) এক রং পাবে না? আর, ন্যূনতম ক’টা রং দরকার?

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

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

কত দিন গবেষণার পর পাওয়া গেল এই অ্যালগরিদম? শঙ্করের উত্তর, ‘দশ বছর’।