Clever Geek Handbook

トランスポートグラフ（概念）+ソースで最短パスを検索する

私はかつて、都市の地図に関連するプロジェクトを経験しました。 ルートとそれに対応する公共交通機関の停留所がある地図があるので、ポイントAからポイントBへの道を検索してみませんか？



ハードウェアが配置されるはずだったハードウェアのインターネットチャネルは非常に狭いため、検索はローカルで完全に実行する必要があります。つまり、サーバーの容量を使用しません。 さらに、もちろん、ユーザーの注意を失わずに、できるだけ早くユーザーに結果を提供したかったのです。



約1〜2時間座って何も考えられなかったので、ルートを考えることができるというアイデアが浮かんできました。 そして、ルートをポイントに向けると、非常に簡単なグラフが表示されます。

アイデアは良さそうで、私はそれが好きでした。



最初に行われたのは、サイトからルートを輸送することでした。 それから彼はカウントで動作するように設定しました。

これは難しい作業ではないことがわかりました。ルートのすべてのストップを取り、設定した半径内に他のルートのストップがあるかどうかを確認します。 半径は600m（最新バージョンでは400m）でした。これは、乗り換えが必要な場合に、ある駅から別の駅まで徒歩で苦痛なく歩くことができる推定距離です。 おそらく、この距離は、交差点での1つのストップから別のストップまでの距離がこの距離を超えないため、たとえば200mに短縮できます。



したがって、これらすべての操作の後、グラフを取得しました。これにより、あるルートから別のルートへのパスを十分にすばやく構築できます。 したがって、ある都市交通ルートから別の都市交通ルートへの遷移に関する情報を格納するグラフを取得しました。これは一種のメタグラフです。



数か月間、アルゴリズムは数回書き直されました。その後、最新の実装について詳しく説明します。



ビデオの品質はひどいですが、私はそれを改善する方法を見つけていません。







手順を完了するのにかかる平均時間：



gpt-0.009s、クリックポイントに最も近いストップを見つける

grt-0.001s、ルートからルートへの最短経路を見つける

apt-0.0001s、ストップとターニングポイントをルートに追加

all-0.01c、総パス検索実行時間





データ：





都市の特定の地図があり、都市の輸送ルート（90ルート）が印刷され、これらのルートに属する対応するストップの座標が印刷されています。



マップ上では、ルートは次のようになります。







退屈な基本構造の説明
データは、次の表の形式で表示されます。 



route( id, name, color, route_type_id ) //    route_type( id, name ) //   - , , , ,  route_points( id, marker_description_id, route_id, marker_order ) // ,    marker( id, x, y, address ) //  marker_category( id, name ) //     marker_description( id, name, marker_category_id, marker_id )


そのため、ルートを検索するたびに、ストップ間の距離（1ルート内）の計算に時間を無駄にせず、事前に計算して、対応するテーブルに書き込みます。

