অ্যালগরিদম নিয়ে আরও কথা

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

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

তবে যুদ্ধজয়ের মতো গুরুত্বপূর্ণ না হলেও দৈনন্দিন জীবনে অনেক কাজে আমরা না জেনেই হয়তো এই অ্যালগরিদম ব্যবহার করে থাকি। যেমন, তোমাকে যদি অনেক বই এক জায়গা থেকে অন্য জায়গায় সরাতে বলা হয়, তাহলে তুমি কীভাবে করবে? সব বই একসঙ্গে সরাতে গেলে হয়তো অনেক ভারী হয়ে যাবে। কিন্তু যদি ছোট ছোট ভাগে কয়েকবারে কাজটি করা হয়, তাহলে সহজেই আমরা কাজটি করতে পারি, তাই না?

গত পর্বে দেখানো শেষে অ্যালগরিদমটি ছিল একটি উরারফব and Conquer অ্যালগরিদম। একে আমরা বাইনারি সার্চ বলে থাকি। এটি কীভাবে কাজ করে, তা বলার আগে চলো আমরা একটি গেম খেলি।

তুমি এই খেলাটি যে কারও সঙ্গেই খেলতে পারো। খেলাটি এমন, প্রথমে তুমি একজন ব্যক্তিকে ১ থেকে ১০০০-এর মধ্যে যেকোনো একটি সংখ্যা মনে মনে ধরতে বলবে। এরপর তুমি অনুমান করার চেষ্টা করবে যে সে কোন সংখ্যাটি ধরেছে। প্রতিবার তুমি একটি করে সংখ্যা বলবে, আর ওই ব্যক্তি তোমাকে জানাবে যে তোমার অনুমান সঠিক কি না। যদি সঠিক না হয়ে থাকে, তাহলে সে তোমাকে জানাবে তোমার অনুমান থেকে তার সংখ্যাটি বড় নাকি ছোট। এই খেলাটিতে সঠিক সংখ্যাটি অনুমান করার জন্য তোমাকে ঠিক কতগুলো অনুমান লাগতে পারে? মনে রাখবে, আমরা ভাগ্যের ওপর নির্ভর করতে চাই না। সবচেয়ে বাজে অবস্থাতেও আমরা চাই যতটা সম্ভব কম অনুমান করেই সংখ্যাটি জানতে।

গত মাসের কিআ প্রোগ্রামিং ক্লাবের মিটিংয়ে আমরা গেমটি খেলেছিলাম। আমরা যখন বললাম, ১ থেকে ১০০০-এর মধ্যে যেকোনো সংখ্যা সঠিকভাবে অনুমান করতে আমাদের ১০টির বেশি অনুমান দরকার হবে না, তখন অনেকেই বিশ্বাস করেনি। কিন্তু পরে রাঈদা ঠিকই ১০টির কম অনুমানেই বের করতে পেরেছিল। পরের জন খেলতে চাইল ১ থেকে ২০০০-এর মধ্যে সংখ্যা নিয়ে।

আমরা বললাম, আমাদের এখন ১১টি অনুমান লাগবে। এবারও আমরা পেরেছিলাম। কিন্তু কীভাবে?

না, কোনো জাদুর বলে নয়, বরং আমাদের টেকনিক আসলে ছিল বাইনারি সার্চ।

রাঈদা যেটি করছিল তা হলো, প্রতিবার সে মাঝের সংখ্যা অনুমান করছিল। যেমন তার প্রথম অনুমান ছিল ৫০০। যখন বলা হলো, উত্তরের সংখ্যাটি এই অনুমান থেকে বড়, তখনই কিন্তু বোঝা গেল যে উত্তরটি অবশ্যই ৫০১ থেকে শুরু করে ১০০০-এর মধ্যে কোনো একটি সংখ্যা। কাজেই এর পরেরবারের অনুমান হলো ৭৫০। কারণ এটি ৫০১ থেকে ১০০০-এর ঠিক মাঝের সংখ্যা। যখন জানানো হলো যে উত্তর এর থেকেও বড়, তখন বোঝা গেল উত্তর অবশ্যই ৭৫১ থেকে ১০০০-এর মধ্যে।

পরবর্তী অনুমান হলো (১০০০ + ৭৫১) / ২ = ৮৭৫। এবার বলা হলো, উত্তর এর থেকে ছোট। কাজেই মূল উত্তরটি অবশ্যই ৭৫১ থেকে ৮৭৫-এর মধ্যে, তাই না?

বুঝতেই পারছ, এভাবে করতে থাকলে খুব দ্রুতই আমর বের করতে পারব কোন সংখ্যাটি আমাদের উত্তর। এই পদ্ধতিটি একটি বাইনারি সার্চ পদ্ধতি। কারণ, এই পদ্ধতিতে প্রতি ধাপেই আমাদের উত্তরের যে সীমা, সেটি অর্ধেক হয়ে যাচ্ছে। আমরা শুরু করেছিলাম ১ থেকে ১০০০ নিয়ে। কিন্তু প্রথম অনুমানের পরই সেটি হয়েছে ৫০১ থেকে ১০০০। এইভাবে চলে বলেই অতি দ্রুত আমাদের সীমাটি ছোট হতে হতে একসময় একটি সংখ্যাতে চলে আসে এবং সেটিই হয় আমাদের উত্তর।

তাহলে আমরা কীভাবে বুঝলাম যে আমাদের মাত্র ১০টি অনুমান লাগবে? যদি উল্টো দিক থেকে চিন্তা করি, তাহলে বুঝতেই পারছ যে ১টি সংখ্যার ক্ষেত্রে আমাদের লাগবে ০টি অনুমান। ২টি সংখ্যার ক্ষেত্রে ১টি। চারটি সংখ্যার ক্ষেত্রে লাগবে ২টি অনুমান। ৮টি সংখ্যার ক্ষেত্রে লাগবে ৩টি অনুমান। এইভাবে চলতে থাকলে:

১৬ সংখ্যার জন্য ৪টি অনুমান।

৩২ সংখ্যার জন্য ৫টি অনুমান।

৬৪ সংখ্যার জন্য ৬টি অনুমান।

১২৮ সংখ্যার জন্য ৭টি অনুমান।

২৫৬ সংখ্যার জন্য ৮টি অনুমান।

৫১২ সংখ্যার জন্য ৯টি অনুমান।

১০২৪ সংখ্যার জন্য ১০টি অনুমান।

কাজেই আমরা দেখতে পাচ্ছি, ১০টি অনুমানের মাধ্যমে আমরা ১ থেকে ১০২৪ পর্যন্ত সংখ্যার ক্ষেত্রে উত্তর নির্ণয় করতে পারব। এটিকে আমরা অন্যভাবেও বের করতে পারি। আসলে, আমরা যদি ঘটি সংখ্যা নিয়ে কাজ করি, তাহলে আমাদের দরকার হবেlog2(N) টি অনুমান।

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

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