tabu_search

import random
import time


def construct(n):
    pi = list(range(n))
    random.shuffle(pi)
    return pi


def evaluate(n, f, d, pi):
    delta = [[None] * n for _ in range(n)]  # 施設iが場所jにあるときの目的関数への寄与
    for i in range(n):
        for j in range(n):
            delta[i][j] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                delta[i][j] = delta[i][j] + f[i][k] * d[j][pi[k]]

    cost = 0
    for i in range(n):
        cost += delta[i][pi[i]]

    return cost, delta


def find_move(n, f, d, pi, delta, tabu, iteration):
    minmove = float("inf")
    istar, jstar = None, None
    for i in range(n - 1):
        for j in range(i + 1, n):
            if tabu[i][pi[j]] > iteration or tabu[j][pi[i]] > iteration:
                continue

            move = delta[j][pi[i]] - delta[j][pi[j]] + delta[i][pi[j]] - delta[i][pi[i]] + 2 * f[i][j] * d[pi[i]][pi[j]]

            if move < minmove:
                minmove = move
                istar, jstar = i, j

    return istar, jstar, minmove * 2    # iとjの交換とその改悪量


def tabu_search(n, f, d, max_iter, tabulen):
    tabu = [[None] * n for _ in range(n)]   # 施設iと施設jの交換が禁止されている反復数
    for i in range(n):
        for j in range(n):
            tabu[i][j] = 0

    pi = construct(n)
    cost, delta = evaluate(n, f, d, pi)
    bestcost = cost

    for it in range(max_iter):
        istar, jstar, mindelta = find_move(n, f, d, pi, delta, tabu, it)

        if istar is None or jstar is None:
            continue

        cost += mindelta
        for i in range(n):
            for j in range(n):
                delta[i][j] += (f[i][jstar] - f[i][istar]) * (d[j][pi[istar]] - d[j][pi[jstar]])

        tabu[istar][pi[istar]] = it + tabulen
        tabu[jstar][pi[jstar]] = it + tabulen
        pi[istar], pi[jstar] = pi[jstar], pi[istar]

        if cost < bestcost:
            bestcost = cost
            bestsol = list(pi)

    return bestcost, bestsol


def mk_rnd_data(n):
    f = [[None] * n for _ in range(n)]
    d = [[None] * n for _ in range(n)]
    for i in range(n - 1):
        for j in range(i + 1, n):
            f[i][j] = f[j][i] = random.randint(0, 9)
            d[i][j] = d[j][i] = random.randint(0, 9)

    for i in range(n):
        f[i][i] = d[i][i] = 0

    return n, f, d


def optimal_solution(n, f, d):
    from itertools import permutations

    best_cost = float("inf")
    best_perm = None
    for p in permutations(list(range(n))):
        cost, _ = evaluate(n, f, d, list(p))
        if cost < best_cost:
            best_cost = cost
            best_perm = p

    return best_cost, best_perm


def main():
    n, f, d = mk_rnd_data(20)
    max_iter = 100
    tabu_len = 10

    print("tabu search")
    start = time.time()
    best_cost, best_perm = tabu_search(n, f, d, max_iter, tabu_len)
    print(f"best cost:{best_cost}")
    print(f"best perm:{best_perm}")
    print(f"time:{time.time() - start:.03f} sec")
    print()

    # print("full search")
    # start = time.time()
    # best_cost, best_perm = optimal_solution(n, f, d)
    # print(f"best cost:{best_cost}")
    # print(f"best perm:{best_perm}")
    # print(f"time:{time.time() - start:.03f} sec")


if __name__ == '__main__':
    main()