খোঁজাখুঁজির অ্যালগরিদম

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

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

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

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

১. সবার ওপরের খাতাটির রোল নম্বরের সঙ্গে কাঙ্ক্ষিত রোল নম্বর মিলিয়ে দেখি।

২. যদি মিলে যায়, তাহলে আমাদের খোঁজা শেষ। সরাসরি চতুর্থ ধাপে চলে যাই।

৩. যদি না মেলে তাহলে ওপরের খাতাটি সরিয়ে স্তূপের নিচে রেখে দিয়ে আবার ১ নম্বর ধাপ থেকে শুরু করি।

৪. খাতাটি ছাত্রকে দেখাই।

যদিও এ অ্যালগরিদম লেখা ও বোঝা আমাদের জন্য সহজ, কিন্তু আমরা জানি, বাস্তবে এ অ্যালগরিদম অনেক বেশি সময়সাপেক্ষ। যদি আমাদের কাছে ১০০ খাতা থাকে, তাহলে প্রতিবার কোনো একজন ছাত্রের খাতা খুঁজে পেতে আমাদের ১০০টি খাতাই উল্টে দেখতে হতে পারে (যদি খুব বেশি দুর্ভাগ্য হয়)। ভাগ্যবান হলে হয়তো আমরা প্রথমেই খাতাটি পেয়ে যেতে পারি, কিন্তু কম্পিউটার বিজ্ঞান সব সময় সবচেয়ে খারাপ পরিস্থিতিতেও সবচেয়ে ভালো উপায় খুঁজে পেতে চায়। তাই আমরা এমন কোনো অ্যালগরিদম খুঁজে বের করার চেষ্টা করব, যেটা যেকোনো পরিস্থিতিতেই খুব ভালো কাজ করবে।

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

১. যদি কাঙ্ক্ষিত রোল নম্বরটি ৫০ থেকে ছোট হয়, তাহলে আমরা ‘খোঁজার অ্যালগরিদম ১’-এর মতো কাজ করব।

২. যদি কাঙ্ক্ষিত রোল নম্বরটি ৫০-এর বড় হয়, তাহলে আমরা পুরো খাতার স্তূপটিকে উল্টিয়ে নেব, যাতে এখন খাতাগুলো রোল নম্বর অনুযায়ী বড় থেকে ছোট আকারে সাজানো থাকে। এরপর ‘খোঁজার অ্যালগরিদম ১’-এর মতো কাজ করব।

এই অ্যালগরিদম লেখার ক্ষেত্রে আমরা একটি শর্টকাট নিয়েছি। আমরা ‘খোঁজার অ্যালগরিদম ১’ বলার মাধ্যমে ওপরের চারটি লাইন বারবার লেখা বাঁচিয়ে ফেলেছি। এটি প্রোগ্রামিংয়ে বহুল ব্যবহূত টেকনিক। মজার ব্যাপার হলো, এখন খাতাগুলোকে সাজিয়ে আমরা অনেক কাজ বাঁচিয়ে ফেলেছি। একটু চিন্তা করলেই বুঝতে পারবে, এখন সবচেয়ে খারাপ পরিস্থিতিতেও ৫০টির বেশি খাতা ওল্টাতে হবে না। কাজেই ‘খোঁজার অ্যালগরিদম ১’-এর চেয়ে অর্ধেক পরিশ্রমে এখন প্রতিটা খোঁজা কাজ করতে পারব।

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

১. খাতার স্তূপটিকে দুই ভাগ করি। ডান পাশে রাখি ওপরের অংশটুকু এবং বাঁ পাশে রাখি নিচের অংশটুকু।

২. যদি বাঁ পাশের সবচেয়ে ওপরের খাতার রোল নম্বরের সঙ্গে আমাদের কাঙ্ক্ষিত রোল নম্বর মিলে যায়, তাহলে ৫ নম্বর ধাপে যাই।

৩. যদি বাঁ পাশের সবচেয়ে ওপরের খাতার রোল নম্বরটি সঙ্গে আমাদের কাঙ্ক্ষিত রোল নম্বরের থেকে বড় হয়, তাহলে আমরা বুঝতে পারি যে আমাদের কাঙ্ক্ষিত খাতাটি ডান পাশের অংশে আছে। এ ক্ষেত্রে আমরা বাঁ পাশের অংশটি সরিয়ে রাখি এবং ডান পাশের অংশটিকে মূল স্তূপ বিবেচনা করে ১ নম্বর ধাপ থেকে আবার কাজ শুরু করি।

৪. ২ বা ৩ নম্বরের কোনোটিই না হলে খাতাটি অবশ্যই বাঁ পাশের আছে। এ ক্ষেত্রে আমরা ডান পাশের অংশটি সরিয়ে রাখি। বাঁ পাশের অংশটিকে মূল স্তূপ বিবেচনা করে ১ নম্বর ধাপ থেকে আবার কাজ শুরু করি।

৫. খাতাটি খুঁজে পাওয়া গেছে।

যদি বুঝতে সমস্যা হয়, সে ক্ষেত্রে আমরা একটি উদাহরণ দিলে হয়তো পরিষ্কার হয়ে যাবে।

• ধরি আমরা রোল নম্বর ৩৮-এর খাতা খুঁজতে চাই।

• তাহলে আমরা প্রথমে দুই অংশে খাতাগুলোকে ভাগ করব, যেটির বাঁ অংশে থাকবে রোল ৫১ থেকে ১০০-এর খাতা এবং ডান অংশে থাকবে রোল ১ থেকে ৫০-এর খাতা।

• যেহেতু বাঁ অংশের সবার ওপরের খাতার রোল নম্বর (৫১) আমাদের কাঙ্ক্ষিত রোল নম্বর (৩৮) থেকে বড়, কাজেই ৩ নম্বর ধাপের মতো করে আমরা বাঁ পাশের অংশকে সরিয়ে রাখব এবং আমাদের মূল স্তূপে এখন থাকবে রোল ১ থেকে ৫০ রোল নম্বরের খাতাগুলো।

• এই স্তূপকে আমরা দুই অংশে ভাগ করব। বাঁ অংশে থাকবে রোল ২৬ থেকে ৫০-এর খাতা। ডান অংশে থাকবে রোল ১ থেকে ২৫-এর খাতা।

• ৪ নম্বর ধাপ অনুযায়ী আমরা ডান অংশকে সরিয়ে রাখব এবং বাঁ অংশকে নিয়ে কাজ চালিয়ে যাব।

• আবারও আমরা দুই অংশে ভাগ করব। বাঁ অংশে থাকবে রোল ৩৮ থেকে ৫০ এবং ডান অংশে থাকবে রোল ২৬ থেকে ৩৭। ২ নম্বর ধাপ অনুযায়ী আমরা খাতাটি খুঁজে পেলাম।

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

যদি আমাদের ক্লাসে ১০০ জন ছাত্র না থেকে ঘ জন ছাত্র থাকে, তাহলে আমাদের দেওয়া তিনটি অ্যালগরিদমের কোনটিতে কী পরিমাণ খাতা ওল্টাতে হবে? আমরা সবচেয়ে খারাপ পরিস্থিতির জন্য এর উত্তর চাচ্ছি। তোমার দেওয়া উত্তরের গাণিতিক প্রমাণ কি করতে পারবে?