Androidでの行列距離遺伝的アルゴリズム

Question

私はAndroidでルーティングアプリケーションを作っています。ユーザーが場所を移動する時間を入力でき、アプリケーションがユーザーが移動できる可能な経路の出力を与えることができます。

私は遺伝子アルゴリズム（GA）を使用してユーザーに経路を提供しています。私はGAを実行するためにPHPを使用しています。

ルーティングが有効になるためには、ルートが可能かどうかを検証するために、各都市間の距離を知る必要があります。実行をより速くするために各都市間の距離を保存する方法は？ Google Maps APIから直接 の距離を取得しようとしましたが、実行に時間がかかります。

私はjsonファイルまでの距離を保存すると考えていましたが、それは可能ですか？または別の効果的な方法がありますか？

宛先が動的であることに注意してください。ユーザーは新しい目的地を追加することができるので、新しい目的地があるときはいつでも行列の距離を更新する必要があります。

お願いします:)ありがとうございます。

Answer 1

あなたはユーザーの初期の位置を知っていて、異なる目的地の距離を知りたいと思っています。進化的アルゴリズムの代わりにDijkstraのような単一ソースの最短経路決定論的アルゴリズムを使用することをお勧めします。実装はO（E.logV）で実行されるフィボナッチヒープによって実装される最小優先順位キューに基づいて実装されます.Eはエッジの数、Vは頂点の数です。それは遺伝的アルゴリズムよりもはるかに高速に実行され、また、おおよその答えの代わりに最良の答えを見つける。それはまたあなたに適した最初の最も近い目的地を最初に見つけるプロパティを持っています。