Pythonですべての手紙を配達するための最小パスを見つけるプログラム

問題の概要

n個の都市がn−1本の道路で相互に接続されているとします。この構成では、どの都市からでも他のすべての都市へ移動できます。都市の郵便システムでは毎日k通の手紙を配達しており、その宛先はk個の異なる都市のいずれかです。郵便配達員は毎日、これらすべての手紙を宛先の住所へ届けなければなりません。ここで求めたいのは、すべての手紙を配達し終えるまでに配達員が移動しなければならない距離の最小値です。なお、配達員は任意の都市から出発することができます。

たとえば、次のような入力が与えられたとします。

手紙を配達すべき都市（delv）が1、2、4である場合、出力は4になります。

配達員は都市1、2、4のいずれからでも配達を開始できます。都市1から出発した場合の経路は1→2→4となり、都市4から出発した場合はその逆の4→2→1となります。このときの合計コストは1＋3＝4です。一方、都市2から出発した場合のコストは、他の2つのケースよりも大きくなります。

解法のアプローチ

この問題は、木構造（n個のノードとn−1本の辺）に対する深さ優先探索（DFS）を使って解きます。基本的な考え方は次のとおりです。

• 配達対象の都市を含む部分木にある辺は、すべて往復する必要があるため、その総コストをSUMとして集計し、答えの候補をSUM×2とします。
• ただし、配達員はどこか1か所で折り返して戻る必要がないため、配達対象部分木の中で最も長い一本道（直径）に相当する分だけ移動を省略できます。この最大値をMAXとして記録します。
• 最終的な答えは「SUM × 2 − MAX」となります。

具体的には、以下の手順に従います。

• 関数depth_search()を定義します。引数はnode（現在のノード）とp（親ノード）です。
  • d1 := −無限大
  • d2 := −無限大
  • adj_list[node]内の各ペア(x, y)について、次を実行します。
    • xがpと等しくない場合：
      • d1 := max(d1, depth_search(x, node) + y)
      • d1 > d2であれば、d2とd1の値を入れ替える
      • ti[node] := ti[node] + ti[x]
      • 0 < ti[x] < kであれば、SUM := SUM + y
  • d1 > 0であれば、MAX := max(MAX, d1 + d2)
  • d2 > 0かつtj[node]がゼロでなければ、MAX := max(MAX, d2)
  • tj[node]がゼロでなければ、d2 := max(0, d2)
  • d2を返す
• k := delvの要素数
• adj_list := 新しいマップ（隣接リスト）
• ti := サイズ(nodes + 5)のリストを0で初期化
• tj := サイズ(nodes + 5)のリストを0で初期化
• delv内の各iについて、ti[i] := 1、tj[i] := 1とする
• roads内の各項目について、次を実行します。
  • x := item[0]、y := item[1]、c := item[2]
  • xがadj_listに存在しなければ、adj_list[x] := []を作成
  • yがadj_listに存在しなければ、adj_list[y] := []を作成
  • adj_list[x]の末尾に(y, c)を追加
  • adj_list[y]の末尾に(x, c)を追加
• SUM := 0、MAX := 0
• depth_search(1, 1)を呼び出す
• SUM * 2 − MAXを返す

実装例

理解を深めるために、以下のPython実装を見てみましょう。

import sys
from math import inf as INF
sys.setrecursionlimit(10**5 + 5)

def depth_search(node, p):
    global SUM, MAX
    d1 = -INF
    d2 = -INF

    for x, y in adj_list[node]:
        if x != p:
            d1 = max(d1, depth_search(x, node) + y)
            if d1 > d2:
                d1, d2 = d2, d1

            ti[node] += ti[x]
            if 0 < ti[x] < k:
                SUM += y

    if d1 > 0: MAX = max(MAX, d1 + d2)
    if d2 > 0 and tj[node]: MAX = max(MAX, d2)
    if tj[node]: d2 = max(0, d2)

    return d2

def solve(nodes, delv, roads):
    global k, ti, tj, adj_list, SUM, MAX
    k = len(delv)
    adj_list = {}
    ti = [0] * (nodes + 5)
    tj = [0] * (nodes + 5)

    for i in delv:
        ti[i] = tj[i] = 1

    for item in roads:
        x, y, c = map(int, item)
        if x not in adj_list: adj_list[x] = []
        if y not in adj_list: adj_list[y] = []

        adj_list[x].append([y, c])
        adj_list[y].append([x, c])

    SUM = 0
    MAX = 0
    depth_search(1,1)
    return SUM * 2 - MAX

print(solve(5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]))

入力

5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]

出力

4

まとめ

このプログラムでは、木構造上でDFSを1回実行するだけで、配達が必要な辺の往復コストの合計から最長経路を差し引くことで、最小移動距離を効率的に求めています。計算量はO(n)であり、都市数が多い場合でも高速に動作するのが特徴です。