Day 151-Q2 | 蟻コロニー最適化（ACO）

問題

$N$ 都市のTSPを、以下の簡略化した蟻コロニー最適化で解く。距離は対称行列$D$で与えられる。フェロモン行列$\tau$は全成分$1.0$で初期化。パラメータ$\alpha,\beta$（整数）、蒸発率$\rho$、追加量係数$Q$、反復回数$\mathrm{ITER}$が与えられる。

1反復の手続き（都市は1-indexed、内部は0-indexedでよい）

都市1から出発。現在都市$i$から未訪問都市$j$への魅力度 $\mathrm{score}(i,j)=\tau_{i,j}^{\alpha}\times(1/D_{i,j})^{\beta}$ が最大の都市へ決定的に移動（同点は都市番号最小）。全都市訪問後、出発都市に戻り一周長$L$を計算。
全ペアのフェロモンを蒸発： $\tau_{i,j}\gets\tau_{i,j}\times(1-\rho)$。
巡回路の辺（両方向）に $Q/L$ を加算。

これを$\mathrm{ITER}$回繰り返し、各反復の巡回路（都市1から出発した訪問順）と長さを出力せよ。

入力形式

N alpha beta rho Q ITER
D_11 D_12 ... D_1N
:
D_N1 ... D_NN

制約

$3 \le N \le 8$

$1 \le \alpha,\beta \le 5$

$0<\rho<1$、$Q>0$

$1 \le \mathrm{ITER} \le 20$

$1 \le D_{i,j} \le 1000$、対称

入出力例

入力例1

4 1 2 0.5 10.0 3
0 2 9 10
2 0 6 4
9 6 0 3
10 4 3 0

出力例1

1 2 4 3 18
1 2 4 3 18
1 2 4 3 18

概念図：4都市の巡回路とフェロモン強化

ヒント（段階的開示）

ヒント1（方向性）

真のACOは複数の蟻がランダムに経路を選ぶが、本問は蟻1匹・確率選択を「最大の魅力度」に置き換えた決定的簡略版。同じ入力なら常に同じ経路になる。

ヒント2（アプローチ）

初回反復はフェロモンが一様($\tau=1$)なので、魅力度は事実上$D_{i,j}^{-\beta}$のみで決まる（最近傍法に一致）。2反復目以降はフェロモンの蒸発・追加による正のフィードバックが働く。

ヒント3（誘導）

def build_tour(D, tau, alpha, beta, n):
    visited = [False]*n
    cur = 0
    visited[0] = True
    tour = [0]
    for _ in range(n-1):
        best_j, best_score = None, None
        for j in range(n):
            if visited[j]:
                continue
            score = (tau[cur][j]**alpha) * ((1.0/D[cur][j])**beta)
            if best_score is None or score > best_score:
                best_score, best_j = score, j
        tour.append(best_j)
        visited[best_j] = True
        cur = best_j
    return tour

模範解答 (Python)

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); ptr += 1
    alpha = int(data[ptr]); ptr += 1
    beta = int(data[ptr]); ptr += 1
    rho = float(data[ptr]); ptr += 1
    Q = float(data[ptr]); ptr += 1
    iters = int(data[ptr]); ptr += 1
    D = []
    for i in range(n):
        row = [int(data[ptr + j]) for j in range(n)]
        ptr += n
        D.append(row)

    tau = [[1.0] * n for _ in range(n)]
    out_lines = []
    for _ in range(iters):
        visited = [False] * n
        cur = 0
        visited[0] = True
        tour = [0]
        for _ in range(n - 1):
            best_j = None
            best_score = None
            for j in range(n):
                if visited[j]:
                    continue
                score = (tau[cur][j] ** alpha) * ((1.0 / D[cur][j]) ** beta)
                if best_score is None or score > best_score:
                    best_score = score
                    best_j = j
            tour.append(best_j)
            visited[best_j] = True
            cur = best_j
        L = sum(D[tour[i]][tour[(i + 1) % n]] for i in range(n))
        out_lines.append(" ".join(str(c + 1) for c in tour) + " " + str(L))
        for i in range(n):
            for j in range(n):
                tau[i][j] *= (1 - rho)
        dep = Q / L
        for i in range(n):
            a = tour[i]
            c = tour[(i + 1) % n]
            tau[a][c] += dep
            tau[c][a] += dep
    print("\n".join(out_lines))

main()

Step-by-Step 解説

11反復目（フェロモン一様）
都市1(0-idx 0)から出発。$D_{0,1}=2,D_{0,2}=9,D_{0,3}=10$より最近傍の都市2へ。以降も貪欲に近い都市を選び、巡回路[0,1,3,2]（1-indexed 1 2 4 3）、長さ$2+4+3+9=18$。

2フェロモン更新
蒸発で全ペア$\times0.5$。巡回路の辺$(0,1),(1,3),(3,2),(2,0)$に$Q/L=10/18\approx0.5556$を両方向加算。

32・3反復目も同じ経路
本インスタンスでは初回の最近傍貪欲がたまたま大域最適(長さ18)と一致しており、フェロモン強化はその辺をさらに後押しするだけなので同じ経路が再現される。

4早期収束の裏側
もし初回選択が非最適なら、フェロモン強化はその非最適経路を強化し続ける。本来のACOは複数蟻の多様性でこの罠を回避しようとするが、本問の簡略版はそれを捨てている。

よくあるミス

ミス	原因	正しい書き方
フェロモン更新を巡回路構成の前に行う	手順の順序を誤解	「構成→長さ計算→蒸発→追加」の順で1反復を完結
蒸発を巡回路の辺だけに適用	蒸発と追加を混同	蒸発は全ペア、追加は巡回路の辺のみ
$\tau_{i,j}$と$\tau_{j,i}$の片方だけ更新	対称性の仮定漏れ	両方向とも明示的に更新する
$\beta$乗を魅力度全体にかけてしまう	数式の対応関係の誤読	$\tau^\alpha$と$(1/D)^\beta$は別指数で積を取る
同点判定で`>=`を使い後の都市で上書き	比較演算子のミス	厳密な`>`のみで昇順走査すれば最小番号が残る

次のステップ

発展: 蟻を複数匹にして多様性を持たせ、非最適な初期解に陥るインスタンスでも最適解へ収束できるか実験する。
次回予告: 遺伝的アルゴリズム（Genetic Algorithm）

自己評価

完全理解おおむね理解要復習

Day 151-Q2 — 蟻コロニー最適化（Ant Colony Optimization）

問題