Алгоритм преодоления ограничения элементов, заданного API матрицы расстояний
Во-первых, я выполнил поиск в StackOverflow, поэтому я знаю, что это новое. Пожалуйста, читайте дальше:
Итак, у меня есть строковый массив из 9 мест, и мне нужно найти расстояние между ними для ввода в алгоритм. Я использовал Google Matrix API API и передаю эти места как начало, так и пункт назначения, и он возвращает ответ, который я делаю в виде квадратной матрицы n x n, например:
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 часов она не может работать. Так есть ли другой способ, которым я могу преодолеть это? Я знаю, что должен быть какой-то способ, которым я могу сделать несколько запросов и заполнить матрицу, я хотел бы знать, как, так как я не могу придумать алгоритм.
Решение
Я не уверен, как часто вы делаете это, но предупреждаю, что это может сложиться очень быстро по мере роста количества элементов. От их сайт:
«количество источников, умноженное на количество пунктов назначения, равно количеству элементов.», и элементы начинаются с $ .01 / каждый. Так что, если вы делаете 25 отправлений и 25 пунктов назначения, это будет 625 элементов за 6,25 долл. США. За 100 это будет 100 долларов. За 200 это будет 400 долларов. За 1000 это будет 10000 долларов.
Если вы все еще хотите продолжить, вот некоторый псевдокод того, как вы могли бы сделать это (предполагается, что все, включая 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;
};
Другие решения
Других решений пока нет …