Python: 巡回セールスマン問題をやってみた

巡回セールスマン問題ってどんな問題だったっけ?ふわっとしてたんで、理解するために、まずはシンプルに総当たりで解いてみた。だけです。

巡回セールスマン問題をいろんな近似解法で解く（1）

from itertools import permutations as IT_perm

total_cost = lambda costs : lambda seq : sum(
    costs[ seq[i - 1] ][ e ]
    for i, e in enumerate( seq )
)

head_fixed_permutations = lambda nodes : (
    nodes[ 0:1 ] + list( tail ) 
    for tail in IT_perm( nodes[ 1: ] )
)


costs = [
      [0, 6, 5, 5]
    , [6, 0, 7, 4]
    , [5, 7, 0, 3]
    , [5, 4, 3, 0]
    ]

nodes = [0, 1, 2, 3]

print(
    min(
        head_fixed_permutations( nodes )
        , key = total_cost( costs )
    )
)

# 結果：[0, 1, 3, 2]

リスト costs で、ノードa から ノードb までの移動コストが cost[a][b] で与えられているという前提です。
nodes はその ノードのリストで、出発点は nodes[0]：(値は 0)に固定、ということです。

考えたやりかたは、
先頭を固定したノードの順列に、
コストの合計を計算する関数を適用した値で、
最小のものを
出力する
ということです。

なるほど、こういうことか。意外とシンプルでした。