অ্যাডভান্সড টপিক৮ মিনিট পড়া

অ্যাপ্রক্সিমেশন অ্যালগরিদম (Approximation Algorithms)

১% সময়ে ৯০% কাছাকাছি পৌঁছানো — সাথে গাণিতিক প্রমাণ
vertex cover:2-অ্যাপ্রক্সিমেশন, \(O(V+E)\)metric TSP:1.5-অ্যাপ্রক্সিমেশন (ক্রিস্টোফাইডস - Christofides)set cover:\(O(\log n)\)-অ্যাপ্রক্সিমেশন (গ্রিডি - greedy)

কিছু কিছু সমস্যা এতটা কঠিন যে সবচেয়ে দ্রুতগতির কম্পিউটারেও এর সঠিক বা অপ্টিমাল সমাধানটি খুঁজে বের করতে মহাবিশ্বের বয়সের চেয়েও বেশি সময় লেগে যেতে পারে। এগুলোকে বলা হয় এনপি-হার্ড (NP-hard) প্রবলেম। তাই এই ধরনের ক্ষেত্রে আপনার কী করা উচিত?

আপনি হাল ছেড়ে দেবেন না। আপনি একটি অ্যাপ্রক্সিমেশন অ্যালগরিদম (approximation algorithm) ব্যবহার করবেন: এটি এমন একটি দ্রুতগতির অ্যালগরিদম যা একটি প্রমাণযোগ্য প্রতিশ্রুতি (provable promise) দিয়ে থাকে যে এর উত্তরটি নিখুঁত বা অপ্টিমাল উত্তরের থেকে খুব একটা বেশি দূরে হবে না। এটি কোনো মনগড়া অনুমান নয় — এটি একটি গাণিতিক নিশ্চয়তা (mathematical guarantee)।

অ্যাপ্রক্সিমেশন রেশিও (The approximation ratio)

একটি অ্যালগরিদমে অ্যাপ্রক্সিমেশন রেশিও α থাকে যদি এটি সবসময় অপ্টিমাল মানের α ফ্যাক্টরের মধ্যে থাকা কোনো উত্তর বা সমাধান প্রদান করে:

• মিনিমাইজেশনের (minimization) ক্ষেত্রে: অ্যালগরিদমের উত্তর ≤ α × OPT (α ≥ 1)।
• ম্যাক্সিমাইজেশনের (maximization) ক্ষেত্রে: অ্যালগরিদমের উত্তর ≥ OPT / α (α ≥ 1)।

২ (2) রেশিওর মানে হলো আপনি অপ্টিমাল খরচের সর্বোচ্চ দ্বিগুণ খরচে আছেন। ১.৫ (1.5) রেশিওর মানে হলো আপনি অপ্টিমালের চেয়ে সর্বোচ্চ ৫০% ওপরে আছেন। এটি যত ১ এর কাছাকাছি হবে, ফলাফলটি তত ভালো।

ভার্টেক্স কভার (Vertex Cover) — চমৎকার 2-অ্যাপ্রক্সিমেশন

একটি ভার্টেক্স কভার হলো কতগুলো ভার্টেক্সের একটি সেট S যেখানে প্রতিটি এজের (edge) কমপক্ষে একটি এন্ডপয়েন্ট বা প্রান্ত S এ থাকে। (ধরে নিন: মোড়ে মোড়ে পাহারাদার বসানো যাতে প্রতিটি রাস্তায় নজর রাখা যায়।) সবচেয়ে ছোট (minimum) ভার্টেক্স কভার খুঁজে বের করা একটি এনপি-হার্ড (NP-hard) সমস্যা।

2-অ্যাপ্রক্সিমেশন: বারবার যেকোনো একটি কভারবিহীন এজ (u, v) বেছে নিন, u এবং v উভয়কেই কভারে যোগ করুন, এরপর ওই দুটির সাথে যুক্ত সমস্ত এজ সরিয়ে দিন। কোনো এজ বাকি না থাকা পর্যন্ত এটির পুনরাবৃত্তি করুন। এটি \(O(V+E)\) সময়ে সম্পন্ন হয়।

এটি কেন অপ্টিমালের চেয়ে সর্বোচ্চ ২ গুণ বেশি হয়? আমরা যে এজগুলো বেছে নিই সেগুলো একটি ম্যাচিং (matching) তৈরি করে — কোনো দুটি এজের মধ্যে সাধারণ বা শেয়ার করা কোনো ভার্টেক্স থাকে না। আমাদের কভারে নির্বাচিত প্রতি এজের জন্য ২টি করে ভার্টেক্স নেওয়া হয়। কিন্তু যেকোনো বৈধ কভারকে অবশ্যই নির্বাচিত প্রতি এজের জন্য অন্তত ১টি ভার্টেক্স অন্তর্ভুক্ত করতে হবে (সেটিকে কভার করার জন্য)। তাই |আমাদের কভার| ≤ 2 × |OPT|।

