Day 150-Q5 — 山登り法（Hill Climbing・グラフ彩色の局所改善）

2026-09-11 赤色 Master / Phase 8+ ★★★★★★★★★ 改善する手だけを最も良い順に選び続け、改善する手が無くなったら止まる最もシンプルな局所探索

問題

$N$頂点・$M$辺の無向グラフと色数$K$が与えられる。各頂点に$0$〜$K-1$の色を割り当てる初期彩色が与えられる。同じ色の両端点を結ぶ辺をコンフリクト辺と呼ぶ。以下のsteepest-ascent山登り法を実行し、停止時のコンフリクト辺数と最終彩色を出力せよ。

各反復の手順

  1. 現在のコンフリクト辺数をcurとする。
  2. 全頂点$v$(昇順)と$v$の現在色以外の全色$c$(昇順)の組$(v,c)$を列挙。
  3. 各組について色変更後のコンフリクト辺数newと削減量delta=cur-newを求める。
  4. delta最大の組を選ぶ(同着は辞書式最小の$(v,c)$)。
  5. delta>0のときのみ実際に変更し次の反復へ。
  6. delta<=0なら探索終了。

入力形式

N M K
u_1 v_1
:
u_M v_M
c_1 ... c_N

制約

$3 \le N \le 12$
$N-1 \le M \le 20$
$2 \le K \le 4$
$0 \le c_i \le K-1$

入出力例

入力例1

5 5 2
0 1
1 2
2 3
3 4
4 0
0 0 0 0 0

出力例1

1
1 0 1 0 0

概念図：5-サイクルの彩色が1手ずつ改善される様子

奇数サイクルは2色で完全彩色不可能 → 局所最適でも1コンフリクトが残る 初期 conflicts=5 0 1 2 3 4 it1: 頂点0→色1 conflicts=3 0 1 2 3 4 it2: 頂点2→色1 conflicts=1(停止) 0 1 2 3 4 緑の辺=異色(OK)、赤の辺=コンフリクト。5頂点の奇数サイクルではどう塗っても赤い辺を完全には消せない。

ヒント（段階的開示）

ヒント1（方向性）

グラフは5頂点の閉路で、奇数長のサイクルは2色では完全な彩色（コンフリクト0）が不可能なことが知られている。このため山登り法がどれだけ改善を続けても、最終的に少なくとも1本のコンフリクト辺が残る。

ヒント2（アプローチ）

「最も改善する手」を毎回選ぶには全ての$(v,c)$組についてコンフリクト辺数の変化を計算する必要がある。$N,M$が小さいため、色を変えてから全辺を再チェックする愚直な方法で十分高速。

ヒント3（誘導） 
def conflicts(coloring):
    return sum(1 for (u, v) in edges if coloring[u] == coloring[v])

coloring = initial_coloring[:]
while True:
    cur = conflicts(coloring)
    best_delta, best_v, best_c = 0, -1, -1
    for v in range(N):
        for c in range(K):
            if c == coloring[v]:
                continue
            trial = coloring[:]; trial[v] = c
            delta = cur - conflicts(trial)
            if delta > best_delta:
                best_delta, best_v, best_c = delta, v, c
    if best_delta <= 0:
        break
    coloring[best_v] = best_c

模範解答 (Python)

import sys


def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); m = int(data[ptr + 1]); k = int(data[ptr + 2]); ptr += 3
    edges = []
    for _ in range(m):
        u = int(data[ptr]); v = int(data[ptr + 1]); ptr += 2
        edges.append((u, v))
    coloring = [int(data[ptr + i]) for i in range(n)]
    ptr += n

    def conflicts(col):
        return sum(1 for (u, v) in edges if col[u] == col[v])

    while True:
        cur = conflicts(coloring)
        best_delta = 0
        best_v = -1
        best_c = -1
        for v in range(n):
            for c in range(k):
                if c == coloring[v]:
                    continue
                trial = coloring[:]
                trial[v] = c
                new_conf = conflicts(trial)
                delta = cur - new_conf
                if delta > best_delta:
                    best_delta = delta
                    best_v = v
                    best_c = c
        if best_delta <= 0:
            break
        coloring[best_v] = best_c

    print(conflicts(coloring))
    print(" ".join(map(str, coloring)))


main()

Step-by-Step 解説

1初期コンフリクト数
初期彩色0 0 0 0 0では全5辺が同色でコンフリクト、cur=5。
2反復1
頂点0を色1に変えると辺(0,1)と辺(4,0)が解消されコンフリクトは3(delta=2)。他のどの頂点変更も2を超えないため頂点0が選ばれる。彩色は1 0 0 0 0。
3反復2
頂点2を色1に変えると辺(1,2)と辺(2,3)が解消されdelta=2でコンフリクトは1。彩色は1 0 1 0 0。
4局所最適で停止
この状態でどの頂点を変えてもコンフリクトを減らせない（奇数サイクルの構造上、2色では必ず1本以上残る）ためbest_delta<=0で終了。

よくあるミス

ミス原因正しい書き方
delta>=best_deltaで更新し辞書式最小でない解が選ばれる同着の扱いの誤解厳密に>で比較し先に見つかったものを残す
delta==0の手まで受理してしまう「改悪でなければよい」と誤解delta>0のときだけ受理する
局所最適到達後も反復を続けてしまう停止条件の誤解best_delta<=0で必ず停止する
コンフリクト数を前回値の使い回しで済ませる差分更新の簡略化しすぎ本問の制約では全辺を毎回スキャンして再計算するのが安全
Q4のタブーサーチと混同し改悪を受理してしまう2つのアルゴリズムの混同山登り法には改悪の受理もタブーリストも無く、局所最適で即終了する

次のステップ

  • 発展: 本問の5頂点奇数サイクルでは2色でのコンフリクト最小値が1であることが構造的に保証されるが、一般のグラフでは山登り法が真の最小コンフリクト数より悪い局所最適で停止することがある。Q4のタブーサーチや焼きなまし法と比較すると、山登り法がどれだけ「運任せ」な性質を持つかが実感できる。
  • 次回予告: Master Levelローテーション継続（次回セッションでテーマを再選定）

自己評価

自分の回答

気づき・メモ