Алгоритм преодоления ограничения элементов, заданного API матрицы расстояний - PullRequest
Новая
       42

Алгоритм преодоления ограничения элементов, заданного API матрицы расстояний

0 голосов
/ 24 октября 2018

Во-первых, я выполнил поиск в StackOverflow, поэтому я знаю, что это новое.Пожалуйста, прочитайте:

Итак, у меня есть строковый массив из 9 мест, и мне нужно найти расстояние между ними для ввода в алгоритм.Я использовал Google Matrix API API и передаю эти места как места происхождения, так и места назначения, и он возвращает ответ, который я делаю в виде квадратной матрицы nxn, например: 

0  3201  4584  4821  1628  1218  1786  4738  4897
3122  0  1400  1638  1797  2756  3323  5310  5472
4523  1400  0  237 3198  4156  4723  6711  6872
4760  1638  237 0  3435  4394  4961  6948  7110
1324  1846  3247  3485  0  958 1525  3931  4093
932 2854  4273  4510  1002  0  567 4873  5034
1499  3422  4840  5078  1569  567 0  5440  5602
5061  5359  6760  6998  4019  4959  5526  0  161
5233  5531  6931  7169  4190  5130  5697  171 0

В этом, как по строкам, так и по строкамПо столбцам указаны названия мест, т.е. один и тот же массив мест в том же порядке, поэтому диагональные элементы равны нулю (хотя в действительности ответ Google не всегда равен 0 по какой-то причине), поскольку переход к месту от самого себя должен быть 0.

Теперь проблема в том, что API матрицы расстояний Google имеет ограничение в 25 элементов на запрос, где сумма количества исходных и конечных пунктов не должна превышать 25. Поэтому, поскольку я использую один и тот же источники направления, это разбивает его до 12 элементов максимум.Но приложение, которое я создаю, требует вычисления более чем в 12 местах, поэтому я подумал об обходном пути.

Одна идея - использовать такую ​​логику (это не настоящий код, я написал его просто для того, чтобыпокажите алгоритм / псевдокод): 

if(count(places) > 12) {
   distanceMatrix = []
   for(place in placesArray) {
      distanceMatrix[] = apiCall->(place, placesArray); // apiCall(origin, dest)
   }
} else {
   response = apiCall->(placesArray, placesArray); // apiCall(origin, dest)
   distancesMatrix = convertResponseToDistancesMatrix(response)
}

Таким образом, в общем случае в этом случае, если счетчик мест превышает 12 мест, он вместо этого будет использовать цикл for, где он принимает это одно место в качестве источника и всеместа как места назначения.Таким образом, я смогу переместить предел с 12 до 25, поскольку он учитывает 1 источник и 24 пункта назначения.Проблема в том, что все еще за 24, это не может работать.Так есть ли другой способ, которым я могу преодолеть это?Я знаю, что должен быть какой-то способ, которым я могу сделать несколько запросов и заполнить матрицу, я хотел бы знать, как, поскольку я не могу придумать алгоритм.

1 Ответ

0 голосов
/ 24 октября 2018

Я не уверен, как часто вы делаете это, но предупреждаю, что это может сложиться очень быстро по мере роста количества элементов.Начиная с их сайта :

"число отправителей, умноженное на количество пунктов назначения, равное количеству элементов.", А элементы начинаются с $ .01 / каждый.Так что, если вы делаете 25 отправлений и 25 пунктов назначения, это будет 625 элементов за 6,25 $.За 100 это будет 100 долларов.За 200 это будет 400 долларов.Для 1000 это будет $ 10 000.

Если вы все еще хотите продолжить, вот некоторый псевдокод, как вы могли бы сделать это (предполагается, что все, включая apiCall, является синхронным, и что результаты находятся в 2d массиве):

/**
 * @param locations Array of locations you want to consider
 */
var queryDistances = function(locations) {
    var locationDistances = [];
    var placesToConsiderAtOnce = 12;

    //Get the location groups to consider
    var locationGroups;
    for(var i = 0; i < locations.length; i++){
        var locationArraysIndex = Math.floor(i / placesToConsiderAtOnce);
        locationGroups[locationArraysIndex] = locationGroups[locationArraysIndex] || [];
        locationGroups[locationArraysIndex].push(locations[i]);
    }

    //Process all combinations of the location groups
    for(var i = 0; i < locationGroups.length; i++){
        for(var j = 0; j < locationGroups.length; j++){
            var originArray = locationGroups[i];
            var destinationArray = locationGroups[j];
            var results = apiCall(originArray, destinationArray);

            for(var k = 0; k < originArray.length; k++){
                for(var l = 0; l < destinationArray.length; l++){
                    var locationDistancesFirstIndex = k + i * placesToConsiderAtOnce;
                    var locationDistancesSecondIndex = l + j * placesToConsiderAtOnce;

                    locationDistances[locationDistancesFirstIndex] = locationDistances[locationDistancesFirstIndex] || [];
                    locationDistances[locationDistancesSecondIndex] = results[k][l];
                }
            }
        }
    }

    return locationDistances;
};
...