Untitled

n = 4
visited = [0] * n
path = []
cost = 0
def find_min(adj, i):
    first, second = float('inf'), float('inf')
    for j in range(n):
        if i == j:
            continue
        if adj[i][j] <= first:
            second = first
            first = adj[i][j]

        elif (adj[i][j] <= second and
              adj[i][j] != first):
            second = adj[i][j]

    return first, second

def get_min_lower_bound(adj):
    lower_bound = 0
    for i in range(n):
        first, second = find_min(adj, i)
        lower_bound = lower_bound + first + second
    return lower_bound / 2

def bnb(adj, level, pre_bound):
    if all(item == 1 for item in visited):
        return

    elif level == n - 1:
        left = 0
        right = 0
        for i in range(n):
            if visited[i] == 0:
                right = left
                left = i

        left_cost = adj[path[-1]][left] + adj[left][right] + adj[right][0]
        right_cost = adj[path[-1]][right] + adj[right][left] + adj[left][0]

        if left_cost < right_cost:
            path.append(left)
            path.append(right)
            path.append(0)
        else:
            path.append(right)
            path.append(left)
            path.append(0)

    else:
        min_bound = float('inf')
        bound = [0] * n
        cur_bound = 0
        if level == 0:
            path.append(0)
            visited[0] = 1
            for i in range(1, n):
                min_0, _ = find_min(adj, 0)
                min_i, _ = find_min(adj, i)
                cur_bound = get_min_lower_bound(adj) - (min_0 + min_i) / 2 + adj[0][i]
                bound[i] = cur_bound
                if cur_bound < min_bound:
                    min_bound = cur_bound
        else:
            for i in range(n):
                if visited[i] != 1:
                    _, second = find_min(adj, path[-1])
                    min, _ = find_min(adj, i)
                    cur_bound = pre_bound - (second + min) / 2 + adj[path[-1]][i]
                    bound[i] = cur_bound
                    if cur_bound < min_bound:
                        min_bound = cur_bound
        for j in range(n):
            if bound[j] == min_bound:
                path.append(j)
                visited[j] = 1
                bnb(adj, level + 1, min_bound)
                path.pop()
                visited[j] = 0


if __name__ == "__main__":
    # n = int(input("Enter the number of locations: "))
    # mean = float(input("Enter the mean: "))
    # sigma = float(input("Enter the standard deviation: "))

    adj = [[0, 10, 15, 20],
           [10, 0, 35, 25],
           [15, 35, 0, 30],
           [20, 25, 30, 0]]
    bnb(adj, 0, 0)

    print(path)