FindShortestTour

FindShortestTour[{v1,v2,}]
すべての を1回ずつ訪れる場合の総距離を最小化するような の順序を求めようとする.

FindShortestTour[graph]
各頂点を1回訪れる場合に全長を最短にする graph 中の頂点の順番を求めようとする.

詳細とオプション詳細とオプション

  • FindShortestTourは,巡回セールスマン問題(TSP)としても知られている.
  • FindShortestTourの形式のリストを返す.は求まったコースの長さ,は順番である.
  • 可能なオプション
  • DistanceFunctionAutomaticオブジェクトのペアに適用する関数
    MethodAutomatic使用するメソッド
  • に依存するDistanceFunctionの自動設定には以下がある.
  • EuclideanDistance数のリストの数
    EditDistance文字列
    GeoDistance地理的位置
  • graph については,距離はGraphDistanceであるとみなされる.これは,重みのないグラフについては最短距離の長さ,重み付きグラフについては重みの総和である.

例題例題すべて開くすべて閉じる

  (2)  (2)

平面上の点を通る最短距離の長さとその順序を求める:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

求まったコースに沿って点を並べる:

In[3]:=
Click for copyable input
Out[3]=

コースをプロットする:

In[4]:=
Click for copyable input
Out[4]=

グラフ中の最短コース求める:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

コースをハイライトする:

In[3]:=
Click for copyable input
Out[3]=
2007年に導入
(6.0)
| 2014年に修正
(10.0)