Julia(Graphs)で巡回セールスマン問題を解き、図示する方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(Graphs)で巡回セールスマン問題を解き、図示する方法を紹介します。

前提知識:Julia(Graphs)で重みつき最短経路問題を解き、図示する方法Julia(Graphs)でハミルトンサイクルを求め、図示する方法

 

準備

Graphs, GraphPlotColors, Randomを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

巡回セールスマン問題を解き、図示する方法

巡回セールスマン問題とは

日本の47都道府県を一度ずつすべて巡りたいセールスマンがいるとして、その移動コスト(距離、時間、交通費など)を最小化するようなルートは見つけられるでしょうか。

重みつきグラフにおいて、その重さの合計を最小化するようなハミルトンサイクルを探す問題は、巡回セールスマン問題(traveling salesman problem)と呼ばれています。

ハミルトンサイクルとは、与えられたグラフのすべての頂点を一度だけ通るようなサイクル(長さ3以上の単純な閉経路)のことです。つまり、巡回セールスマン問題とは、最短ハミルトンサイクルを探す問題、と言いかえられます。

 

簡単な例と関数作り

まず、次のような重みベクトルを与えた無向グラフを考えましょう。

各辺に書かれている数値が、辺の重みです。今回は1から5までの整数をランダムに指定しました。「Random.seed!(2022)」によって乱数のシードを与えたので、実行結果は再現されます。

 

最短のハミルトンサイクルを求めるにあたって、まずグラフのハミルトンサイクルをすべて求める関数を作りましょう。

「simplecycles_limited_length」という関数で、与えられた長さ以下のサイクルがすべて求められます。そのうち長さがグラフの頂点の数に等しいものがハミルトンサイクルです。

 

試してみると

確かにハミルトンサイクルたちが求められています。これらは向きが異なるだけで実質同じサイクルですが、一般にはたくさんのハミルトンサイクルが得られるでしょう。

 

得られたハミルトンサイクルから、最短のものを探しましょう。そのためにまず、サイクルの重みの合計を求める関数を作ります。

重みベクトルを距離行列に変換して、距離行列の情報を使って与えられたサイクルの重みを求めます。

これで与えられたサイクルの重み合計が計算できるようになりました。

 

これを使って、最短ハミルトンサイクルとその重み合計を求める関数を作ります。

「cycles_weight」として、各サイクルの重みを集めた配列を作っています。そして「argmin」でその配列の最小値を取る変数を取り出して、結果を返しました。

 

グラフと重みが与えられたとき、最短ハミルトンサイクルとその重み合計が求められます。

 

さらに、結果を最短経路問題ハミルトンサイクルを求める問題と同様にして図示してみましょう。

if文を使い、ハミルトンサイクルが存在するかどうかによって、表示結果を変えています。

 

これで巡回セールスマン問題の結果が、ひと目でわかるようになりました。

 

ハミルトンサイクルが存在しない例

 

このグラフ(bull graph)は、ハミルトンサイクルを持ちません。

きちんと適切な結果が表示されています。

 

正多面体グラフの最短ハミルトンサイクル

プラトン立体(正多面体)のグラフは、複数のハミルトンサイクルを持っています。各辺にランダムな重みを割り当て、その最短ハミルトンサイクルを求めてみましょう。

Graphs.jlでは、smallgraphという関数でプラトン立体のグラフが作れます。

 

正四面体

 

正六面体(立方体)

 

正八面体

 

正十二面体

 

正二十面体

 

 

以上、Julia(Graphs)で巡回セールスマン問題を解き、図示する方法を紹介してきました。

巡回セールスマン問題は、計算量理論ではNP困難であることが知られていて、原理的に計算時間がかかります。

ただし、今回見たような小さなサイズの問題ならば、正多面体グラフの最短ハミルトンサイクルをすべて求めて表示するのに8秒程度で済んでいます。グラフと重みを与えるだけで計算できるので、試してみてはいかがでしょうか。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

グラフ理論における経路、連結性とは?

Julia(Graphs)で最短経路問題を解き、図示する方法

Julia(Graphs)でハミルトンサイクルを求め、図示する方法

Julia(Graphs)で重みつき最短経路問題を解き、図示する方法