巡回セールスマン問題実践集①~全探索編~

TSPを解くを実践しました。英語で書かれているが、図やプログラムから容易に理解が進められる。用語の定義をしっかりと説明してくれている点も非常にありがたかった。
また、codeを説明していく展開の仕方が非常に勉強になった。

ここでは手っ取り早く理解したい人用にサクッと書いていく。
#巡回セールスマン問題って何

巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。

Wikipediaより

#全探索法:alltours_tsp
その名の通り、すべての取りうる経路について調べ上げて、最短経路を求める。
TSPを解くに従って、
codeの中で"やりたいこと"を記述して、その後に実際のcodeを書く。
code下部の#TO DOでは、未定義の言葉や関数などこれから書く内容を示している。

def alltours_tsp(cities):
    "取りうるすべての経路を生成し、最短経路のものを選択する。"
    return shortest_tour(alltours(cities))

def shortest_tour(tours): 
    "最短距離でいける経路を選択する。"
    return min(tours, key=tour_length)

# TO DO: Data types: cities, tours, Functions: alltours, tour_length

##取りうるすべての経路
###alltours
permutationは日本語に訳すと順列。
itertools.permutationsを使います。
itertoolsについて詳しく知りたい方用

alltours = itertools.permutations

cities = {1, 2, 3}

list(alltours(cities))

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
が出力されるはず

###tour_length
経路の長さを求める。

def tour_length(tour):
    "経路中の連続する2点間の距離の和を求める。"
    return sum(distance(tour[i], tour[i-1]) 
               for i in range(len(tour)))

# TO DO: Data types: cities, Functions: distance

python的書き方メモ
tour[-1]はtourの最後の要素を示してくれるから、
distance(tour[0], tour[-1])で経路の最初と最後の地点の経路を計算できて、
経路ぐるっと一周する距離を求められる。

##都市を設定
簡易的にユークリッド平面的な二点間の距離について扱う

###City,distance
複素数によって地点、距離を求める

class Point(complex):
    x = property(lambda p: p.real)
    y = property(lambda p: p.imag)
    
City = Point

def distance(A, B): 
    "2点A,B間の距離"
    return abs(A - B)

試しに

A = City(3, 0)
B = City(0, 4)
distance(A, B)

5.0

###ランダムな都市を設定
Cityをn回呼び出すことでランダムな都市をn個生成できる。

{City(random.randrange(1000), random.randrange(1000)) for c in range(6)}

{(299+183j), (313+355j), (360+369j), (387+789j), (443+853j), (702+269j)}

###Cities
こんな感じで関数Citiesに色々やってもらおう

def Cities(n, width=900, height=600, seed=42):
    "width x height の長方形内でランダムなn個の都市を作る"
    random.seed(seed * n)
    return frozenset(City(random.randrange(width), random.randrange(height))
                     for c in range(n))

メモ
・同じランダムセットをもう一度出力して欲しい時とランダムに複数の出力をして欲しい時がある。
　seedを設定することでそれに対応した。random.seedでランダムな数の生成をリセットする。
例を見た方が早い↓

# 5都市のセット
Cities(5)

frozenset({(172+20j), (234+40j), (393+7j), (671+296j), (696+415j)})

# 毎回全く同じ5都市のセット
[Cities(5) for i in range(3)]

[frozenset({(172+20j), (234+40j), (393+7j), (671+296j), (696+415j)}), frozenset({(172+20j), (234+40j), (393+7j), (671+296j), (696+415j)}), frozenset({(172+20j), (234+40j), (393+7j), (671+296j), (696+415j)})]

# 毎回異なる5都市のセット
[Cities(5, seed=i) for i in range(3)]

[frozenset({(41+265j), (414+310j), (523+497j), (776+430j), (864+394j)}), frozenset({(29+476j), (637+261j), (759+367j), (794+255j), (814+542j)}), frozenset({(211+473j), (439+494j), (585+33j), (591+15j), (832+503j)})]

これで関数alltours_tspを使う用意はできた。

