巡回セールスマン問題(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のもとで提供されています。