Вычисление двумерной матрицы расстояний из ответа Google DistanceMatrix в Java - PullRequest
Новая
       38

Вычисление двумерной матрицы расстояний из ответа Google DistanceMatrix в Java

0 голосов
/ 26 мая 2019

Я пытаюсь решить проблему коммивояжера и проблемы с маршрутизацией автомобиля с помощью библиотеки инструментов Google или, в учебном пособии, найденном здесь , они используют матрицу расстояний whose i, j запись - это расстояние от местоположения i до местоположения j в милях, где местоположения указаны в следующем порядке:

  1. Нью-Йорк 1. Лос-Анджелес 2. Чикаго 3. Миннеаполис 4. Денвер 5. Даллас 6. Сиэтл 7. Бостон 8. Сан-Франциско 9. Сент-Луис 10. Хьюстон 11. Феникс 12. Солт-Лейк-Сити

И их матричное расстояние выглядит так: 

  public final long[][] distanceMatrix = {
      {0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972},
      {2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579},
      {713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260},
      {1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987},
      {1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371},
      {1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999},
      {2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701},
      {213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099},
      {2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600},
      {875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162},
      {1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200},
      {2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504},
      {1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0},
  };

Они также предоставляют учебник о том, как динамически создавать матрицу расстояний, за исключением того, что в Python, и я не очень хорош в этом, я использую Java.

В моем Java implementation Я использую Java Client, и мой код выглядит как 

private static long[][] buildDistanceMatrix(int matrixSize, DistanceMatrix distanceMatrix) {
        long[][] matrix = new long[matrixSize][matrixSize];
        for (int i = 0; i < distanceMatrix.rows.length; i++) {
            DistanceMatrixElement[] elements = distanceMatrix.rows[i].elements;
            for (int j = 0; j < elements.length; j++) {
                    matrix[i][j] = elements[j].distance.inMeters;
            }
        }
        return matrix;
    }


    public static void getDistanceMatrix(List<LatLng> origins, List<LatLng> destinations){
        GeoApiContext context = new GeoApiContext.Builder()
                .apiKey(GOOGLE_MAPS_API_KEY)
                .build();
        DistanceMatrixApiRequest distanceMatrixApiRequest = DistanceMatrixApi.newRequest(context)
                .mode(TravelMode.DRIVING)
                .trafficModel(TrafficModel.BEST_GUESS)
                .departureTime(Instant.now().atZone(ZoneOffset.UTC).toInstant())
                .destinations(destinations.toArray(new LatLng[destinations.size()]))
                .origins(origins.toArray(new LatLng[origins.size()]));


        distanceMatrixApiRequest.setCallback(new PendingResult.Callback<DistanceMatrix>() {
            @Override
            public void onResult(DistanceMatrix distanceMatrix) {

                long[][] matrix = buildDistanceMatrix(destinations.size(), distanceMatrix);
                System.out.println(Arrays.deepToString(matrix));

            }

            @Override
            public void onFailure(Throwable throwable) {
                throwable.printStackTrace();

            }
        });
    }

И результат выглядит как

[[10196, 6647, 4881], [0, 0, 0], [0, 0, 0]]

Я не понимаю, как была сделана матрица в python code, может кто-нибудь помочь мне ее сформулировать?

Мой ответ DistanceMatrix выглядит как 

"destinationAddresses": [
    "Central St, Lusaka, Zambia",
    "Unnamed Road, Lusaka, Zambia",
    "Jacaranda Rd, Lusaka, Zambia"
],
"originAddresses": [
    "1940 - 3 Munthaka Cl, Lusaka, Zambia"
],
"rows": [
    {
        "elements": [
            {
                "distance": {
                    "humanReadable": "10.2 km",
                    "inMeters": 10193
                },
                "duration": {
                    "humanReadable": "23 mins",
                    "inSeconds": 1352
                },
                "durationInTraffic": {
                    "humanReadable": "26 mins",
                    "inSeconds": 1549
                },
                "status": "OK"
            },
            {
                "distance": {
                    "humanReadable": "6.6 km",
                    "inMeters": 6647
                },
                "duration": {
                    "humanReadable": "13 mins",
                    "inSeconds": 779
                },
                "durationInTraffic": {
                    "humanReadable": "14 mins",
                    "inSeconds": 839
                },
                "status": "OK"
            },
            {
                "distance": {
                    "humanReadable": "4.9 km",
                    "inMeters": 4881
                },
                "duration": {
                    "humanReadable": "9 mins",
                    "inSeconds": 516
                },
                "durationInTraffic": {
                    "humanReadable": "9 mins",
                    "inSeconds": 538
                },
                "status": "OK"
            }
        ]
    }
]

}```
...