MATHEMATICA 組込みシンボル

FindShortestTour

すべての

を1回ずつ訪れる場合の総距離を最小化するような

の順序を求める．

詳細

FindShortestTourはの形式のリストを返す．は求まったコースの長さ，は順番である．

可能なオプション：

	DistanceFunction	オブジェクトのペアに適用する距離関数
	Method	使用するメソッド

は数または数のリストでよい．この場合，使用されるデフォルトの距離関数はEuclideanDistanceである．

が文字列の場合，使用されるデフォルトの距離関数はEditDistanceである．

点の数が少ない場合，一般にFindShortestTourは最短コースを求める．点の数が多い場合でも，少なくとも最短に近い長さのコースが通常求められる．

Methodオプションの使用可能な設定値には，，，，，，，，，，がある．

ユークリッド空間における点の数が少ない場合は必ず最短コースを与える法が使われる．

例題

すべて閉じる

例 (2)

平面上の6点を通る最短距離と点の順序を求める：

点のリストを指定する：

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

コースをプロットする：

平面上の6点を通る最短距離と点の順序を求める：

In[1]:=

Out[1]=

点のリストを指定する：

In[1]:=

In[2]:=

Out[2]=

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

In[3]:=

Out[3]=

コースをプロットする：

In[4]:=

Out[4]=

スコープ (2)

3D空間の点を通る最短コースを求める：

文字列のリストを通る最短コースを求める：

一般化と拡張 (1)

（対称の）隣接行列に基づいてDistanceFunctionを使う：

オプション (4)

以下で，

格子上で座標が互いに素であるすべての位置を求める：

2Dリアル入力のデフォルトである

メソッドを使って最短コースを求める：

2Dあるいはリアル以外の入力のデフォルトである

メソッドを使って最短コースを求める：

アルゴリズムは改善のために辺の終点の交換を行う：

（凸法，最安挿入，角度選択）は

の点を意図する：

アルゴリズムは，ある点からまだ訪れていない中で最も近い近傍に移動する：

は既知の上限を加えた

アルゴリズムの変形である：

はコースを最短にするためにシミュレーションをしたアニーリングを使う：

デフォルトで，EditDistanceは文字列に使われる：

次は，「川」を渡る際にペナルティが設けられた，100個の点を通る最短コースを求める：

次はコースのプロットで「川」が赤で示されている：

次は6個の点の間の疎な距離行列を定義し，最短コースを求める：

次は最短コース（赤）だけでなく各辺の距離もプロットしている：

アプリケーション (6)

平面上の50の点をランダムに訪れる最短コースを求める：

3Dでランダムな50の点を訪れる最短コースを求める：

座標が互いに素である2D上の点を通る最短コースを求める：

座標が互いに素である3D中の点を通る最短コースを求める：

ヨーロッパ諸国の名前を通る「最短コース」を求める：

巡回セールスマンのヨーロッパツアーのコースを求める：

おもしろい例題 (1)

世界中のすべての国を回るツアーを計画する：

ツアーを可視化する：