Rで巡回セールスマン問題
# !! Tumblrは"ダブルクォーテーションマーク"の形を勝手に変えてしまうので、コピペする場合は適宜書き換えて下さい。 !!
# TSP = Traveling Salesman Problem = 巡回セールスマン問題
# 作業ディレクトリを適宜変更. # mac:Session → Set Working Directory → To Source File Location # win:File → Set Working Directory → To Source File Location
# パッケージのダウンロード. 初回のみ. なんかy/nのところでyにしたらエラー吐いたのでnにしたらうまくいった. install.packages("TSP") # ライブラリ呼び出し. library(TSP)
# 距離行列を直接入力.
d.matrix = matrix( c(0,2,4,5,8, 2,0,3,6,2, 3,3,0,5,2, 4,4,1,0,5, 7,2,3,5,0), 5 # 行列のサイズ )
# あるいは、同ディレクトリ内に d.sample.csv を用意し, そこから距離行列を取得する. # d.matrix = as.matrix( read.csv("d.sample.csv", header = FALSE) )
# 距離行列が非対称行列なら solve_TSP( ATSP(距離行列) ) , 対称行列なら solve_TSP( TSP(距離行列) ) で巡回サラリーマン問題を解く. # (A: アシンメトリー). atsp = solve_TSP( ATSP(d.matrix) )
# atsp は ATSPクラスに入っている. as.vectorで経路が取り出せる. tour_lengthで走行距離が取り出せる. route = as.vector(atsp) len = tour_length(atsp)
>route [1] 4 1 2 5 3 >len [1] 11
# 何度か試したところもっと良い解(len =7)も出てきたので、発見的手法を用いているようだ. # solve_TSP(ATSP(d.matrix), method = "nearest_insertion") などとすることで、手法を指定することができる. # 手法には "nearest_insertion", "cheapest_insertion", "farthest_insertion", "arbitrary_insertion", "nn", "repetitive_nn", "2-opt" などがある. 経験的に "repetitive_nn" が良い解を出すが, 多分その分計算に時間がかかる.
















