Matrix Entfernung Genetischer Algorithmus auf Android

Question

Ich mache eine Routing-Anwendung auf Android, wenn Benutzer die Anzahl der Stunden eingeben können, um einen Ort zu reisen und meine Anwendung würde eine Ausgabe der möglichen Route Benutzer geben können.

Ich benutze genetischen Algorithmus (GA), um den Weg zum Benutzer zu geben, und ich verwende PHP, um meine GA auszuführen.

Hier kommt das Problem, um Routing effektiv zu sein, muss ich die Entfernung zwischen jeder Stadt zu überprüfen, ob die Route möglich ist und die Entfernung in minimiert. Wie wird die Entfernung zwischen den einzelnen Städten gespeichert, um die Ausführung zu beschleunigen? Ich habe versucht, die Entfernung direkt von Google Maps API zu erhalten, aber es dauert längere Ausführungszeit.

Ich dachte, um die Entfernung zu JSON-Datei zu speichern, aber ist das möglich? Oder gibt es noch andere effektive Wege?

Beachten Sie, dass das Ziel dynamisch ist. Benutzer können ein neues Ziel hinzufügen, so dass bei jedem neuen Ziel die Matrixdistanz aktualisiert werden muss.

Bitte helfen Sie mir :) Danke.

Answer 1

Sie kennen die Ausgangsposition des Benutzers und möchten verschiedene Zielentfernungen kennen. Ich schlage vor, dass Sie den deterministischen Algorithmus des kürzesten Weges der einzelnen Quelle wie Dijkstra anstelle des evolutionären Algorithmus verwenden. Die Implementierung basiert auf einer Warteschlange mit minimaler Priorität, die von einem Fibonacci-Heap implementiert wird, der in O (E.logV) ausgeführt wird, wobei E die Anzahl der Kanten und V die Anzahl der Scheitelpunkte ist. Es läuft viel schneller als der genetische Algorithmus und findet auch die beste Antwort statt einer ungefähren. Es hat auch die Eigenschaft, die zuerst die nächsten Ziele zuerst findet, die für Sie passend ist.