alltours_tsp(Cities(8))

((6+546j), (199+147j), (350+65j), (737+26j), (847+187j), (891+465j), (554+374j), (505+548j))

tour_length(alltours_tsp(Cities(8)))

2509.3075877203014

##経路を表示
出力された経路が最短経路なのかわからない。
図に表示して直感的に理解できるようにしよう。
###plot_tour
都市を点、経路を線で表示する。

def plot_tour(tour): 
    "都市を点、経路を都市間を結ぶ線としてプロット"
    plot_lines(list(tour) + [tour[0]])
    
def plot_lines(points, style='bo-'):
    "連続する都市を結ぶように線をプロット"
    plt.plot([p.x for p in points], [p.y for p in points], style)
    plt.axis('scaled'); plt.axis('off')

plot_tour(alltours_tsp(Cities(8)))

めっちゃよさそう!!

###plot_tsp
評価のためにもう一段階優れた関数を設定する。
plot_tsp(algorithm, cities)では引数にアルゴリズム(alltours_tspなど)と都市をとる。

def plot_tsp(algorithm, cities):
    "TSPを解くアルゴリズムを都市に適用し、最終的な経路をプロットし、諸情報を表示する"
    # 優れた経路を求め、それにかかった時間を計算する。
    t0 = time.clock()
    tour = algorithm(cities)
    t1 = time.clock()
    assert valid_tour(tour, cities)
    plot_tour(tour); plt.show()
    print("{} city tour with length {:.1f} in {:.3f} secs for {}"
          .format(len(tour), tour_length(tour), t1 - t0, algorithm.__name__))
    
def valid_tour(tour, cities):
    "求めた経路が元の都市に適したものか判定する。"
    return set(tour) == set(cities) and len(tour) == len(cities)

plot_tsp(alltours_tsp, Cities(8))

8 city tour with length 2509.3 in 0.123 secs for alltours_tsp

##改良版alltours.tsp
n個の都市に対して、現状はn!個の経路を考えている。
しかし、n個の円順列は(n-1)!通りである。(先頭を固定すればよい)
その無駄をなくために、alltoursを関数として定義し直す。
また、今後のために経路をlist型にする。
###alltours改
都市を開始地点とそれ以外の２つに分け、それ以外の順列のそれぞれと最初の都市を合わせたリストを出力する。

def alltours(cities):
    "共通の開始地点からの全経路を出力する"
    start = first(cities)
    return [[start] + Tour(rest)
            for rest in itertools.permutations(cities - {start})]

def first(collection):
    "iter()を利用してcollectionの最初の要素を取り出す。"
    return next(iter(collection))

Tour = list  # 経路をlist型にするため

メモ
iter()はlistやtupleを先頭の要素から取れるようにする。
要素を取り出すときはnext()を使う。
iterについて参考元

alltours_tsp(Cities(8))を呼び出すことで全く同じ経路について確認できる。
が今なら計算が早くなっているはず。

plot_tsp(alltours_tsp, Cities(8))

8 city tour with length 2509.3 in 0.022 secs for alltours_tsp

都市の数を増やしてみる

plot_tsp(alltours_tsp, Cities(10))

10 city tour with length 2291.8 in 2.019 secs for alltours_tsp

alltours_tspの計算速度

10都市の問題に対して約2秒かかった。
一般的にn個の都市に対して(n-1)!個の経路を総当たりで調べる。
よって計算にかかる時間もおよそn!の比率で増えていくと考えられる。

n	alltours.tsp(Cities(n))の計算時間
10	Covering 10! tours = 2 secs
11	2 secs × 11! / 10! ≈ 22 secs
12	2 secs × 12! / 10! ≈ 4 mins
14	2 secs × 14! / 10! ≈ 13 hours
16	2 secs × 16! / 10! ≈ 200 days
18	2 secs × 18! / 10! ≈ 112 years
25	2 secs × 25! / 10! ≈ 270 billion years

TSPを解くのにもっといい方法があるはずである。

次回はTSPを最近傍探索法によって解きます。