0

GPS 位置の 20,000 ポイントの配列があります。

これらは、チェックする必要がある森の小道上のポイントを表しています。何 km の森の小道を確認する必要があるかを把握する必要があります。

  1. ポイントをルートにグループ化します。
  2. 各ルートのショートパスを測定

どのアルゴリズムをどの順序で検討する必要があるか。

最短パスを取得してルートに分割するか、ルートを取得してからそれぞれの短縮パスを見つける必要がありますか。

ここに画像の説明を入力

4

3 に答える 3

2

このソリューションは、ポイントしかなく、ポイントがどの森の小道にあり、どの順序であるかなどがわからないことを前提としています。

私はこのようにしてみます：

1 各ノードをリンクで相互に接続し、リンクの重みとして距離を使用します (または、ノード間をメートル単位で 2km/h で移動する場合は秒数を使用します。森の中を歩くのが遅いと仮定すると、低速です)既存の林道）

2 森に困難がある場合 (山、谷、川):

2a: 上昇/下降: 標高差を使用してリンクの重みを上げ、屋外計画リソースを調べ、何メートルの上昇が移動時間に影響を与えるかを調べます。(300m は概算で 1 時間追加される可能性があります)

2b: 谷、川、またはその他の制限: 1 つのポイントから別のポイントに直接移動できない場合は、再度ウェイトを上げるか、リンクを削除します。(たとえば、谷をポリゴンとして描画し、ポリゴンを横切るすべてのリンクを削除します)

森の中にはすでに小道/林道がありますか?
はい、モデル (グラフ) にリンクとして描画し、リンクの重みを使用します (例: 時速 5 km の歩行速度)。

これで、ノード間の移動速度に関連するリンクの重みが現実的であることが望ましいノードとリンクを含むグラフが作成されました。

ショート パス (ダイクストラス アルゴリズム) と巡回セールスマン アルゴリズムを使用します。

それが大変な作業である場合 (コンピューター サイエンスの学位を取得した人にとっては数か月かかる場合があります)、手動で計画します。1000 x 1000m のラスターを描画し、人間の知性に仕事を任せます。

歩行によってチェックする必要がある 20,000 点は多大な労力を必要とするため、自動計画と人間の経験を評価することはさらに価値があります。両方のバリアントを試して、どちらがより効率的かを確認してください。

(私は、アウトドアの経験があり、カントリー ラインとチェック ポイントが記載された優れた地図を持っている場合、より良い仕事をすることができると思います。

于 2013-10-02T15:44:28.687 に答える
0

この質問は、制約付きの配車ルートの問題に似ているようです。たとえば、貯蓄アルゴリズムのヒューリスティックを試すことができます: http://neo.lcc.uma.es/vrp/solution-methods/heuristics/ Savings- algorithms/ 。

于 2013-10-02T09:21:34.567 に答える
0

私の他の魂：

これは、まだ投稿していない情報があることを前提としています。

おそらく、ポイントの座標だけでなく、より多くの情報を持っているでしょう。このポイントを作成したのは誰ですか? グラフィックでは、パス上にあるように見えます。車でその道を走行中に記録されますか? 次に、タイムスタンプがあり、したがって、順番に並んでおり、したがってすでにパスに関連しているポイントの順序があります。

したがって、最初のステップは、ポイントをパスに割り当てることです。(ベクトルとして知られているすべての森の小道をデジタル マップに描画し、ポイントを自動的に近東の小道に一致させることもできます)。

直線上の各ノードに直接到達できない場合にパスが必要です (たとえば、車で運転したり、川が直接の直線パスを避けているときに森の中を歩いたりする場合)。

次に、リンク上のノードを含むグラフを作成したら、最小スパニング ツリーを使用してパスの長さの合計をキロメートル単位で計算します。

ポイントを訪問するには、多くの場合、ブランチに戻る必要があります。そのため、巡回セールスマン アルゴリズムは、すべてのノードを訪問するのに必要なキロメーターを提供するのに役立ちます。

于 2013-10-02T16:10:59.057 に答える