1

SDK 3.0 以降、iPhone の GPS 機能を簡単に使用できますが、Google のマップの使用は明示的に禁止されています。これには 2 つの意味があると思います。

  1. マップは自分で用意する必要があります
  2. 最短ルートを自分で計算する必要があります。

最短経路の計算は長年数学者を困惑させてきましたが、Tom Tom と Google の両方が素晴らしい仕事をしているので、その問題は解決されたようです。私自身は数学者ではありませんが、ネットで検索していると、 Dijkstra Algorithmに出くわしました。このアルゴリズムを iPhone のマップのようなアプリでうまく使用した人はいますか? 私/コミュニティと共有してもよろしいですか？これは正しいアプローチですか、それとも他のオプションですか? ご検討いただきありがとうございます。

4

7 に答える 7

5

ダイクストラのアルゴリズムが実世界のマッピングに役立つとは思いません。Tom Leys が言ったように (私は彼の投稿にコメントしますが、それを行う担当者がいません)、開始点が 1 つ必要なためです。開始点が変更された場合、すべてを再計算する必要があります。これは、非常に大きなデータ セットの iPhone のようなデバイスでは非常に遅くなると思います。

于 2009-05-18T07:52:29.677 に答える
4

ダイクストラのアルゴリズムは、(単一の開始ノードから) すべてのノードへの最短パスを見つけるためのものです。ゲーム プログラマーは、A* などの直接検索を使用します。Dijkstra が最初に開始位置に最も近いノードを処理する場合、A* は終了位置に最も近いと推定されるノードを処理します。

これが機能する方法は、任意の位置から終点までの安価な「推定」関数を提供することです。良い例は、鳥がそこに到達するために飛ぶ距離です。A* は、これを各ノードの開始からの現在の距離に加算し、最短経路上にあると思われるノードを選択します。

見積もりが適切であるほど、適切なパスを見つけるのにかかる時間が短くなります。この時間が長すぎる場合は、簡単な地図で経路検索を実行してから、より複雑な地図で別の経路検索を実行して、簡単な地図で見つけた場所間のルートを見つけることができます。

更新 よく検索した結果、 A* に関する記事を見つけました。

于 2009-05-18T07:49:32.210 に答える
3

ダイクストラのアルゴリズムは、n 個のノードと m 個のエッジ (単一パスの場合) に対して O(m log n) であり、ネットワーク ルーティングに使用するのに十分効率的です。これは、1 回限りの計算に使用するのに十分効率的であることを意味します。

簡単に言うと、ダイクストラのアルゴリズムは次のように機能します。

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

一般に信じられていることとは反対に、Dijkstra のアルゴリズムは必ずしもすべてのペアの最短経路の計算ではありませんが、これを行うように適応させることはできます。

道路と交差点のグラフと交差点間の距離を取得する必要があります。このデータがあれば、ダイクストラのアルゴリズムを使用して最短ルートを計算できます。

于 2009-05-18T09:53:52.670 に答える
1

A* アルゴリズムを使用したルートの計算は、オフライン マップ データを使用する iPhone で十分高速です。私はこれを商業的に行った経験があります。ウィキペディアに記載されている A* アルゴリズムを使用し、道路網をメモリに保持して再利用します。いったんロードされると、スペインやカナダの西半分のような広いエリアでもルーティングは事実上瞬時に行われます。

OpenStreetMap または他の場所からデータを取得し、それを有向グラフに変換します (知っている人によると、これが正しい方法です) 同じ ID を持つポイントを共有する 2 つの道路が結合されていると仮定します。予想される速度に基づいてさまざまな種類の道路に重みを割り当てます。道路の一部が一方通行の場合は、単一の円弧のみを作成します。双方向の道路には、各方向に 1 つずつ、合計 2 つの円弧があります。危険な方向転換を防ぐためのアドホック コードと、ルーティング制限の実装を除けば、これでほぼすべてです。

于 2012-07-20T13:52:20.840 に答える
1

テクノロジー totomtom コールの「IQ ルート」を見ると、1 日の時間帯ごとに実際の速度と移動時間が測定されます。これにより、到着時間がより正確になります。したがって、予想される到着時間は、より事実に基づいています http://www.tomtom.com/page/iq-routes

于 2011-08-21T10:42:34.733 に答える
0

これについては、ここで以前に説明しました:マップ上のポイント a からポイント b への方向を計算するアルゴリズムは何ですか?

于 2009-06-18T10:40:46.913 に答える
0

CloudMadeをご覧ください。彼らは、現在の場所に基づいたナビゲーションを可能にする iPhone および iPad 向けの無料サービスを提供しています。オープンストリートマップ上に構築されており、独自のマップスタイルを作成するなどの気の利いた機能がいくつかあります. 時々少し遅くなりますが、完全に無料です。

于 2012-02-27T10:33:17.627 に答える