মেট্রিক টিএসপি (Metric TSP) — ক্রিস্টোফাইডস 1.5-অ্যাপ্রক্সিমেশন

মেট্রিক ডিস্টেন্সের (metric distances) ট্রাভেলিং সেলসম্যান প্রবলেম (Traveling Salesman Problem) বা যেখানে ট্রায়াঙ্গেল ইনইকুয়ালিটি (triangle inequality) মানা হয় (অর্থাৎ, কোনো শর্টকাটই তৃতীয় কোনো শহরের ভেতর দিয়ে যাওয়ার চেয়ে লম্বা নয়) সেখানে 1.5-অ্যাপ্রক্সিমেশন চমৎকারভাবে কাজ করে:

১. সমস্ত শহরের জন্য একটি মিনিমাম স্প্যানিং ট্রি T খুঁজে বের করুন।
২. T এর মধ্যে অড ডিগ্রি (odd degree) বা বিজোড় ডিগ্রি থাকা ভার্টেক্সগুলোর সেট O চিহ্নিত করুন (হ্যান্ডশেকিং লেমা অনুযায়ী এর সংখ্যা সবসময় একটি জোড় সংখ্যা হবে)।
৩. সেই অড-ডিগ্রি ভার্টেক্সগুলোর ওপর একটি মিনিমাম ওয়েট পারফেক্ট ম্যাচিং M খুঁজে বের করুন।
৪. T এবং M কে একত্রিত করে একটি অয়লারিয়ান মাল্টিগ্রাফ (Eulerian multigraph) তৈরি করুন (এখন প্রতিটি ভার্টেক্সের ইভেন ডিগ্রি বা জোড় ডিগ্রি আছে)।
৫. একটি অয়লার সার্কিট খুঁজে বের করুন, এরপর পুনরাবৃত্তি হওয়া শহরগুলোকে শর্টকাট করে নিন (ট্রায়াঙ্গেল ইনইকুয়ালিটি গ্যারান্টি দেয় যে শর্টকাটগুলো কখনো খরচ বাড়াবে না)।

এর ফলাফল হিসেবে যে ট্যুর বা রুটটি পাওয়া যাবে তার খরচ হবে সর্বোচ্চ 1.5 × OPT।

সেট কভার (Set Cover) — গ্রিডি \(O(\log n)\)-অ্যাপ্রক্সিমেশন

ধরে নিন n সংখ্যক এলিমেন্ট বা উপাদানের একটি সংগ্রহ এবং কিছু সেটের কালেকশন দেওয়া আছে। আপনাকে এমন সবচেয়ে কম সংখ্যক সেট খুঁজে বের করতে হবে যা সমস্ত উপাদানকে কভার করে। গ্রিডি (Greedy) পদ্ধতি: এমন সেটটিকে সবসময় বেছে নিন যা বর্তমান আনকভারড (uncovered) থাকা সবচেয়ে বেশি সংখ্যক উপাদানকে কভার করে। সব উপাদান কভার না হওয়া পর্যন্ত এটি পুনরাবৃত্তি করুন।

এটি H_n = 1 + 1/2 + 1/3 + … + 1/n ≈ ln(n) অ্যাপ্রক্সিমেশন রেশিও অর্জন করে। এবং মজার ব্যাপার হলো: কোনো পলিনোমিয়াল-টাইম (polynomial-time) অ্যালগরিদম এর চেয়ে ভালো করতে পারবে না (যদি না P=NP হয়)। সমস্ত কার্যকর বা ইফিশিয়েন্ট অ্যালগরিদমগুলোর মধ্যে গ্রিডি অ্যালগরিদমই মূলত অপ্টিমাল বা সর্বোত্তম।

PTAS এবং FPTAS

