Qiita Conference 2025

Qiita史上最多!豪華12名のゲストが登壇

特別講演ゲスト(敬称略)

ymrl、成瀬允宣、鹿野壮、伊藤淳一、uhyo、徳丸浩、ミノ駆動、みのるん、桜庭洋之、tenntenn、けんちょん、こにふぁー

7
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-07-10

典型問題と実行方法

巡回セールスマン問題

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
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up

Qiita Conference 2025 will be held!: 4/23(wed) - 4/25(Fri)

Qiita Conference is the largest tech conference in Qiita!

Keynote Speaker

ymrl、Masanobu Naruse, Takeshi Kano, Junichi Ito, uhyo, Hiroshi Tokumaru, MinoDriven, Minorun, Hiroyuki Sakuraba, tenntenn, drken, konifar

View event details
7
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?