গ্রাফ অ্যালগরিদম৮ মিনিট পড়া

হ্যামিল্টোনীয় পথ (Hamiltonian Path)

প্রতিটি ঘর ঠিক একবার করে ভ্রমণ করুন — এটি প্রতিটি সেতু ভ্রমণের চেয়ে অনেক বেশি কঠিন
brute force:ভয়াবহ · \(O(n!)\)bitmask DP:এক্সপোনেনশিয়াল · \(O(2^n · n^2)\)NP status:NP-complete

একজন ডেলিভারি ড্রাইভারকে একটি এলাকার প্রতিটি ঘরে ঠিক একবার করে যেতে হবে। এটি শুনতে খুব সহজ মনে হলেও — এর সবচেয়ে ভালো রুট বা পথটি খুঁজে বের করা কম্পিউটার সায়েন্সের অন্যতম কঠিন সমস্যাগুলোর একটি।

একটি হ্যামিল্টোনীয় পথ (Hamiltonian path) হলো এমন একটি পথ যা কোনো গ্রাফের প্রতিটি ভার্টেক্স বা নোডকে ঠিক একবার করে স্পর্শ করে। একটি হ্যামিল্টোনীয় সার্কিট (Hamiltonian circuit) একই কাজ করে এবং সবশেষে শুরুর বিন্দুতে ফিরে আসে। অয়লারীয় পথের (যা প্রতিটি এজ বা ব্রিজকে একবার ভিজিট করে) মতো হ্যামিল্টোনীয় পথের ক্ষেত্রে ডিগ্রি চেক করার মতো কোনো সহজ ট্রিক নেই। এটি খুঁজে বের করতে আপনাকে মূলত প্রতিটি সম্ভাব্য পথ চেষ্টা করেই দেখতে হবে।

এটি অয়লারীয় পথের চেয়ে কেন এত জটিল?

অয়লারীয় পথ: "প্রতিটি সেতু একবার পার হওয়া" → একটি সহজ ডিগ্রি কন্ডিশন ব্যবহার করে \(O(V+E)\) সময়ে সমাধানযোগ্য।

হ্যামিল্টোনীয় পথ: "প্রতিটি বাড়ি একবার ঘুরে আসা" → এনপি-কমপ্লিট (NP-complete)। এর কোনো পলিনোমিয়াল-টাইম অ্যালগরিদম আজও আবিষ্কৃত হয়নি। কোনো একটি গ্রাফে এটি পাওয়া যাবে কিনা তা জানার কোনো সরল নিয়ম নেই। সমস্যা দুটি শুনতে প্রায় একই রকম হলেও, জটিলতার দিক থেকে এদের মধ্যে আকাশ-পাতাল পার্থক্য রয়েছে।

ব্রুট ফোর্স: প্রতিটি রুট চেষ্টা করা

সবচেয়ে সাধারণ পদ্ধতি: ভার্টেক্সগুলোর সব সম্ভাব্য ক্রম চেষ্টা করে দেখা। n সংখ্যক ভার্টেক্সের জন্য n! সংখ্যক ক্রম রয়েছে — ১০টি ভার্টেক্সের জন্য ৩,৬২৮,৮০০টি রুট চেক করতে হবে। ২০টি ভার্টেক্সের জন্য এটি দাঁড়াবে ২.৪ × ১০১৮-এ। ১২টির বেশি ভার্টেক্সের জন্য এটি করা সম্পূর্ণ অসম্ভব।

বিটমাস্ক ডিপি (Bitmask DP): হেল্ড-কার্প ট্রিক

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

এখানে dp[mask][v] = true হবে যদি এমন একটি বৈধ পথ থাকে যা ঠিক mask-এ থাকা ভার্টেক্সগুলোকে কভার করে এবং ভার্টেক্স v-এ গিয়ে শেষ হয়। এখানে বিটমাস্ক ভার্টেক্সগুলোর সাবসেটকে কমপ্যাক্টলি স্টোর করে — যদি ভার্টেক্স i ভিজিট করা হয়ে থাকে তবে i-তম বিট ১ হয়।

বেস কেস বা মূল অবস্থা: প্রতিটি শুরুর ভার্টেক্স v এর জন্য dp[১ << v][v] = true।

ট্রানজিশন বা পরিবর্তন: dp[mask][v] = true হবে যদি মাস্কে এমন কোনো ভার্টেক্স u থাকে (u ≠ v) যার জন্য dp[mask without v][u] = true হয় এবং গ্রাফে (u→v) একটি এজ থাকে।

