16 pgRouting in Debian6 6 - ルートの検索2 A-Star

6.2. A-Star
A-Star アルゴリズムはもう一つの良く知られたルーティングアルゴリズムです。
それぞれのネットワークリンクの search と trget へ位置情報を追加します。
検索 target により近いよりよいリンクの最短経路を検索することができます。

Prerequisites は、既に設定済みです。

Function with parameters

最短経路 A-Star 関数は、Dijkstar 関数ととても似ていて、target 検索に近いリンクです。
この検索の計算方法は、組み込まれているので、組み込み関数に変えたいときは pgRouting をコンパイルしなおす必要があります。


6.2.1. Core

routing2=# SELECT * FROM shortest_path_astar('
SELECT gid as id, source::integer,
target::integer,
length::double precision as cost,
x1, y1, x2, y2 FROM ways',
10, 1, false, false);

 vertex_id | edge_id |        cost        
-----------+---------+--------------------
        10 |       8 |  0.346119164295792
         9 |      23 | 0.0146912365339526
        11 |      22 |  0.075644096442472
        22 |      21 | 0.0618382434046277
        21 |      20 | 0.0915961112943772
        20 |      19 | 0.0790971710844567
        19 |     111 | 0.0382842275772729
        96 |     112 |  0.286175933407192
        97 |     113 | 0.0520291616070434
       100 |     565 |  0.289789710373784
       490 |  380609 |   0.76797799806671
       123 |  380608 |  0.735939901886778
       186 |     215 |  0.226197723036394
        30 |      36 |  0.634325320625154
         1 |      -1 |                  0
(15 行)

~
(stdin):q


Wrapper function WITH bounding box

Wrapper 関数は、遷移や境界線 box 制限などで core 関数を拡張します。

routing2=# SELECT gid, AsText(the_geom) AS the_geom FROM astar_sp_delta('ways', 10, 1, 0.1);

  gid   |                                         the_geom                                                                                                                  
--------+----------------------------------------------------------------------------------------------------------------
      8 | MULTILINESTRING((139.7577762 35.6405846,139.7602379 35.6429693))
     23 | MULTILINESTRING((139.7576138 35.6405785,139.7577762 35.6405846))
     22 | MULTILINESTRING((139.7567768 35.6405692,139.7576138 35.6405785))
     21 | MULTILINESTRING((139.7560925 35.6405677,139.7567768 35.6405692))
     20 | MULTILINESTRING((139.7550789 35.6405698,139.7560925 35.6405677))
     19 | MULTILINESTRING((139.7542037 35.64058,139.7543194 35.6405713,139.7550789 35.6405698))
    111 | MULTILINESTRING((139.7542037 35.64058,139.7540437 35.6402612))
    112 | MULTILINESTRING((139.7540437 35.6402612,139.7535339 35.6392546,139.7528491 35.6378777))
    113 | MULTILINESTRING((139.7528491 35.6378777,139.7526395 35.6374419))
    565 | MULTILINESTRING((139.7526395 35.6374419,139.75219 35.6368954,139.7517603 35.6360734,139.7513313 35.6350625))
 380609 | MULTILINESTRING((139.7545699 35.6414479,139.7542355 35.6407687,139.7528655 35.6380556,139.7518411 35.6360552,139.7513313 35.6350625))
(stdin):q

Note
●現在、box 境界線なしの A-Star のための wrapper 関数はありません。従って、box 境界線は、パフォーマンスを向上するためにとても有効です。
box 境界線が必要ないなら、Dijkstra でいつも十分です。
● OSM データの投影法は度数なので、例えば、0.1度足した始点と終点 vertex を含む box 境界線を設定します。