মেট্রিক TSP অ্যাপ্রক্সিমেশন

import random
import math
from itertools import permutations

def euclidean(p, q):
    return math.hypot(p[0] - q[0], p[1] - q[1])

def build_mst_prim(points):
    # প্রিমের অ্যালগরিদম (দেখুন M5/L23-এ পূর্ণ প্রমাণসহ আলোচনা) -- এখানে শুধু ব্যবহার করা হচ্ছে
    n = len(points)
    in_tree = [False] * n
    dist = [math.inf] * n
    parent = [-1] * n
    dist[0] = 0
    mst_edges = []
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=lambda v: dist[v])
        in_tree[u] = True
        if parent[u] != -1:
            mst_edges.append((parent[u], u))
        for v in range(n):
            if not in_tree[v]:
                d = euclidean(points[u], points[v])
                if d < dist[v]:
                    dist[v] = d
                    parent[v] = u
    return mst_edges

def approx_tsp_tour(points):
    n = len(points)
    mst_edges = build_mst_prim(points)
    adj = {i: [] for i in range(n)}
    for u, v in mst_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 sorted(adj[u]):
            if not visited[v]:
                dfs(v)
    dfs(0)
    return order

def tour_length(points, order):
    total = 0.0
    n = len(order)
    for i in range(n):
        a = points[order[i]]
        b = points[order[(i + 1) % n]]
        total += euclidean(a, b)
    return total

def brute_force_tsp(points):
    n = len(points)
    best = math.inf
    rest = list(range(1, n))
    for perm in permutations(rest):
        order = [0] + list(perm)
        length = tour_length(points, order)
        if length < best:
            best = length
    return best

rng = random.Random(11)
worst_ratio = 0.0
print(f"{'trial':>5} | {'n':>3} | {'ALG':>8} | {'OPT':>8} | {'ratio':>6}")
for trial in range(10):
    n = rng.randint(4, 8)
    points = [(rng.uniform(0, 10), rng.uniform(0, 10)) for _ in range(n)]
    order = approx_tsp_tour(points)
    alg_len = tour_length(points, order)
    opt_len = brute_force_tsp(points)
    ratio = alg_len / opt_len
    worst_ratio = max(worst_ratio, ratio)
    print(f"{trial:>5} | {n:>3} | {alg_len:>8.2f} | {opt_len:>8.2f} | {ratio:>6.2f}")
    assert ratio <= 2 + 1e-9, "২-অ্যাপ্রক্সিমেশন বাউন্ড ভঙ্গ হয়েছে!"

print(f"\nসর্বোচ্চ পর্যবেক্ষিত ratio (ALG/OPT): {worst_ratio:.2f} -- সবসময় <= 2.00")