উত্তর: যদি যেকোনো v এর জন্য dp[(১<

এর জটিলতা হলো \(O(2^n · n^2)\) — এটিও একটি এক্সপোনেনশিয়াল টাইম গ্রোথ, তবে \(O(n!)\) এবং \(O(2^n · n^2)\) এর মধ্যে পার্থক্য বিশাল। n=২০ এর জন্য: ২০! ≈ ২.৪×১০১৮ যেখানে ২২০ × ৪০০ ≈ ৪×১০৮। অর্থাৎ ডিপি পদ্ধতিটি ব্রুট ফোর্সের চেয়ে প্রায় ১০০ কোটি গুণ বেশি দ্রুত!

টিএসপি (TSP): যখন এজগুলোর ওজন থাকে

ট্রাভেলিং সেলসম্যান প্রবলেম (Travelling Salesman Problem) সমস্যাটি হ্যামিল্টোনীয় সার্কিটেরই একটি বর্ধিত রূপ যেখানে প্রতিটি এজের একটি খরচ বা ওয়েট থাকে: আপনাকে সর্বনিম্ন খরচের সার্কিটটি খুঁজে বের করতে হবে। একই ডিপি পদ্ধতি এখানেও কাজ করে — শুধু বুলিয়ান মানের বদলে সর্বনিম্ন খরচ স্টোর করতে হয়। এর জটিলতাও \(O(2^n · n^2)\) এবং এটিও এনপি-হার্ড (NP-hard)।

বিশাল n এর জন্য তখন অ্যাপ্রক্সিমেশন অ্যালগরিদম (approximation algorithms) ব্যবহার করা হয়। মেট্রিক টিএসপি (যেখানে দূরত্বগুলো ত্রিভুজ অসমতা বা triangle inequality মেনে চলে) এর জন্য ক্রিস্টোফাইডস অ্যালগরিদম (Christofides algorithm) এমন একটি সমাধান দেয় যা নিখুঁত উত্তরের চেয়ে সর্বোচ্চ ৫০% বেশি হতে পারে। এমএসটি ব্যবহার করে খুব সহজেই একটি '২-অ্যাপ্রক্সিমেশন' সমাধান পাওয়া যায়।

দ্রষ্টব্য: অয়লারীয় এবং হ্যামিল্টোনীয় পথের মধ্যকার পার্থক্য কম্পিউটার সায়েন্সে একটি বিখ্যাত শিক্ষা: যা শুনতে প্রায় একই রকম মনে হয়, তা আসলে জটিলতার দিক থেকে বিশাল ভিন্ন হতে পারে। একটি হলো \(O(V+E)\); আর অন্যটি সঠিক সমাধান বের করতে মহাবিশ্বের আয়ুষ্কালের সমান সময় নিতে পারে।

হ্যামিল্টোনীয় পথ — বিটমাস্ক ডিপি (Bitmask DP)

def hamiltonian_path(n, edges):
    adj = [[False]*n for _ in range(n)]
    for u, v in edges:
        adj[u][v] = True


    # dp[mask][v] = True if we can visit nodes in mask ending at v
    dp = [[False]*n for _ in range(1<<n)]
    for v in range(n):
        dp[1<<v][v] = True


    for mask in range(1<<n):
        for v in range(n):
            if not dp[mask][v]: continue
            if not (mask >> v & 1): continue
            for u in range(n):
                if mask >> u & 1: continue  # already visited
                if adj[v][u]:
                    dp[mask|(1<<u)][u] = True


    full = (1<<n) - 1
    return any(dp[full][v] for v in range(n))


# Path exists: 0->1->2->3
edges = [(0,1),(1,2),(2,3)]
print(hamiltonian_path(4, edges))  # True


# No path: 0->1, 0->2, but node 3 is disconnected
edges2 = [(0,1),(0,2)]
print(hamiltonian_path(4, edges2)) # False
Output
True
False

Complexity

💥 ব্রুট ফোর্স (সব পারমুটেশন)
২০! ≈ ২.৪×১০১৮ — যদি আপনি প্রতি সেকেন্ডে ১০০ কোটি রুট চেক করেন, তবে এটি শেষ করতে ৭৫ বছর সময় লাগবে
ফ্যাক্টোরিয়াল — n≈১২ এর বেশি সম্ভব নয় \(O(n!)\)
⚡ বিটমাস্ক ডিপি (Held-Karp)
২২০ × ৪০০ ≈ ৪×১০৮ — যা মাত্র কয়েক সেকেন্ডেই সম্পন্ন করা যায়; এতে মেমোরি প্রয়োজন হয় \(O(2^n · n)\)
এক্সপোনেনশিয়াল কিন্তু n≈২০ পর্যন্ত করা সম্ভব \(O(2^n · n^2)\)
🏷️ এনপি-কমপ্লিট (NP-complete)
যদি এর কোনো পলিনোমিয়াল সমাধান পাওয়া যায়, তবে সেটি P=NP প্রমাণ করবে — যা গণিতের অন্যতম অমীমাংসিত রহস্য
কোনো পলিনোমিয়াল অ্যালগরিদম জানা নেই NP-complete
📏 মেট্রিক টিএসপি সঠিকতার অনুমান
Christofides অ্যালগরিদম ১.৫ গুণ বা তার চেয়েও নিখুঁত ফলাফল দিতে পারে; সাধারণ এমএসটি অ্যালগরিদম ২ গুণ পর্যন্ত নির্ভুল হতে পারে
দ্রুত এবং নিখুঁত ফলাফলের কাছাকাছি \(O(E \log E)\)

ছোট কুইজ

একটি ডেলিভারি অ্যাপে ১৫টি স্টপ বা গন্তব্য আছে। কেন ব্রুট ফোর্স পদ্ধতি এখানে একেবারেই অকার্যকর?

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

অয়লারীয় পথ ও সার্কিট (Eulerian Path & Circuit)
আপনি কি প্রতিটি সেতু বা ব্রিজ ঠিক একবার করে পার হতে পারবেন? ১৭৩৬ সালে অয়লার এই প্রশ্নের উত্তর দিয়েছিলেন
→
বিটমাস্ক ডিপি (Bitmask DP)
মাত্র একটি সিঙ্গেল পূর্ণসংখ্যায় বা ইনটিজারে সমস্ত সম্ভাব্য সাবসেটের পছন্দগুলো ট্র্যাক করুন
→
এনপি (NP), এনপি-কমপ্লিট (NP-Complete), এনপি-হার্ড (NP-Hard)
দ্য মিলিয়ন-ডলার প্রশ্ন: কোনো উত্তর খুঁজে বের করা কি কখনো তা যাচাই করার মতো সহজ হতে পারে?
→