লাস ভেগাস বনাম মন্টি কার্লো (Las Vegas vs Monte Carlo)

বেশিরভাগ অ্যালগরিদম একটি নির্দিষ্ট নিয়ম বা রেসিপি মেনে চলে: একই ইনপুট দিলে, তারা সর্বদা হুবহু একই ধাপগুলো অনুসরণ করে। কিন্তু কম্পিউটার সায়েন্সের সবচেয়ে সুন্দর ও মার্জিত কিছু অ্যালগরিদম কাজের ফাঁকে মুদ্রা নিক্ষেপের (flipping coins) মতো আচরণ করে। তারা র্যান্ডম বা দৈবচয়নের মাধ্যমে সিদ্ধান্ত নেয় — আর মজার ব্যাপার হলো, এরপরেও তারা সঠিকভাবে (বা প্রায় সবসময়ই সঠিকভাবে) কাজ করে এবং প্রচণ্ড দ্রুত হয়।

এগুলোকে র্যান্ডমাইজড অ্যালগরিদম (randomized algorithms) বলা হয়। এখানে র্যান্ডমনেস বা দৈবচয়ন কোনো ত্রুটি নয় — এটিই আসলে এর মূল হাতিয়ার। কোডকে সহজ করতে, ক্ষতিকর বা অ্যাডভারসারিয়াল ইনপুট (adversarial inputs) এড়াতে, বা গতানুগতিক বা ডিটারমিনিস্টিক (deterministic) অ্যালগরিদমগুলোর চেয়েও ক্ষেত্রবিশেষে ভালো গড় গতি (average-case speeds) অর্জন করতেই এটি ব্যবহার করা হয়।

দুটি ভিন্ন স্বাদ: লাস ভেগাস (Las Vegas) এবং মন্টি কার্লো (Monte Carlo)

ক্যাসিনোর শহরগুলোর নামানুসারে এই র্যান্ডমাইজড অ্যালগরিদমগুলোর দুটি প্রধান ভাগ বা ক্যাম্প (camp) রয়েছে (মূল সংযোগ হলো: দুটিতেই এক ধরনের জুয়ার ব্যাপার আছে, তবে ভিন্ন উপায়ে)।

একটি লাস ভেগাস (Las Vegas) অ্যালগরিদম সর্বদা সঠিক উত্তর প্রদান করে। এখানে শুধু একটি জিনিসই পরিবর্তন হয়, আর তা হলো এটি সম্পন্ন হতে কত সময় নেবে। এটিকে এমন একটি স্লট মেশিনের (slot machine) মতো ভাবতে পারেন যা শেষপর্যন্ত অর্থ প্রদান করেই — শুধু আপনি জানেন না কখন করবে। র্যান্ডমাইজড কুইক-সর্ট (Randomized QuickSort) এর সবচেয়ে চমৎকার উদাহরণ: যাই ঘটুক না কেন, এর আউটপুট হবে একটি সর্টেড বা সাজানো অ্যারে (sorted array)। শুধু এর রানটাইম বা সময় নির্ভর করে আপনি র্যান্ডমভাবে কোন পিভট (pivot) বেছে নিচ্ছেন তার ওপর।

একটি মন্টি কার্লো (Monte Carlo) অ্যালগরিদম সবসময় একটি নির্ধারিত সময়ের (fixed amount of time) মধ্যে কাজ শেষ করে কিন্তু মাঝে মাঝে এটি ভুল উত্তরও দিতে পারে। তবে ভুল হওয়ার সম্ভাবনা খুবই কম এবং এটি নিয়ন্ত্রণের মধ্যে থাকে। মিলার-রবিন প্রাইমালিটি টেস্ট বা মৌলিক সংখ্যা যাচাই পদ্ধতি (Miller-Rabin primality test) এর একটি আদর্শ উদাহরণ: এটি k বার চালান, আর ফলস পজিটিভ (false positive) বা ভুল হওয়ার সম্ভাবনা কমে দাঁড়াবে 4^(-k)। যদি k=40 হয়, তবে এর সম্ভাবনা এক ট্রিলিয়নে একবার — যে কোনো বাস্তব ও ব্যবহারিক কাজের জন্য এটি অত্যন্ত নিরাপদ।

তাহলে শুধু ডিটারমিনিস্টিক (Deterministic) অ্যালগরিদম ব্যবহার করা হয় না কেন?

এর দুটি বড় কারণ রয়েছে:

• অ্যাডভারসারিয়াল ইনপুট (Adversarial inputs): ডিটারমিনিস্টিক অ্যালগরিদমে সবসময় এমন একটি নির্দিষ্ট ওয়ার্স্ট-কেস বা সবচেয়ে খারাপ অবস্থা থাকে, যা একজন অ্যাটাকার বা হ্যাকার পরিকল্পিতভাবে তৈরি করতে পারে। যদি আপনার হ্যাশ টেবিল সর্বদা একই হ্যাশ ফাংশন ব্যবহার করে, তবে একজন অ্যাটাকার এমন ইনপুট তৈরি করতে পারে যাতে সব ইনপুটগুলো হ্যাশ টেবিলে একই জায়গায় গিয়ে কলিশন (collision) বা সংঘর্ষ ঘটায়, যা প্রতিটি অপারেশনকেই \(O(n)\) তে নামিয়ে আনে। তবে একটি র্যান্ডমাইজড হ্যাশ ফাংশন এটিকে প্রায় অসম্ভব করে তোলে — কারণ অ্যাটাকার কখনোই আগে থেকে জানতে পারে না যে আপনি কোন ফাংশনটি রানটাইমে বেছে নেবেন।
• সরলতা (Simplicity): সমতুল্য গ্যারান্টি থাকার পরও, কিছু ডিটারমিনিস্টিক অ্যালগরিদমের তুলনায় অনেক র্যান্ডমাইজড অ্যালগরিদম ইমপ্লিমেন্ট (implement) বা প্রয়োগ এবং অ্যানালাইজ করা বিস্ময়করভাবে সহজ। উদাহরণস্বরূপ, র্যান্ডমাইজড কুইক-সর্ট ৫ লাইনের কোড; যেখানে মিডিয়ান-অফ-মিডিয়ানস (Median-of-Medians) (যাতে সুনিশ্চিতভাবে \(O(n \log n)\) ডিটারমিনিস্টিক সর্ট হয়) ডজন ডজন লাইনের কোড নিতে পারে।

প্রোবাবিলিটি অ্যাম্প্লিফিকেশন বা সম্ভাব্যতার পরিবর্ধন (Probability Amplification)

মন্টি কার্লো অ্যালগরিদমগুলো বারবার পুনরাবৃত্তির বা রিপিটিশনের (repetition) মাধ্যমে অবিশ্বাস্যরকম নির্ভরযোগ্য হয়ে উঠতে পারে। যদি একবার রান করানোর ফলে ভুল উত্তর পাওয়ার সম্ভাবনা ১/৪ (1/4) হয়, তবে সেটিকে স্বাধীনভাবে বা ইন্ডিপেন্ডেন্টলি k বার রান করিয়ে এবং সবার মধ্যে মেজরিটি ভোট (majority vote) নেওয়ার মাধ্যমে ওই ভুলের সম্ভাবনাকে সূচকীয়ভাবে ছোট (exponentially small) বা k এর কাছাকাছি নিয়ে আসা যায়। এটিকে প্রোবাবিলিটি অ্যাম্প্লিফিকেশন (probability amplification) বলা হয় — যা একটি অত্যন্ত শক্তিশালী এবং সাধারণ কৌশল।