ট্র্যাভেলিং সেলসম্যান — ব্রাঞ্চ-অ্যান্ড-বাউন্ড

import itertools
import math
import random


def make_euclidean_instance(n, seed):
    # ফিক্সড সিড দিয়ে n টি এলোমেলো 2D পয়েন্ট, সিমেট্রিক ইউক্লিডিয়ান দূরত্ব ম্যাট্রিক্স
    rng = random.Random(seed)
    pts = [(rng.uniform(0, 100), rng.uniform(0, 100)) for _ in range(n)]
    dist = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                dist[i][j] = math.dist(pts[i], pts[j])
    return dist


def tsp_brute_force(dist, n):
    # সব (n-1)! পারমুটেশন চেষ্টা করে প্রকৃত অপটিমাম -- শুধু বেসলাইন, ছোট n-এর জন্য
    best_cost = float('inf')
    best_tour = None
    for perm in itertools.permutations(range(1, n)):
        tour = [0] + list(perm)
        cost = sum(dist[tour[i]][tour[(i + 1) % n]] for i in range(n))
        if cost < best_cost:
            best_cost = cost
            best_tour = tour
    return best_tour, best_cost


def tsp_branch_and_bound(dist, n, use_bound=True):
    best_cost = [float('inf')]
    best_tour = [None]
    nodes_explored = [0]

    # প্রতিটি শহরের সবচেয়ে সস্তা আউটগোয়িং এজ -- বাউন্ড ফর্মুলার মূল উপাদান
    min_out = [min(dist[c][j] for j in range(n) if j != c) for c in range(n)]

    visited = [False] * n
    visited[0] = True
    path = [0]

    def backtrack(current, current_cost):
        nodes_explored[0] += 1
        if len(path) == n:
            total = current_cost + dist[current][0]  # শুরুর শহরে ফিরে আসার এজ
            if total < best_cost[0]:
                best_cost[0] = total
                best_tour[0] = path.copy()
            return

        if use_bound:
            unvisited = [c for c in range(n) if not visited[c]]
            bound = current_cost + sum(min_out[c] for c in unvisited)
            if bound >= best_cost[0]:
                return  # B(pi) >= best_found -- এই শাখায় উন্নতির সম্ভাবনা নেই, নিরাপদে প্রুন

        for nxt in range(n):
            if not visited[nxt]:
                visited[nxt] = True
                path.append(nxt)
                backtrack(nxt, current_cost + dist[current][nxt])
                path.pop()
                visited[nxt] = False

    backtrack(0, 0)
    return best_tour[0], best_cost[0], nodes_explored[0]


print("n=6,7,8,9 -- প্রতিটিতে ৩টি ভিন্ন র‍ান্ডম ইনস্ট্যান্স -- মোট ১২টি তুলনা:\n")
all_match = True
for n in [6, 7, 8, 9]:
    for seed in [1, 2, 3]:
        dist = make_euclidean_instance(n, seed)
        _, bf_cost = tsp_brute_force(dist, n)
        _, bb_cost, nodes = tsp_branch_and_bound(dist, n)
        match = abs(bf_cost - bb_cost) < 1e-9
        all_match = all_match and match
        print(f"  n={n} seed={seed}: brute-force={bf_cost:8.3f}  branch&bound={bb_cost:8.3f}  মিলল={match}  নোড={nodes}")

print("\nসবগুলো ইনস্ট্যান্সে ব্রাঞ্চ-অ্যান্ড-বাউন্ড ব্রুট-ফোর্সের সাথে একমত:", all_match)

import math
import random


def make_euclidean_instance(n, seed):
    rng = random.Random(seed)
    pts = [(rng.uniform(0, 100), rng.uniform(0, 100)) for _ in range(n)]
    dist = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i != j:
                dist[i][j] = math.dist(pts[i], pts[j])
    return dist


def tsp_branch_and_bound(dist, n, use_bound=True):
    # আগের কোড সেলের মতোই, শুধু use_bound=False দিলে বাউন্ড-চেকটি সম্পূর্ণ বন্ধ থাকে
    # (তখন এটি শুধু ফিজিবিলিটি মেনে সব সম্ভাব্য ট্যুর এক্সপ্লোর করে -- প্লেইন ব্যাকট্র্যাকিং)
    best_cost = [float('inf')]
    nodes_explored = [0]
    min_out = [min(dist[c][j] for j in range(n) if j != c) for c in range(n)]
    visited = [False] * n
    visited[0] = True
    path = [0]

    def backtrack(current, current_cost):
        nodes_explored[0] += 1
        if len(path) == n:
            total = current_cost + dist[current][0]
            if total < best_cost[0]:
                best_cost[0] = total
            return
        if use_bound:
            unvisited = [c for c in range(n) if not visited[c]]
            bound = current_cost + sum(min_out[c] for c in unvisited)
            if bound >= best_cost[0]:
                return
        for nxt in range(n):
            if not visited[nxt]:
                visited[nxt] = True
                path.append(nxt)
                backtrack(nxt, current_cost + dist[current][nxt])
                path.pop()
                visited[nxt] = False

    backtrack(0, 0)
    return best_cost[0], nodes_explored[0]


print(f"{'n':>3} | {'বাউন্ড-সহ নোড':>14} | {'বাউন্ড-বিহীন নোড':>17} | {'প্রুনিং রেশিও':>14} | {'(n-1)!/2':>10}")
for n in [6, 7, 8, 9]:
    dist = make_euclidean_instance(n, 1)
    cost_bound, nodes_bound = tsp_branch_and_bound(dist, n, use_bound=True)
    cost_full, nodes_full = tsp_branch_and_bound(dist, n, use_bound=False)
    sym_space = math.factorial(n - 1) // 2
    ratio = nodes_bound / nodes_full
    # বাউন্ড থাকা/না-থাকা উভয় ক্ষেত্রেই একই অপটিমাম আসা উচিত -- বাউন্ড শুধু গতি বাড়ায়, উত্তর বদলায় না
    assert abs(cost_bound - cost_full) < 1e-9
    print(f"{n:>3} | {nodes_bound:>14} | {nodes_full:>17} | {ratio:>13.2%} | {sym_space:>10}")