Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
7
Help us understand the problem. What is going on with this article?
@SaitoTsutomu

組合せ最適化 - 典型問題 - 巡回セールスマン問題

More than 1 year has passed since last update.

典型問題と実行方法

巡回セールスマン問題

n個の点(都市)の集合$V$から構成されるグラフ$G=(V,E)$および各辺に対するコストが与えられているとき、全ての点を1回ずつ経由する巡回路で辺上の(距離などの)コストの和を最小にするものを求めよ。

実行方法

usage
Signature: tsp(nodes, dist=None, method=None)
Docstring:
巡回セールスマン問題
入力
    nodes: 点(dist未指定時は、座標)のリスト
    dist: (i,j)をキー、距離を値とした辞書
    method: 計算方法(ex. 'ortools')
出力
    距離と点番号リスト
python
from ortoolpy import tsp
tsp([(2, 0), (1, 2), (0, 1), (3, 1), (2, 2)])[1]
結果
[0, 2, 1, 4, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import Tsp
Tsp('data/node1.csv')[1]
id x y demand
0 0 5 1 0
3 3 1 0 1
5 5 0 4 1
2 2 1 5 1
1 1 8 5 1
4 4 8 0 1

Google OR-Toolsのソルバーを使う方法

method='ortools'」をつけると、 Google OR-Tools のソルバー(近似解法)を使います。

注意

  • pip install ortoolsで Google OR-Tools をインストールしてください。
  • 距離行列(dist)の要素は整数にしてください。
python
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp
np.random.seed(0)
nodes = np.random.rand(20, 2) * 1000  # 20都市
dist = distance.cdist(nodes, nodes).astype(int)  # 距離行列
print(tsp(nodes, dist, method='ortools'))  # 近似解法
print(tsp(nodes, dist))  # 厳密解法(参考)

コストの総和(4099)は、2行目の厳密解(4072.0)より大きくなっています。

結果(コストの和と点番号のリスト)
(4099, [0, 11, 3, 6, 9, 10, 19, 4, 5, 18, 1, 14, 7, 17, 12, 8, 13, 15, 2, 16])
(4072.0, [0, 2, 16, 14, 7, 17, 12, 8, 13, 15, 11, 3, 6, 9, 10, 19, 4, 5, 1, 18])

データ

7
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
7
Help us understand the problem. What is going on with this article?