SQL Server のグラフで巡回セールスマン問題をやってみる

SQL Server のグラフを色々試していくシリーズ。

2回目は巡回セールスマン問題(traveling salesman problem)です。
最短経路で目的地を全部回りたいってやつですね。

今回のお題はまた阪急電車です。
梅田からスタートして、

十三
西宮北口
神戸三宮
宝塚
高槻
河原町

の全ての駅で1度は降りてから梅田に帰ってくる。
これの最安値経路を求めたいと思います。

雰囲気こんな感じになるかな？
梅田 -> 河原町 -> 高槻 -> 十三 -> 神戸三宮 -> 西宮北口 -> 宝塚 -> 梅田

また比較するために通常のテーブルでも試してみます。
相変わらず可視化は Neo4j で。
f:id:odashinsuke:20171227135649j:plain
今回は運賃なので、全ての駅が互いに繋がっている状態です。

ノードが駅でエッジが運賃です。

create table G_駅 (
    駅名 nvarchar(10) not null
) as node
create table G_運賃 (
    価格 int not null
) as edge

insert into G_駅 values 
(N'梅田'), (N'十三'), (N'西宮北口'), (N'神戸三宮'), (N'宝塚'), (N'高槻市'), (N'河原町')

declare @e1 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'梅田')
declare @e2 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'十三')
declare @e3 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'西宮北口')
declare @e4 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'神戸三宮')
declare @e5 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'宝塚')
declare @e6 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'高槻市')
declare @e7 nvarchar(max) = (select $node_id from G_駅 where 駅名 = N'河原町')

insert into G_運賃 values 
(@e1, @e2, 150), 
(@e1, @e3, 270), 
(@e1, @e4, 320), 
(@e1, @e5, 280), 
(@e1, @e6, 280), 
(@e1, @e7, 400), 
(@e2, @e1, 150), 
(@e2, @e3, 220), 
(@e2, @e4, 320), 
(@e2, @e5, 280), 
(@e2, @e6, 280), 
(@e2, @e7, 400),
(@e3, @e2, 220), 
(@e3, @e1, 270), 
(@e3, @e4, 270), 
(@e3, @e5, 190), 
(@e3, @e6, 370), 
(@e3, @e7, 470),
(@e4, @e2, 320), 
(@e4, @e3, 270), 
(@e4, @e1, 320), 
(@e4, @e5, 280), 
(@e4, @e6, 400), 
(@e4, @e7, 620), 
(@e5, @e2, 280), 
(@e5, @e3, 190), 
(@e5, @e4, 280), 
(@e5, @e1, 280), 
(@e5, @e6, 370), 
(@e5, @e7, 530), 
(@e6, @e2, 280), 
(@e6, @e3, 370), 
(@e6, @e4, 400), 
(@e6, @e5, 370), 
(@e6, @e1, 280), 
(@e6, @e7, 280), 
(@e7, @e2, 400), 
(@e7, @e3, 470), 
(@e7, @e4, 620), 
(@e7, @e5, 530), 
(@e7, @e6, 280), 
(@e7, @e1, 400)

ついでに、通常のテーブルの方も作ってしまいましょう。

create table 運賃 (
    発駅 nvarchar(10) not null, 
    着駅 nvarchar(10) not null, 
    価格 int not null
)

insert into 運賃 values 
(N'梅田', N'十三', 150), 
(N'梅田', N'西宮北口', 270), 
(N'梅田', N'神戸三宮', 320), 
(N'梅田', N'宝塚', 280), 
(N'梅田', N'高槻市', 280), 
(N'梅田', N'河原町', 400), 
(N'十三', N'梅田', 150), 
(N'十三', N'西宮北口', 220), 
(N'十三', N'神戸三宮', 320), 
(N'十三', N'宝塚', 280), 
(N'十三', N'高槻市', 280), 
(N'十三', N'河原町', 400),
(N'西宮北口', N'十三', 220), 
(N'西宮北口', N'梅田', 270), 
(N'西宮北口', N'神戸三宮', 270), 
(N'西宮北口', N'宝塚', 190), 
(N'西宮北口', N'高槻市', 370), 
(N'西宮北口', N'河原町', 470),
(N'神戸三宮', N'十三', 320), 
(N'神戸三宮', N'西宮北口', 270), 
(N'神戸三宮', N'梅田', 320), 
(N'神戸三宮', N'宝塚', 280), 
(N'神戸三宮', N'高槻市', 400), 
(N'神戸三宮', N'河原町', 620), 
(N'宝塚', N'十三', 280), 
(N'宝塚', N'西宮北口', 190), 
(N'宝塚', N'神戸三宮', 280), 
(N'宝塚', N'梅田', 280), 
(N'宝塚', N'高槻市', 370), 
(N'宝塚', N'河原町', 530), 
(N'高槻市', N'十三', 280), 
(N'高槻市', N'西宮北口', 370), 
(N'高槻市', N'神戸三宮', 400), 
(N'高槻市', N'宝塚', 370), 
(N'高槻市', N'梅田', 280), 
(N'高槻市', N'河原町', 280), 
(N'河原町', N'十三', 400), 
(N'河原町', N'西宮北口', 470), 
(N'河原町', N'神戸三宮', 620), 
(N'河原町', N'宝塚', 530), 
(N'河原町', N'高槻市', 280), 
(N'河原町', N'梅田', 400)