একটি পলিনোমিয়াল-টাইম অ্যাপ্রক্সিমেশন স্কিল (Polynomial-Time Approximation Scheme বা PTAS) আপনার বেছে নেওয়া যেকোনো ε এর জন্য একটি (1+ε)-অ্যাপ্রক্সিমেশন প্রদান করে — ε এর মান যত ছোট হবে, এটি অপ্টিমালের তত কাছাকাছি পৌঁছাবে, কিন্তু এটি বেশ ধীরগতির হতে পারে। অন্যদিকে একটি ফুলি পলিনোমিয়াল-টাইম অ্যাপ্রক্সিমেশন স্কিম (Fully Polynomial-Time Approximation Scheme বা FPTAS) কে অবশ্যই n এবং 1/ε উভয়টির ক্ষেত্রেই পলিনোমিয়াল সময়ে চলতে হয় — যার ফলে এটি অতি ক্ষুদ্র ε এর জন্যও ব্যবহারিক বা প্র্যাক্টিকাল হয়ে ওঠে। 0/1 ন্যাপস্যাক (Knapsack) সমস্যার একটি FPTAS আছে: এটি আইটেমের মানগুলোকে স্কেল এবং রাউন্ড (round) করে, তারপর সরাসরি ডিপি (exact DP) চালায়, যা \(O(n^2/ε)\) সময়ে একটি (1+ε)-অ্যাপ্রক্সিমেশন প্রদান করে।

দ্রষ্টব্য: অ্যাপ্রক্সিমেশন রেশিও একটি ওয়ার্স্ট-কেস গ্যারান্টি (worst-case guarantee) প্রদান করে — এটি কোনো গড় বা এভারেজ নয়। ২ (2) রেশিওযুক্ত একটি অ্যালগরিদম বেশিরভাগ ইনপুটেই একদম সঠিক অপ্টিমাল উত্তরই দিতে পারে, কিন্তু আপনি সবচেয়ে কঠিন বা জটিল কেসগুলোর জন্যও নিশ্চিন্ত থাকতে পারেন।

গ্রিডি ভার্টেক্স কভার — 2-অ্যাপ্রক্সিমেশন

def vertex_cover_2approx(n, edges):
    """Returns a vertex cover guaranteed to be at most 2x optimal."""
    covered = set()
    cover = set()
    for u, v in edges:
        if u not in covered and v not in covered:
            cover.add(u)
            cover.add(v)
            covered.add(u)
            covered.add(v)
    return cover


# Example: path graph 0-1-2-3
edges = [(0,1), (1,2), (2,3)]
cover = vertex_cover_2approx(4, edges)
print("Cover:", cover)         # e.g. {0, 1, 2, 3} or subset
print("Cover size:", len(cover))  # at most 2 * OPT


# Verify: every edge has at least one endpoint in cover
assert all(u in cover or v in cover for u,v in edges)
print("Valid cover: True")
Output
Cover: {0, 1, 2, 3}
Cover size: 4
Valid cover: True

Complexity

🛡️ ভার্টেক্স কভার (গ্রিডি 2-অ্যাপ্রক্সিমেশন)
ইউনিক গেমস কনজেকচার (Unique Games Conjecture) এর অধীনে এই 2 রেশিওটি মূলত টাইট বা আবদ্ধ — খুব সম্ভবত আপনি এর থেকে ভালো কোনো ইফিশিয়েন্ট অ্যালগরিদম পাবেন না
নিশ্চিতভাবে অপ্টিমালের সর্বোচ্চ ২ গুণ (2x) \(O(V + E)\)
✈️ মেট্রিক টিএসপি (ক্রিস্টোফাইডস)
বাধা বা বটলনেক (Bottleneck) হলো মিনিমাম ওয়েট পারফেক্ট ম্যাচিং; ২০২০ সালে (1.5−ε) উন্নতি পাওয়া গেলেও ক্রিস্টোফাইডসই ব্যবহারিক বা প্র্যাক্টিকাল স্ট্যান্ডার্ড হিসেবে রয়ে গেছে
নিশ্চিতভাবে অপ্টিমালের সর্বোচ্চ ১.৫ গুণ (1.5x) \(O(n^3)\)
🗂️ সেট কভার (গ্রিডি)
m = সেটের সংখ্যা; P≠NP শর্তের অধীনে এই রেশিওটিই অপ্টিমাল — আপনি এর চেয়ে ভালো কোনো ইফিশিয়েন্ট অ্যালগরিদম পাবেন না
সর্বোচ্চ ln(n) × অপ্টিমাল \(O(n \cdot m)\)
🎛️ ন্যাপস্যাক FPTAS
গতির বিনিময়ে অ্যাকুরেসি বা নির্ভুলতা কেনা: ১% ভুলের জন্য ε=0.01 সেট করুন; এটি n এবং 1/ε উভয় ক্ষেত্রেই পলিনোমিয়াল
সর্বোচ্চ (1+ε) × অপ্টিমাল \(O(n^2 / ε)\)

ছোট কুইজ

একটি মিনিমাইজেশন প্রবলেমের ক্ষেত্রে একটি অ্যাপ্রক্সিমেশন অ্যালগরিদমের রেশিও 3। এটি আসলে কী হওয়ার নিশ্চয়তা বা গ্যারান্টি দেয়?

পড়া চালিয়ে যান