ক্যাপস্টোন — অ্যালগরিদম ডিজাইন, অ্যানালাইসিস ও তুলনা
এই পাঠে যা শিখবেন
- একই সমস্যায় এক্স্যাক্ট, DP, গ্রিডি ও অ্যাপ্রক্সিমেশন পদ্ধতি পাশাপাশি বসিয়ে তাদের ট্রেড-অফ প্রত্যক্ষভাবে দেখা
- Held-Karp বিটমাস্ক DP-র রিকারেন্স ও বাস্তবায়ন — এবং কেন এটি ব্রুট-ফোর্সের চেয়ে দ্রুত তবু এখনও exponential
- নিয়ারেস্ট-নেইবার গ্রিডি ও MST-ভিত্তিক ২-অ্যাপ্রক্সিমেশনের মধ্যে পার্থক্য — একটির কোনো প্রমাণিত গ্যারান্টি নেই, আরেকটির আছে
- একটি জেনুইনভাবে কম্পিউট-করা তুলনামূলক সারাংশ তৈরি করা, যা হার্ডকোড করা টেক্সট নয়, বরং বাস্তব কোড থেকে সরাসরি আসা ফলাফল
১ · সমস্যা — ট্র্যাভেলিং সেলসম্যান প্রবলেম (TSP)
TSP: $n$টি শহরের মধ্যে একটি চক্রাকার ট্যুর খুঁজে বের করা যা প্রতিটি শহরে ঠিক একবার যায় এবং শুরুর শহরে ফিরে আসে, যেখানে ট্যুরের মোট দূরত্ব সর্বনিম্ন। আমরা শহরগুলোকে ২D স্থানাঙ্ক হিসেবে নিচ্ছি এবং দূরত্ব মাপছি ইউক্লিডীয় (Euclidean) দূরত্ব দিয়ে — এর মানে ট্রায়াঙ্গেল ইনইকুয়ালিটি ($d(a,c) \le d(a,b) + d(b,c)$) স্বয়ংক্রিয়ভাবে সত্য থাকে, যা একে একটি মেট্রিক TSP ইনস্ট্যান্স করে তোলে — M12/L52-এর অ্যাপ্রক্সিমেশনের পূর্বশর্ত।
এই সমস্যাটি বেছে নেওয়ার কারণ: এটি একই সাথে D&C/ব্রুট-ফোর্স বেসলাইন (M4/M8), DP (M6), গ্রিডি (M5), এবং অ্যাপ্রক্সিমেশন (M12) — কোর্সের প্রায় প্রতিটি প্যারাডাইমকে একটি একক সমস্যায় স্বাভাবিকভাবে ফিট করায়। নিচে পাঁচটি ধাপে, পাঁচটি কোড সেলে, একই চারটি ছোট শহর-সেটে (আকার $n = 6, 7, 8, 8$) এই সবকটি পদ্ধতি চালিয়ে দেখা হবে।
২ · ধাপ ১ — ব্রুট-ফোর্স এক্স্যাক্ট সমাধান (ভিত্তি বেসলাইন)
যেহেতু TSP-তে একটি ট্যুরের ঘূর্ণন (rotation) ও দিক পরিবর্তন করলেও দূরত্ব একই থাকে, শহর $0$-কে সবসময় শুরু হিসেবে ফিক্স করে বাকি $n-1$টি শহরের সব পারমুটেশন চেক করাই যথেষ্ট — তাই মোট $(n-1)!$ পারমুটেশন লাগে, $n!$ নয় (তবু ফ্যাক্টরিয়াল গ্রোথ থেকেই যায়)। এটি M4/M8-এর "সব সম্ভাবনা তালাশ করা" এক্স্যাক্ট বেসলাইনের ধ্রুপদী উদাহরণ — $n \le 8$-এর জন্য ব্যবহারযোগ্য, কিন্তু $n = 15$ হলেই $(14)! \approx 8.7 \times 10^{10}$ পারমুটেশন হয়ে যাবে।
import math
from itertools import permutations
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def build_matrix(points):
n = len(points)
return [[dist(points[i], points[j]) for j in range(n)] for i in range(n)]
# চারটি ছোট, স্থির শহর-সেট (Euclidean স্থানাঙ্ক -- তাই ট্রায়াঙ্গেল ইনইকুয়ালিটি
# স্বয়ংক্রিয়ভাবে সত্য থাকে, মেট্রিক TSP-এর পূর্বশর্ত)
instances = [
[(45.2, 56.0), (92.4, 46.6), (50.8, 58.7), (18.5, 51.2), (63.0, 79.3), (9.4, 30.3)],
[(9.1, 81.0), (69.3, 4.2), (98.2, 96.5), (65.4, 61.6), (15.7, 1.5), (52.8, 6.0), (19.0, 24.2)],
[(3.0, 46.4), (44.1, 84.2), (51.9, 64.0), (50.0, 66.2), (45.7, 27.8), (99.8, 99.6), (84.0, 70.8), (31.5, 23.0)],
[(23.6, 10.3), (39.6, 15.5), (6.7, 40.2), (91.8, 80.0), (76.5, 22.2), (53.7, 27.7), (17.3, 10.6), (21.4, 92.7)],
]
def brute_force_tsp(D):
n = len(D)
best_cost, best_perm, count = math.inf, None, 0
for perm in permutations(range(1, n)):
count += 1
tour = (0,) + perm
cost = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
if cost < best_cost:
best_cost, best_perm = cost, tour
return best_cost, best_perm, count
print(f"{'#':>2} {'n':>3} | {'অপটিমাল কস্ট':>14} {'চেক করা পারমুটেশন':>18} {'(n-1)!':>8}")
for idx, pts in enumerate(instances):
D = build_matrix(pts)
cost, perm, count = brute_force_tsp(D)
print(f"{idx:>2} {len(pts):>3} | {cost:>14.3f} {count:>18} {math.factorial(len(pts)-1):>8}")৩ · ধাপ ২ — Held-Karp বিটমাস্ক DP (একই এক্স্যাক্ট উত্তর, কম কাজে)
Held-Karp DP-র মূল ধারণা: $C(S, j)$ = শহর $0$ থেকে শুরু করে ঠিক সেট $S$-এর সবগুলো শহর ভ্রমণ করে $j$-তে শেষ করার সর্বনিম্ন খরচ, যেখানে $j \in S$। এর optimal substructure স্পষ্ট: একটি অপটিমাল $(S, j)$-পথ অবশ্যই কোনো $(S \setminus \{j\}, k)$-এর একটি অপটিমাল পথের পরে $k \to j$ ধার যোগ করেই তৈরি — রিকারেন্স:
$$C(S, j) = \min_{k \in S \setminus \{j\},\ k \ne 0} \big( C(S \setminus \{j\}, k) + d(k, j) \big), \qquad C(\{0\}, 0) = 0$$আর ওভারল্যাপিং সাব-প্রবলেমও স্পষ্ট: একই $(S, j)$ জোড়া বিভিন্ন সম্ভাব্য শেষ-ধাপের হিসাব থেকে বারবার প্রয়োজন হয় — এই পুনরাবৃত্তিই DP-কে ব্রুট-ফোর্সের চেয়ে সাশ্রয়ী করে তোলে। সম্ভাব্য অবস্থা $(S, j)$-এর সংখ্যা $O(n \cdot 2^n)$ (প্রতিটি সাবসেট $S$-এর জন্য $n$টি সম্ভাব্য শেষ-শহর), আর প্রতিটি অবস্থা থেকে $O(n)$টি ট্রানজিশন চেক হয় — তাই মোট সময় জটিলতা $O(n^2 \cdot 2^n)$, যা $O(n!)$-এর চেয়ে $n$ বড় হলে বহুগুণ দ্রুত (যদিও এখনও exponential, পলিনমিয়াল নয়)। নিচের কোডে একই চারটি ইনস্ট্যান্সে DP চালিয়ে ব্রুট-ফোর্সের সাথে হুবহু মেলানো হয়েছে, এবং প্রকৃত অবস্থা-সংখ্যা ও ট্রানজিশন-সংখ্যা গণনা করে $(n-1)!$-এর সাথে তুলনা করা হয়েছে।
import math
from itertools import permutations
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def build_matrix(points):
n = len(points)
return [[dist(points[i], points[j]) for j in range(n)] for i in range(n)]
instances = [
[(45.2, 56.0), (92.4, 46.6), (50.8, 58.7), (18.5, 51.2), (63.0, 79.3), (9.4, 30.3)],
[(9.1, 81.0), (69.3, 4.2), (98.2, 96.5), (65.4, 61.6), (15.7, 1.5), (52.8, 6.0), (19.0, 24.2)],
[(3.0, 46.4), (44.1, 84.2), (51.9, 64.0), (50.0, 66.2), (45.7, 27.8), (99.8, 99.6), (84.0, 70.8), (31.5, 23.0)],
[(23.6, 10.3), (39.6, 15.5), (6.7, 40.2), (91.8, 80.0), (76.5, 22.2), (53.7, 27.7), (17.3, 10.6), (21.4, 92.7)],
]
def brute_force_tsp(D):
n = len(D)
best_cost, count = math.inf, 0
for perm in permutations(range(1, n)):
count += 1
tour = (0,) + perm
cost = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
if cost < best_cost:
best_cost = cost
return best_cost, count
def held_karp(D):
# dp[(mask, j)] = শহর 0 থেকে শুরু করে mask সেটের সবগুলো শহর ভ্রমণ করে j-তে
# শেষ করার সর্বনিম্ন খরচ -- বিটমাস্ক DP, ক্লাসিক Held-Karp রিকারেন্স
n = len(D)
FULL = 1 << n
dp = {(1, 0): 0.0}
transitions = 0
for mask in range(1, FULL):
if not (mask & 1):
continue
for j in range(n):
if not (mask & (1 << j)) or (mask, j) not in dp:
continue
cur_cost = dp[(mask, j)]
for k in range(n):
if mask & (1 << k):
continue
transitions += 1
new_mask = mask | (1 << k)
new_cost = cur_cost + D[j][k]
if (new_mask, k) not in dp or new_cost < dp[(new_mask, k)]:
dp[(new_mask, k)] = new_cost
full_mask = FULL - 1
best_cost = min(dp[(full_mask, j)] + D[j][0] for j in range(1, n) if (full_mask, j) in dp)
return best_cost, len(dp), transitions
print(f"{'#':>2} {'n':>3} | {'ব্রুট-ফোর্স':>12} {'Held-Karp':>10} {'মিলল?':>7} | {'BF পারমুটেশন':>13} {'HK states':>10} {'HK transitions':>15} {'n^2*2^n':>9}")
for idx, pts in enumerate(instances):
D = build_matrix(pts)
bf_cost, bf_count = brute_force_tsp(D)
hk_cost, hk_states, hk_trans = held_karp(D)
n = len(pts)
match = abs(bf_cost - hk_cost) < 1e-6
print(f"{idx:>2} {n:>3} | {bf_cost:>12.3f} {hk_cost:>10.3f} {str(match):>7} | {bf_count:>13} {hk_states:>10} {hk_trans:>15} {n*n*2**n:>9}")True প্রতিটিতে) — এটাই DP বাস্তবায়নের সঠিকতার প্রকৃত প্রমাণ, শুধু "রিকারেন্স ঠিক মনে হচ্ছে"
বলে বিশ্বাস নয়। রাজ্য-সংখ্যা (dict-এ প্রকৃত এন্ট্রি) তাত্ত্বিক আপার-বাউন্ড $n^2 \cdot 2^n$-এর চেয়ে অনেক কম
(যেমন $n=8$-এ $449$ বনাম $16384$), কারণ শুধু $0$ অন্তর্ভুক্ত এমন সাবসেটই বিবেচ্য। তবু, $n=8$-এ ব্রুট-ফোর্সের
$5040$টি পারমুটেশনের বিপরীতে Held-Karp-এর মাত্র $1351$টি ট্রানজিশন লাগে — বাস্তব, পরিমাপযোগ্য সাশ্রয়, যদিও
উভয়ই শেষ পর্যন্ত exponential থেকে যায়।
৪ · ধাপ ৩ — নিয়ারেস্ট-নেইবার গ্রিডি হিউরিস্টিক
M5-এর গ্রিডি টেমপ্লেট প্রয়োগ করে সবচেয়ে সরল হিউরিস্টিক: বর্তমান শহর থেকে সবচেয়ে কাছের অভ্রমিত শহরে যাওয়া, পুনরাবৃত্তি করা। এটি $O(n^2)$ সময়ে চলে — হাজার হাজার শহরেও ব্যবহারযোগ্য — কিন্তু এর জন্য কোনো এক্সচেঞ্জ-আর্গুমেন্ট প্রমাণ নেই এবং সাধারণ (non-metric) গ্রাফে এর কোনো প্রমাণিত অপটিমাম-অনুপাত বাউন্ড নেই — এমনকি মেট্রিক ক্ষেত্রেও এর ওয়ার্স্ট-কেস রেশিও $\Theta(\log n)$ হতে পারে বলে জানা যায় (এই কোর্সের পরিধির বাইরের একটি ফলাফল)। নিচের কোডে একই চারটি ইনস্ট্যান্সে এর প্রকৃত গ্যাপ ব্রুট-ফোর্স অপটিমামের বিপরীতে গণনা করা হয়েছে।
import math
from itertools import permutations
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def build_matrix(points):
n = len(points)
return [[dist(points[i], points[j]) for j in range(n)] for i in range(n)]
instances = [
[(45.2, 56.0), (92.4, 46.6), (50.8, 58.7), (18.5, 51.2), (63.0, 79.3), (9.4, 30.3)],
[(9.1, 81.0), (69.3, 4.2), (98.2, 96.5), (65.4, 61.6), (15.7, 1.5), (52.8, 6.0), (19.0, 24.2)],
[(3.0, 46.4), (44.1, 84.2), (51.9, 64.0), (50.0, 66.2), (45.7, 27.8), (99.8, 99.6), (84.0, 70.8), (31.5, 23.0)],
[(23.6, 10.3), (39.6, 15.5), (6.7, 40.2), (91.8, 80.0), (76.5, 22.2), (53.7, 27.7), (17.3, 10.6), (21.4, 92.7)],
]
def brute_force_optimal(D):
n = len(D)
best_cost = math.inf
for perm in permutations(range(1, n)):
tour = (0,) + perm
cost = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
if cost < best_cost:
best_cost = cost
return best_cost
def nearest_neighbor(D):
n = len(D)
visited = [False] * n
visited[0] = True
cur, total = 0, 0.0
for _ in range(n - 1):
best_j, best_d = None, math.inf
for j in range(n):
if not visited[j] and D[cur][j] < best_d:
best_j, best_d = j, D[cur][j]
visited[best_j] = True
total += best_d
cur = best_j
total += D[cur][0]
return total
print(f"{'#':>2} {'n':>3} | {'অপটিমাল':>10} {'নিয়ারেস্ট-নেইবার':>17} {'গ্যাপ (x)':>10} {'গ্যাপ (%)':>10}")
for idx, pts in enumerate(instances):
D = build_matrix(pts)
opt = brute_force_optimal(D)
nn = nearest_neighbor(D)
ratio = nn / opt
print(f"{idx:>2} {len(pts):>3} | {opt:>10.3f} {nn:>17.3f} {ratio:>10.3f} {100*(ratio-1):>9.1f}%")৫ · ধাপ ৪ — MST-ভিত্তিক ২-অ্যাপ্রক্সিমেশন (প্রমাণিত গ্যারান্টিসহ)
M12/L52-এর ক্লাসিক নির্মাণ: (১) সব শহরের উপর একটি মিনিমাম স্প্যানিং ট্রি বানাও (প্রিমের অ্যালগরিদম, M5/L23-এর কাট-প্রপার্টি ব্যবহার করে), (২) MST-তে একটি DFS প্রিঅর্ডার ওয়াক করো, (৩) পুনরাবৃত্ত শহর শর্টকাট করো (ট্রায়াঙ্গেল ইনইকুয়ালিটির কারণে শর্টকাট করলে দূরত্ব কখনো বাড়ে না)। প্রমাণের সংক্ষিপ্তসার:
- অপটিমাল ট্যুর থেকে যেকোনো একটি ধার সরালে একটি স্প্যানিং ট্রি পাওয়া যায়, তাই $\text{MST-খরচ} \le \text{OPT}$।
- MST-এর প্রতিটি ধার দুইবার ভ্রমণ করে (DFS-এ যাওয়া-আসা) একটি "ডাবলড" ওয়াক তৈরি করলে তার খরচ $2 \times \text{MST-খরচ} \le 2 \times \text{OPT}$।
- শর্টকাট (একই শহর দ্বিতীয়বার ভ্রমণ না করে সরাসরি পরবর্তী নতুন শহরে যাওয়া) ট্রায়াঙ্গেল ইনইকুয়ালিটির কারণে খরচ কখনো বাড়ায় না — তাই চূড়ান্ত ট্যুরের খরচও $\le 2 \times \text{OPT}$।
নিচের কোডে এই $\le 2\times$ বাউন্ডটি একই চারটি ইনস্ট্যান্সে সরাসরি গণনা করে যাচাই করা হয়েছে, এবং নিয়ারেস্ট-নেইবারের সাথে পাশাপাশি রাখা হয়েছে।
import math
from itertools import permutations
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def build_matrix(points):
n = len(points)
return [[dist(points[i], points[j]) for j in range(n)] for i in range(n)]
instances = [
[(45.2, 56.0), (92.4, 46.6), (50.8, 58.7), (18.5, 51.2), (63.0, 79.3), (9.4, 30.3)],
[(9.1, 81.0), (69.3, 4.2), (98.2, 96.5), (65.4, 61.6), (15.7, 1.5), (52.8, 6.0), (19.0, 24.2)],
[(3.0, 46.4), (44.1, 84.2), (51.9, 64.0), (50.0, 66.2), (45.7, 27.8), (99.8, 99.6), (84.0, 70.8), (31.5, 23.0)],
[(23.6, 10.3), (39.6, 15.5), (6.7, 40.2), (91.8, 80.0), (76.5, 22.2), (53.7, 27.7), (17.3, 10.6), (21.4, 92.7)],
]
def brute_force_optimal(D):
n = len(D)
best_cost = math.inf
for perm in permutations(range(1, n)):
tour = (0,) + perm
cost = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
if cost < best_cost:
best_cost = cost
return best_cost
def nearest_neighbor(D):
n = len(D)
visited = [False] * n
visited[0] = True
cur, total = 0, 0.0
for _ in range(n - 1):
best_j, best_d = None, math.inf
for j in range(n):
if not visited[j] and D[cur][j] < best_d:
best_j, best_d = j, D[cur][j]
visited[best_j] = True
total += best_d
cur = best_j
total += D[cur][0]
return total
def prim_mst(D):
# প্রিমের অ্যালগরিদম -- M5/L23-এ প্রমাণিত কাট-প্রপার্টি ব্যবহার করে
n = len(D)
in_tree = [False] * n
key = [math.inf] * n
key[0] = 0.0
parent = [-1] * n
edges = []
for _ in range(n):
u = min((v for v in range(n) if not in_tree[v]), key=lambda v: key[v])
in_tree[u] = True
if parent[u] != -1:
edges.append((parent[u], u))
for v in range(n):
if not in_tree[v] and D[u][v] < key[v]:
key[v], parent[v] = D[u][v], u
return edges
def mst_2approx(D):
# M12/L52-এর MST-ভিত্তিক ২-অ্যাপ্রক্সিমেশন: MST বানাও, DFS প্রিঅর্ডার ওয়াক করো,
# পুনরাবৃত্ত শহর শর্টকাট করো -- ট্রায়াঙ্গেল ইনইকুয়ালিটির উপর নির্ভরশীল
n = len(D)
edges = prim_mst(D)
adj = {i: [] for i in range(n)}
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
order = []
def dfs(u):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
dfs(v)
dfs(0)
return sum(D[order[i]][order[(i + 1) % n]] for i in range(n))
print(f"{'#':>2} {'n':>3} | {'অপটিমাল':>10} {'NN':>10} {'MST-অ্যাপ্রক্স':>14} {'অ্যাপ্রক্স গ্যাপ (x)':>19} {'<=2x বাউন্ড':>11}")
for idx, pts in enumerate(instances):
D = build_matrix(pts)
opt = brute_force_optimal(D)
nn = nearest_neighbor(D)
approx = mst_2approx(D)
ratio = approx / opt
within = ratio <= 2.0
print(f"{idx:>2} {len(pts):>3} | {opt:>10.3f} {nn:>10.3f} {approx:>14.3f} {ratio:>19.3f} {str(within):>11}")<=2x বাউন্ড কলামে True — রেশিও যথাক্রমে $1.031$, $1.000$,
$1.086$ ও $1.313$, প্রতিটিই প্রমাণিত $2.0$ বাউন্ডের অনেক নিচে। লক্ষণীয়, চতুর্থ ইনস্ট্যান্সে ($n=8$)
MST-অ্যাপ্রক্সিমেশনের রেশিও ($1.313$) নিয়ারেস্ট-নেইবারের ($1.032$) চেয়ে খারাপ — অর্থাৎ একটি নির্দিষ্ট
ইনস্ট্যান্সে প্রমাণহীন হিউরিস্টিক প্রমাণিত অ্যাপ্রক্সিমেশনের চেয়ে ভালো ফল দিতে পারে। কিন্তু এটি MST-পদ্ধতির
মূল্য কমায় না — এর গুরুত্ব এই যে এটি প্রতিটি মেট্রিক ইনস্ট্যান্সে $2\times$-এর বেশি খারাপ
হবে না এই নিশ্চয়তা দেয়, যেখানে নিয়ারেস্ট-নেইবারের এমন কোনো নিশ্চয়তা নেই (এটি ভাগ্যক্রমে ভালো করেছে,
নাকি সবসময় করবে তা প্রমাণ ছাড়া বলা যায় না)।
৬ · ধাপ ৫ — চূড়ান্ত সারাংশ (সত্যিকারের কম্পিউট করা ফলাফল থেকে)
নিচের কোড সেলটি উপরের চারটি পদ্ধতিই আবার নতুন করে চালায় এবং তাদের প্রকৃত ফলাফল থেকে সরাসরি একটি সারাংশ টেবিল তৈরি করে — কোনো সংখ্যাই হার্ডকোড করা টেক্সট নয়, প্রতিটি এই একই রানে গণনা করা।
import math
from itertools import permutations
def dist(p, q):
return math.hypot(p[0] - q[0], p[1] - q[1])
def build_matrix(points):
n = len(points)
return [[dist(points[i], points[j]) for j in range(n)] for i in range(n)]
instances = [
[(45.2, 56.0), (92.4, 46.6), (50.8, 58.7), (18.5, 51.2), (63.0, 79.3), (9.4, 30.3)],
[(9.1, 81.0), (69.3, 4.2), (98.2, 96.5), (65.4, 61.6), (15.7, 1.5), (52.8, 6.0), (19.0, 24.2)],
[(3.0, 46.4), (44.1, 84.2), (51.9, 64.0), (50.0, 66.2), (45.7, 27.8), (99.8, 99.6), (84.0, 70.8), (31.5, 23.0)],
[(23.6, 10.3), (39.6, 15.5), (6.7, 40.2), (91.8, 80.0), (76.5, 22.2), (53.7, 27.7), (17.3, 10.6), (21.4, 92.7)],
]
def brute_force_tsp(D):
n = len(D)
best_cost = math.inf
for perm in permutations(range(1, n)):
tour = (0,) + perm
cost = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
if cost < best_cost:
best_cost = cost
return best_cost
def held_karp(D):
n = len(D)
FULL = 1 << n
dp = {(1, 0): 0.0}
for mask in range(1, FULL):
if not (mask & 1):
continue
for j in range(n):
if not (mask & (1 << j)) or (mask, j) not in dp:
continue
cur_cost = dp[(mask, j)]
for k in range(n):
if mask & (1 << k):
continue
new_mask = mask | (1 << k)
new_cost = cur_cost + D[j][k]
if (new_mask, k) not in dp or new_cost < dp[(new_mask, k)]:
dp[(new_mask, k)] = new_cost
full_mask = FULL - 1
return min(dp[(full_mask, j)] + D[j][0] for j in range(1, n) if (full_mask, j) in dp)
def nearest_neighbor(D):
n = len(D)
visited = [False] * n
visited[0] = True
cur, total = 0, 0.0
for _ in range(n - 1):
best_j, best_d = None, math.inf
for j in range(n):
if not visited[j] and D[cur][j] < best_d:
best_j, best_d = j, D[cur][j]
visited[best_j] = True
total += best_d
cur = best_j
total += D[cur][0]
return total
def prim_mst(D):
n = len(D)
in_tree = [False] * n
key = [math.inf] * n
key[0] = 0.0
parent = [-1] * n
edges = []
for _ in range(n):
u = min((v for v in range(n) if not in_tree[v]), key=lambda v: key[v])
in_tree[u] = True
if parent[u] != -1:
edges.append((parent[u], u))
for v in range(n):
if not in_tree[v] and D[u][v] < key[v]:
key[v], parent[v] = D[u][v], u
return edges
def mst_2approx(D):
n = len(D)
edges = prim_mst(D)
adj = {i: [] for i in range(n)}
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
order = []
def dfs(u):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
dfs(v)
dfs(0)
return sum(D[order[i]][order[(i + 1) % n]] for i in range(n))
# --- সব ইনস্ট্যান্সে সব চারটি পদ্ধতি চালিয়ে প্রকৃত ফলাফল জোগাড় করা ---
rows = []
for pts in instances:
D = build_matrix(pts)
opt_bf = brute_force_tsp(D)
opt_hk = held_karp(D)
nn = nearest_neighbor(D)
approx = mst_2approx(D)
rows.append({
'n': len(pts), 'opt_bf': opt_bf, 'opt_hk': opt_hk, 'nn': nn, 'approx': approx,
})
def summarize(matches_fn, gap_fn):
all_match = all(matches_fn(r) for r in rows)
gaps = [gap_fn(r) for r in rows]
return all_match, max(gaps), sum(gaps) / len(gaps)
methods = [
("ব্রুট-ফোর্স (Exact)", lambda r: True, lambda r: 0.0, "O(n!) -- n=8-এর বেশি হলেই অচল"),
("Held-Karp DP (Exact)", lambda r: abs(r['opt_hk'] - r['opt_bf']) < 1e-6,
lambda r: 100 * (r['opt_hk'] / r['opt_bf'] - 1), "O(n^2 * 2^n) -- n~20-25 পর্যন্ত ব্যবহারযোগ্য"),
("Nearest-Neighbor (Greedy)", lambda r: abs(r['nn'] - r['opt_bf']) < 1e-6,
lambda r: 100 * (r['nn'] / r['opt_bf'] - 1), "O(n^2) -- হাজার হাজার শহরেও দ্রুত, কিন্তু কোনো প্রমাণিত রেশিও নেই"),
("MST-ভিত্তিক ২-অ্যাপ্রক্স", lambda r: abs(r['approx'] - r['opt_bf']) < 1e-6,
lambda r: 100 * (r['approx'] / r['opt_bf'] - 1), "O(n^2 log n) -- বড় n-এও দ্রুত, প্রমাণিত <=2x গ্যারান্টি"),
]
print(f"{'পদ্ধতি':>28} | {'সবসময় অপটিমাল?':>16} | {'গড় গ্যাপ':>9} | {'সর্বোচ্চ গ্যাপ':>13} | স্কেলেবিলিটি")
for name, match_fn, gap_fn, note in methods:
always_match, max_gap, avg_gap = summarize(match_fn, gap_fn)
print(f"{name:>28} | {str(always_match):>16} | {avg_gap:>8.1f}% | {max_gap:>12.1f}% | {note}")একই সমস্যাকে চারটি ভিন্ন দৃষ্টিকোণ থেকে সমাধান করে আমরা এই পুরো কোর্সের কেন্দ্রীয় বার্তাটি প্রত্যক্ষভাবে দেখলাম: একটি অ্যালগরিদম ডিজাইন করা (ব্রুট-ফোর্স, DP, গ্রিডি, বা অ্যাপ্রক্সিমেশন লেখা) এবং সেটি বিশ্লেষণ করা (এটি সবসময় সঠিক কিনা প্রমাণ করা, এর জটিলতা ও — প্রযোজ্য হলে — তার অপটিমাম থেকে গ্যাপের একটি প্রমাণিত সীমা বের করা) দুটি আলাদা কিন্তু সমান গুরুত্বপূর্ণ দক্ষতা। M1-এ আমরা এই পার্থক্যটি প্রথম দেখেছিলাম একটি সাধারণ $O(n)$ বনাম $O(n^2)$ উদাহরণে — L57-এ এসে সেই একই পার্থক্যটি একটি সম্পূর্ণ, বাস্তব, NP-hard সমস্যার চারটি সমাধানে রিগোরাসভাবে প্রয়োগ করে দেখানো হলো। এটাই একজন প্রকৃত অ্যালগরিদম ডিজাইনারের কাজ — প্রতিটি দাবির পেছনে একটি প্রমাণ বা একটি জেনুইন কম্পিউটেশনাল যাচাই থাকা, "কাজ করছে মনে হচ্ছে" কখনো যথেষ্ট না হওয়া।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ চতুর্থ ইনস্ট্যান্সে নিয়ারেস্ট-নেইবার ($1.032\times$) MST-অ্যাপ্রক্সিমেশনের ($1.313\times$) চেয়ে ভালো ফল দিয়েছে — তাহলে কি আমাদের সবসময় নিয়ারেস্ট-নেইবার ব্যবহার করা উচিত?
না — এটাই ঠিক সেই ভুল যা L56-এ আলোচনা করা হয়েছে: একটি নির্দিষ্ট ইনস্ট্যান্সে ভালো ফল দেখে সাধারণীকরণ করা বিপজ্জনক। MST-অ্যাপ্রক্সিমেশনের মূল্য এই নয় যে এটি প্রতিটি ইনস্ট্যান্সে নিয়ারেস্ট-নেইবারকে হারায় — বরং এটি প্রতিটি সম্ভাব্য মেট্রিক ইনস্ট্যান্সে $2\times$-এর বেশি খারাপ হবে না এই নিশ্চয়তা দেয়, যা প্রমাণ করা হয়েছে। নিয়ারেস্ট-নেইবারের এমন কোনো প্রমাণ নেই — এটি একটি বিশেষভাবে নির্মিত (adversarial) ইনস্ট্যান্সে অনেক বেশি খারাপ করতে পারে যেখানে MST-অ্যাপ্রক্সিমেশন এখনও তার $2\times$ গ্যারান্টির মধ্যে থাকবে। ব্যবহারিক সিদ্ধান্তে প্রায়ই দুটোই চালিয়ে যেটা ভালো তা নেওয়া হয় — কিন্তু "প্রমাণিত বাউন্ড আছে" এখনও গুরুত্বপূর্ণ যখন ওয়ার্স্ট-কেস পারফরম্যান্স নিশ্চিত করতে হয়।
প্র ০২ Held-Karp DP-র সময় জটিলতা $O(n^2 \cdot 2^n)$ — এটি এখনও exponential। তাহলে এটি ব্রুট-ফোর্সের $O(n!)$-এর চেয়ে "গুণগতভাবে" ভালো কিছু, নাকি শুধু একটি ছোট ধ্রুবক-ফ্যাক্টর উন্নতি?
এটি গুণগতভাবে ভালো — স্টার্লিং-এর approximation অনুযায়ী $n!$ প্রায় $\left(\frac{n}{e}\right)^n$-এর মতো বাড়ে, যেখানে $2^n$ তার চেয়ে অনেক ধীরে বাড়ে (উভয়ই exponential, কিন্তু $n!$-এর ভিত্তি $n$-এর সাথে নিজেই বাড়ে, $2^n$-এর ভিত্তি স্থির)। তাই $n$ বাড়ার সাথে সাথে ব্যবধান শুধু বাড়তেই থাকে — যেমন উপরের কোডে $n=8$-এ ব্রুট-ফোর্স $5040$টি পারমুটেশন চেক করে, Held-Karp মাত্র $1351$টি ট্রানজিশন করে, কিন্তু $n=20$-এ এই ব্যবধান কয়েক লক্ষ গুণে পৌঁছাবে। তবু $2^{20}$ ইতিমধ্যে দশ লক্ষের বেশি, তাই Held-Karp $n \approx 20$-২৫-এর পরে ব্যবহারিকভাবে অচল হয়ে যায় — এটাই ঠিক কেন NP-hard সমস্যায় "এক্স্যাক্ট হলেও দ্রুততর" পদ্ধতি একটি স্থায়ী সমাধান নয়, শুধু কিছুটা বড় ইনস্ট্যান্স পর্যন্ত সীমা বাড়ায়।
প্র ০৩ এই পুরো ক্যাপস্টোন জুড়ে M5, M6, M8, M12-এর ধারণা ব্যবহার করা হয়েছে — M1-M3 (RAM মডেল, বিগ-ও, রিকারেন্স) কি এখানে সরাসরি ব্যবহৃত হয়েছে, নাকি শুধু ভিত্তি হিসেবে থেকে গেছে?
সরাসরি ব্যবহৃত হয়েছে, যদিও স্পষ্টভাবে নাম নিয়ে নয়। M2-এর বিগ-ও নোটেশন ছাড়া আমরা $O(n!)$, $O(n^2 \cdot 2^n)$, $O(n^2)$ ও $O(n^2 \log n)$ — এই চারটি জটিলতাকে অর্থপূর্ণভাবে তুলনাই করতে পারতাম না। M1-এর RAM মডেল ছাড়া "প্রতিটি দূরত্ব-হিসাব $O(1)$" এই অনুমানটি অস্পষ্ট থেকে যেত (বাস্তবে ভাসমান-বিন্দু বর্গমূল গণনার নিজস্ব খরচ আছে, যা আমরা উপেক্ষা করেছি ঠিক RAM মডেলের সরলীকরণের কারণে)। আর M3-এর রিকারেন্স-সমাধান কৌশলগুলো ছাড়া Held-Karp-এর $O(n^2 \cdot 2^n)$ বাউন্ডটি "রাজ্য-সংখ্যা × প্রতি-রাজ্য-কাজ" হিসেবে ভাঙা কঠিন হতো। এই কোর্সের প্রতিটি মডিউল আসলে একে অপরের উপর নির্ভরশীল একটি একক টুলকিট — L57 শুধু সবগুলো একসাথে ব্যবহার করে দেখাল।
অনুশীলন
-
চিন্তা করুন: যদি পঞ্চম কোড সেলে আরেকটি পদ্ধতি — "শুরুর শহর থেকে দূরত্ব অনুযায়ী শহরগুলোকে
সাজিয়ে একটি ট্যুর বানানো" (স্পষ্টতই একটি খারাপ হিউরিস্টিক) — যোগ করা হতো, তাহলে তার গড় গ্যাপ অন্য
পদ্ধতিগুলোর তুলনায় কেমন হতো বলে আপনার ধারণা?
সম্ভবত অনেক বেশি খারাপ হতো — কারণ এই পদ্ধতিটি প্রতিবেশী শহরগুলোর মধ্যে দূরত্ব বিবেচনা করে না, শুধু একটি নির্বিচার রেফারেন্স বিন্দু থেকে দূরত্ব দেখে সাজায়, যা কাছাকাছি দুটি শহরকে ট্যুরে বহু দূরে ফেলে দিতে পারে। এটি দেখায় যে "কিছু একটা নিয়ম দিয়ে সাজানো" আর "প্রতিবেশী-সচেতন গ্রিডি" (নিয়ারেস্ট-নেইবার) এক জিনিস নয় — একটি ভালো হিউরিস্টিক ডিজাইন করাও নিজেই একটি দক্ষতা।
-
পরীক্ষা করুন: চতুর্থ কোড সেলে
instancesলিস্টের প্রথম ইনস্ট্যান্সটি (instances[0]) সরিয়ে বাকি তিনটি নিয়ে Run চেপে দেখুন<=2x বাউন্ডকলাম এখনও সব সারিতেTrueথাকে কিনা।হ্যাঁ, বাকি তিনটি ইনস্ট্যান্সেও (রেশিও $1.000$, $1.086$, $1.313$) বাউন্ড এখনও ধরে থাকবে — কারণ এই গ্যারান্টিটি একটি নির্দিষ্ট ইনস্ট্যান্সের ভাগ্যের উপর নির্ভর করে না, বরং যেকোনো মেট্রিক ইনস্ট্যান্সে গাণিতিকভাবে প্রমাণিত। এটাই "একটি নির্দিষ্ট টেস্ট কেসে পাস করা" আর "প্রমাণিতভাবে সবসময় সত্য" — এই কোর্সজুড়ে বারবার আসা পার্থক্যটির চূড়ান্ত, সরাসরি প্রদর্শন।
কোর্স সম্পূর্ণ — অভিনন্দন!
- সম্পূর্ণ কোর্স আবার দেখুন সবকটি ৫৭টি পাঠ সম্পন্ন অ্যাসিম্পটোটিক অ্যানালাইসিস থেকে রিকারেন্স, ডিভাইড অ্যান্ড কনকার, গ্রিডি, DP, গ্রাফ অ্যালগরিদম, ব্যাকট্র্যাকিং, স্ট্রিং অ্যালগরিদম, অ্যামর্টাইজড অ্যানালাইসিস, NP-কমপ্লিটনেস, অ্যাপ্রক্সিমেশন ও র্যান্ডোমাইজড অ্যালগরিদম হয়ে এই ক্যাপস্টোন পর্যন্ত — কোর্সের সবকটি পাঠ এখন সম্পূর্ণ।
- অ্যালগরিদম অ্যানালাইসিসের সাধারণ ভুল আগের পাঠ এই ক্যাপস্টোনে দেখা "প্রমাণহীন হিউরিস্টিক একবার ভালো করল মানেই সবসময় ভালো করবে না" নীতিটির পূর্ণ আলোচনা।
- Software Testing & Quality Assurance কোর্স পরবর্তী কোর্স এই কোর্সে শেখা "প্রতিটি দাবি যাচাই করা" এই একই রিগোরাস মানসিকতা এবার প্রয়োগ হবে সফটওয়্যার টেস্টিং ও কোয়ালিটি অ্যাসিওরেন্সে।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, Discrete Mathematics, System Design, Cybersecurity, Cloud Computing & DevOps, Computer Networks, Operating Systems, Computer Architecture, Programming Languages & Compiler Design, Software Engineering & Git, Theory of Computation, Engineering Economics, Full-Stack Web Frameworks, Mobile App Development, Ethics in Computing & AI Safety, Software Testing & Quality Assurance ও Design and Analysis of Algorithms — সব এক জায়গায়।