前回はグラフのクエリで再帰を使ってしまったので、通常のテーブルとの違いがあんまり分かりませんでした。
今回は再帰を使わずに書いてみます。

こんな感じでしょうか。

select top(10)
  concat(開始梅田.駅名, '-', N1.駅名, '-', N2.駅名, '-', N3.駅名, '-', N4.駅名, '-', N5.駅名, '-', N6.駅名, '-', 終了梅田.駅名) as ルート, 
  E1.価格 + E2.価格 + E3.価格 + E4.価格 + E5.価格 + E6.価格 + E7.価格 as 価格 
from G_駅 as 開始梅田, 
  G_運賃 E1, G_駅 as N1, 
  G_運賃 E2, G_駅 as N2,
  G_運賃 E3, G_駅 as N3,
  G_運賃 E4, G_駅 as N4,
  G_運賃 E5, G_駅 as N5,
  G_運賃 E6, G_駅 as N6,
  G_運賃 E7, G_駅 as 終了梅田
where
  開始梅田.駅名 = N'梅田' and 終了梅田.駅名 = N'梅田'
  and match ( 開始梅田 - (E1) -> N1 - (E2) -> N2 - (E3) -> N3 - (E4) -> N4 - (E5) -> N5 - (E6) -> N6 - (E7) -> 終了梅田)
  and N1.駅名 <> 開始梅田.駅名
  and N2.駅名 <> 開始梅田.駅名
  and N2.駅名 <> N1.駅名
  and N3.駅名 <> 開始梅田.駅名
  and N3.駅名 <> N1.駅名
  and N3.駅名 <> N2.駅名
  and N4.駅名 <> 開始梅田.駅名
  and N4.駅名 <> N1.駅名
  and N4.駅名 <> N2.駅名
  and N4.駅名 <> N3.駅名
  and N5.駅名 <> 開始梅田.駅名
  and N5.駅名 <> N1.駅名
  and N5.駅名 <> N2.駅名
  and N5.駅名 <> N3.駅名
  and N5.駅名 <> N4.駅名
  and N6.駅名 <> 開始梅田.駅名
  and N6.駅名 <> N1.駅名
  and N6.駅名 <> N2.駅名
  and N6.駅名 <> N3.駅名
  and N6.駅名 <> N4.駅名
  and N6.駅名 <> N5.駅名
order by 2

f:id:odashinsuke:20171227141113j:plain
開始の梅田と終了の梅田は置いといて、その間を 6つのノード(駅)と7つのエッジ(運賃)で繋げていく。
6つのノードは、今までに出てきた駅名は除くという条件を延々と付けていくと重複無しの移動ルートが取れます。
※ちなみにデータ上、発駅と着駅が同じになるデータ*1は入れていないので、一つ前の駅と同じ*2という条件は省けますが意味の伝わりやすさの観点から入れてます。

その中で、運賃.価格の合計を安い順に並べて Top で引っ張るっという感じです。
愚直に書いてますが、まあ意味は分かりやすいかな？

通常のテーブルはこちら。

select top(10)
  concat(開始梅田.発駅, '-', T1.発駅, '-', T2.発駅, '-', T3.発駅, '-', T4.発駅, '-', T5.発駅, '-', 終了梅田.発駅, '-', 終了梅田.着駅) as ルート, 
  開始梅田.価格 + T1.価格 + T2.価格 + T3.価格 + T4.価格 + T5.価格 + 終了梅田.価格 as 価格 
from
  運賃 開始梅田 
  inner join 運賃 T1 on 開始梅田.着駅 = T1.発駅 
  inner join 運賃 T2 on T1.着駅 = T2.発駅
  inner join 運賃 T3 on T2.着駅 = T3.発駅 
  inner join 運賃 T4 on T3.着駅 = T4.発駅 
  inner join 運賃 T5 on T4.着駅 = T5.発駅
  inner join 運賃 終了梅田 on T5.着駅 = 終了梅田.発駅
where
  開始梅田.発駅 = N'梅田' and 終了梅田.着駅 = N'梅田'
  and 開始梅田.着駅 <> N'梅田'
  and T1.着駅 <> 開始梅田.発駅
  and T2.着駅 <> 開始梅田.発駅
  and T2.着駅 <> T1.発駅
  and T3.着駅 <> 開始梅田.発駅
  and T3.着駅 <> T1.発駅
  and T3.着駅 <> T2.発駅
  and T4.着駅 <> 開始梅田.発駅
  and T4.着駅 <> T1.発駅
  and T4.着駅 <> T2.発駅
  and T4.着駅 <> T3.発駅
  and T5.着駅 <> 開始梅田.発駅
  and T5.着駅 <> T1.発駅
  and T5.着駅 <> T2.発駅
  and T5.着駅 <> T3.発駅
  and T5.着駅 <> T4.発駅
order by 2

