NP-হার্ডনেসের মুখোমুখি — এক্স্যাক্ট, অ্যাপ্রক্সিমেট নাকি হিউরিস্টিক

১ · সিদ্ধান্ত-কাঠামো — তিনটি প্রশ্ন, তিনটি পথ

L48-এর চেকলিস্ট অনুযায়ী আপনি সন্দেহ করছেন (বা জানেন) সমস্যাটি NP-হার্ড। এখন সরাসরি তিনটি প্রশ্ন জিজ্ঞেস করুন — প্রতিটির উত্তর একটি ভিন্ন, ইতিমধ্যে এই কোর্সে কভার করা কৌশলের দিকে নিয়ে যায়।

২ · পথ ১ — ইনপুট সবসময় ছোট: এক্স্যাক্ট পদ্ধতি (M8)

যদি আপনার নির্দিষ্ট অ্যাপ্লিকেশনে ইনপুটের আকার $n$ কখনোই একটা ছোট সীমা ছাড়িয়ে যায় না (যেমন একদিনের ডেলিভারি রুটে ৮-১০টা স্টপ, বা একটা সাবসেট নির্বাচনের সমস্যায় মাত্র ২০-২৫টা আইটেম), তাহলে এক্সপোনেনশিয়াল-সময়ের একটি সঠিক অ্যালগরিদমও ব্যবহারিকভাবে দ্রুত চলতে পারে — বিশেষ করে ভালো prune করা ব্যাকট্র্যাকিং (L36-L37) বা ব্রাঞ্চ-অ্যান্ড-বাউন্ড (L38-L39) ব্যবহার করলে, যা পুরো সার্চ স্পেস এক্সপ্লোর না করেই সঠিক অপ্টিমাম খুঁজে দেয়। এই পথে কোনো আপস করতে হয় না — আউটপুট সবসময় প্রকৃত অপ্টিমাম, শুধু সময়ের নিশ্চয়তা exponential (worst-case)।

নিচের কোডে দেখা যাক "ইনপুট ছোট" বলতে ব্যবহারিকভাবে কী বোঝায় — L39-এর TSP সমস্যার জন্য শহরের সংখ্যা বাড়লে ব্রুট-ফোর্স ট্যুরের সংখ্যা ($\,(n-1)!/2\,$) কত দ্রুত একটি অনুমিত "প্র্যাকটিক্যাল বাজেট" ছাড়িয়ে যায়।

import math

def tsp_brute_force_tours(n):
    # n-টা শহরের জন্য (একটাকে শুরু ধরে, প্রতিসম দূরত্বে দিক-নির্বিশেষে) সম্ভাব্য ভিন্ন ট্যুরের সংখ্যা
    return math.factorial(n - 1) // 2

BUDGET = 10 ** 9  # ধরা যাক, একটি অনুমিত ("illustrative") প্র্যাকটিক্যাল বাজেট -- ১০০ কোটি অপারেশন
# (প্রকৃত থ্রেশহোল্ড হার্ডওয়্যার ও কনস্ট্যান্ট ফ্যাক্টরের উপর নির্ভরশীল -- এটি শুধু আপেক্ষিক গ্রোথ দেখানোর জন্য)

print(f"{'n (শহর সংখ্যা)':>16} | {'সম্ভাব্য ট্যুর সংখ্যা':>22} | {'বাজেটের মধ্যে?':>15}")
for n in range(4, 18):
    tours = tsp_brute_force_tours(n)
    within_budget = "হ্যাঁ" if tours <= BUDGET else "না"
    print(f"{n:>16} | {tours:>22,} | {within_budget:>15}")

৩ · পথ ২ — প্রমাণিত-রেশিও অ্যাপ্রক্সিমেশন গ্রহণযোগ্য (M12)

যদি ইনপুট বড় হতে পারে, কিন্তু পুরোপুরি অপ্টিমাম না হয়ে একটা এমন উত্তরই যথেষ্ট যা প্রমাণিতভাবে সত্যিকারের অপ্টিমামের একটি নির্দিষ্ট গুণিতকের মধ্যে থাকে (যেমন সবসময় $\le 2 \times$ অপ্টিমাম) — তাহলে অ্যাপ্রক্সিমেশন অ্যালগরিদম এই আপসটা একটি গাণিতিক গ্যারান্টিসহ দেয়। এটি "হাল ছেড়ে দেওয়া" নয় — বরং একটি রিগোরাসভাবে প্রমাণিত trade-off। M12-এর L50-এ অ্যাপ্রক্সিমেশন রেশিওর আনুষ্ঠানিক সংজ্ঞা, L51-এ ভার্টেক্স কভার ও সেট কভারের ক্লাসিক ২-অ্যাপ্রক্সিমেশন, এবং L52-এ মেট্রিক TSP-এর MST-ভিত্তিক ২-অ্যাপ্রক্সিমেশন বিস্তারিত দেখা হবে।

৪ · পথ ৩ — অ্যাভারেজ-কেস পারফরম্যান্স জরুরি (M12)

কখনো কখনো ওয়ার্স্ট-কেস গ্যারান্টি (হয় সঠিকতার, নয় সময়ের) নিয়ে খুব বেশি চিন্তা না করে, বাস্তব-জীবনের সাধারণ (typical) ইনপুটে গড়ে ভালো পারফরম্যান্স হলেই যথেষ্ট। এমন ক্ষেত্রে র‍্যান্ডোমাইজেশন এবং হিউরিস্টিক পদ্ধতি কাজে লাগে — L16-এ আমরা ইতিমধ্যে দেখেছি কুইকসর্টের নেইভ ফিক্সড-পিভট ভার্সন adversarial ইনপুটে ধীর হয়ে যায় ($O(n^2)$); M12-এর L53-এ Las Vegas বনাম Monte Carlo র‍্যান্ডোমাইজড অ্যালগরিদমের পার্থক্য এবং L54-এ ঠিক এই adversarial-ইনপুট সমস্যাটা randomized pivot selection দিয়ে সমাধান করে (expected $O(n \log n)$) — একটি সরাসরি, গণনাকৃত payoff।