距離の表を取得します。 



  route_distance( route_id, //  roite_point_from_id, //    roite_point_to_id, //     distance //        )


次に、遷移のメタグラフを作成します。つまり、半径内に他のルートからのストップがあるルートストップを見つけます。 すでに述べたように、私は半径400メートルを選択しました。

処理結果はテーブルに書き込まれます。 



  route_cross_points( route_from_id, //    route_to_id, //    route_point_from_id, //    route_point_to_id, //    distance //   ) //,




PHPでデータをアップロードする





私のすべてのMYSQLベースのソフトウェアの実装は非常に遅かった。 基地から離れることにした。 データを配列にアンロードし、ソケットを介して作業することにしました。 私の場合、アップロードされたデータは約19MBのRAMを占有します。

メイン配列は$ graf配列です。 これは、次のキーの3次元配列です。 



  $r = $this->db->query(' select routeFrom rf, routeTo rt, markerFrom mf, markerTo mt, distance d from route_cross_points RCP '); $kf = 0; foreach($r as $k => $v) { $this->graf[(int)($v['rf'])][(int)($v['rt'])][] = array((int)($v['mf']), (int)($v['mt']), (float)($v['d'])); } $graf[$idFrom][$idTo] = array( 0 => $v1, //  ,        1 => $v2 //  ,        ..... );


1つのルートの停留所が他のルートの2つの停留所の間にあるか、ルートが1ポイント以上で接触している可能性があるため、転送の多くのオプションがあります。 したがって、$ v1、$ v2はこれらの転送です。



また、メモリ内には、ルート内の距離を持つ配列、つまり次の形式の配列があります。

$ routeDistance [$ idRoute] [$ pFrom] [$ pTo] =（float）;

どこで： 



  $rt = $this->db->query(' select route_id rni, POINT1 p1, POINT2 p2, distance d from route_distance '); foreach($rt as $k => $v) { $this->routeDistance[(int)($v['rni'])][(int)($v['p1'])][(int)($v['p2'])] = (int)($v['d']); }




道を見つける





検索を開始するには、行く先と場所を見つける必要があります。 どこ（$ idFrom）およびどこ（$ idTo）から最も近い停車地を見つけたら、その停留所がルートに属していることを確認し、道を見つけようとします。



1つの変更でルートを見つけるには： 



  if(isset($graf[$idFrom][$idTo])) { //      1   . }


たとえば、2つの転送があるパスの検索は、次のように実装されます。 



  foreach($graf[$idFrom] as $keyOne => $one) { if(isset($graf[$idTo][$keyOne])) { //        ,   ,        . } }


したがって、たとえば3回の転送でパスを見つけるには、次のように記述します。 



  foreach($graf[$idFrom] as $keyOne => $one) //             { foreach($graf[$idFrom] as $keyTwo => $two)//           { if(isset($graf[$keyOne][$keyTwo])){ } } }




これらの操作の後、$ id1-> $ id2-> $ id3-> $ id4という形式のルートのセットを取得します。 ここで、$ id *はルートIDです。

次に、どのパスが最も速いかを理解する必要があります。 開始停止（$ pStart）と終了停止（$ pEnd）があります。 また、$ grafテーブルから、転送ポイント（場所、場所、距離）が$ v1、$ v2の値であることがわかります。

$ id1-> $ id2に書き込みます。 すべての転送のデータを追加します。 



  $id1($pStart, $v1['from']) -> $id2($v1['to'], $pEnd) $id1($pStart, $v2['from']) -> $id2($v2['to'], $pEnd) $id1($pStart, $v3['from']) -> $id2($v3['to'], $pEnd)


ルートを評価するには、すべてを追加する必要があることが少しわかります。 



  $routeDistance[$id1][$pStart][$v1['from']] + $v1['distance'] + $routeDistance[$id2][$v1['to']][$pEnd]; $routeDistance[$id1][$pStart][$v2['from']] + $v2['distance'] + $routeDistance[$id2][$v2['to']][$pEnd]; $routeDistance[$id1][$pStart][$v3['from']] + $v3['distance'] + $routeDistance[$id2][$v3['to']][$pEnd];


$ routeDistance [$ id1] [$ pStart] [$ v1 ['from']]-ルート内の距離。

$ v1 ['distance']-抽象単位での移植に費やされる時間。



したがって、計算された量の最小値は、これが望ましいパスになります。 次に、ルート内にあるがルートへの入り口と出口の間のストップを復元します。



例





便宜上、いくつかのルートを選択します。







ルートをポイントに変換してグラフを取得します。







ルート2から5に到達する必要があるとします。

グラフによると、このようなパスの選択が得られます。







さらに、受信したルートを処理します。 どのルートが最速かを調べる必要があります。



ルートの「魅力」の値の計算：

  1. ルートの開始の停止と、別のルートへの転送のすべての可能な停止を取得します。 route_distanceテーブルを使用して、ルート内の開始停止から転送の停止までのパスの長さを見つけます。
  2. 次に、移植の時期を考慮する必要があります。 route_cross_pointテーブルに従って計算された長さに、変更するストップと変更するストップの間の長さを追加します。
  3. ルートごとに繰り返します。




サンプルから最初の行を取得します







$ routeDistance [2] [p.1] [p.3] + d1 + $ routeDistance [3] [p.5] [p.6] + d3 + $ routeDistance [5] [p.7] [p.8 ] =（フロート）

$ routeDistance [2] [p.1] [p.4] + d2 + $ routeDistance [3] [p.5] [p.6] + d3 + $ routeDistance [5] [p.7] [p.8 ] =（フロート）

$ routeDistance-ルート内の距離。

d *-移植の時間。

p.1-出発地点から停止します。

p.8-行き先を止めます。

d1-p.3とp.5の間の距離



最小数が最善の方法です。



不足しているものと開発方法：





-アルゴリズムは、既存の道路網を考慮せず、地点Aから交通機関の停止までの歩行者ルート、したがって、受信した経路から地点Bまでの公共交通機関の最後の停車地を設定しません。

-もちろん、ルートのコストをさらに計算し、必要に応じて、オプションでルートを選択するための基準（最小コスト、時間、転送など）の選択肢を入力できますが、デフォルトではターゲット基準を転送の最小と見なします。

-パスの長さに応じて運賃が導入された場合、アルゴリズムもそれほど追加する必要はありません。



ソースのダウンロード 。 開梱します。 パスにロシア語の文字を含めることはできません。


More articles:


All Articles