f:id:odashinsuke:20171227141500j:plain
match の部分が inner join on に置き換わるイメージですね。
パッと見的には、グラフの match の方が繋がりは分かりやすいかな？
ただ、グラフの場合は From で指定するテーブルが多くなるのはイマイチですね。

通常のテーブルのみですが、再帰版も置いときます。

with cte as (
select 発駅, 着駅, 価格, cast(concat(発駅, '-', 着駅) as nvarchar(max)) as ルート, 1 as cnt from 運賃 where 発駅 = N'梅田'
union all
select 運賃.発駅, 運賃.着駅, cte.価格 + 運賃.価格, cast(concat(cte.ルート, '-', 運賃.着駅) as nvarchar(max)), cte.cnt + 1
from cte inner join 運賃 on cte.着駅 = 運賃.発駅 and charindex(運賃.着駅, cte.ルート) = 0
)
select 
  concat(cte.ルート, '-', 運賃.着駅) as ルート
  , cte.価格 + 運賃.価格 as 合計金額 
from 
  cte inner join 運賃 on cte.着駅 = 運賃.発駅 and 運賃.着駅 = N'梅田' 
where cnt = 6  
order by 2

再帰を使う場合は、最後の梅田を再帰外にしています、梅田だけ2回通る(最初と最後)を表現するのが大変だったので。
今回も試せる環境は用意しましたので、興味ある方はクエリ書いて試してください。 TSQL Runner Q20180123
一応 Neo4j の cypher も貼っときますが、梅田だけ2回通るのを表現出来なくてズルしてます。
梅田=>～(他の駅全て)=>十三=>梅田という取り方になってます。
上手く cypher で表現出来る方いたら教えてください～。
データ

create (s1:F_Station {name:"梅田"}), 
  (s2:F_Station {name:"十三"}), 
  (s3:F_Station {name:"西宮北口"}), 
  (s4:F_Station {name:"神戸三宮"}), 
  (s5:F_Station {name:"宝塚"}), 
  (s6:F_Station {name:"高槻市"}), 
  (s7:F_Station {name:"河原町"}),
  (s1)-[:From {cost:150}]->(s2), 
  (s1)-[:From {cost:270}]->(s3),
  (s1)-[:From {cost:320}]->(s4),
  (s1)-[:From {cost:280}]->(s5),
  (s1)-[:From {cost:280}]->(s6),
  (s1)-[:From {cost:400}]->(s7),
  (s2)-[:From {cost:150}]->(s1), 
  (s2)-[:From {cost:220}]->(s3),
  (s2)-[:From {cost:320}]->(s4),
  (s2)-[:From {cost:280}]->(s5),
  (s2)-[:From {cost:280}]->(s6),
  (s2)-[:From {cost:400}]->(s7),
  (s3)-[:From {cost:220}]->(s2), 
  (s3)-[:From {cost:270}]->(s1),
  (s3)-[:From {cost:270}]->(s4),
  (s3)-[:From {cost:190}]->(s5),
  (s3)-[:From {cost:370}]->(s6),
  (s3)-[:From {cost:470}]->(s7),
  (s4)-[:From {cost:320}]->(s2), 
  (s4)-[:From {cost:270}]->(s3),
  (s4)-[:From {cost:320}]->(s1),
  (s4)-[:From {cost:280}]->(s5),
  (s4)-[:From {cost:400}]->(s6),
  (s4)-[:From {cost:620}]->(s7),
  (s5)-[:From {cost:280}]->(s2), 
  (s5)-[:From {cost:190}]->(s3),
  (s5)-[:From {cost:280}]->(s4),
  (s5)-[:From {cost:280}]->(s1),
  (s5)-[:From {cost:370}]->(s6),
  (s5)-[:From {cost:530}]->(s7),
  (s6)-[:From {cost:280}]->(s2), 
  (s6)-[:From {cost:370}]->(s3),
  (s6)-[:From {cost:400}]->(s4),
  (s6)-[:From {cost:370}]->(s5),
  (s6)-[:From {cost:280}]->(s1),
  (s6)-[:From {cost:280}]->(s7),
  (s7)-[:From {cost:400}]->(s2), 
  (s7)-[:From {cost:470}]->(s3),
  (s7)-[:From {cost:620}]->(s4),
  (s7)-[:From {cost:530}]->(s5),
  (s7)-[:From {cost:280}]->(s6),
  (s7)-[:From {cost:400}]->(s1)
RETURN s1, s2, s3, s4, s5, s6, s7

梅田=>～=>十三=>梅田

MATCH (from:F_Station {name:"梅田"}), 
  path = (from)-[:From*6]->(:F_Station {name:"十三"}), 
  (:F_Station {name:"十三"})-[last:From]->(from)
WHERE ALL(n IN NODES(path) WHERE SINGLE(m IN NODES(path) WHERE m = n))
RETURN path, REDUCE(cost = 0, edge IN RELATIONSHIPS(path) | cost + edge.cost) + last.cost AS totalCost
ORDER BY totalCost ASC
LIMIT 1

*1:運賃的には0円？入場券で150円

*2:N2.駅名<>N1.駅名はあり得ない