巡回セールスマン問題(TSP)

tsp機能を利用するためには以下の宣言文が必要です:

CREATE OR REPLACE FUNCTION tsp(sql text, ids varchar, source_id integer)
	RETURNS SETOF path_result

引数:

sql: SQLのクエリーです。以下に続くカラムからなる行セットを返します:

• source_id: 始点ノードの識別子[int4]
• x: 始点ノードのx座標
• y: 始点ノードのy座標

ids: カンマで区切られたノードID(int4)の文字列

source_id: 始点ノードのID[int4] 関数は行のセットを返します。それぞれの交差しているエッジあたり1行、また終点を含む追加行が1行あります。各行のカラム構成は:

• vertex_id: 各エッジの始点ノードIDです。経路探索の終点ノードIDを含む最後のエッジの後に、もう一行あります。(最後のエッジの終点ノードから続くエッジがないことを示すため)
• edge_id: 未使用、通常は0
• cost: 未使用、常に0

例:

SELECT * FROM tsp('SELECT distinct source AS source_id, 
                   x1::double precision AS x, 
                   y1::double precision AS y FROM dourol 
         WHERE source IN (83593,66059,10549,18842,13)',
                   '83593,66059,10549,18842,13', 10549);

 vertex_id | edge_id | cost
-----------+---------+------
     10549 |       0 |    0
     83593 |       0 |    0
     66059 |       0 |    0
     18842 |       0 |    0
        13 |       0 |    0
(5 rows)

あとがき: ノードIDカラムは最短経路探索に使用することができます。

---

この日本語訳の著作権は、日本ユニシス株式会社に帰属しています。また、この日本語訳は、GNU FDLのもとで提供されています。