Соответствие трем или более ближайшим числам из массивов

У меня есть четыре массива размером 2 ^ N, где N = 25. Элементы массивов были сгенерированы моим алгоритмом. Они отсортированы, но содержат числа. Теперь мне нужно взять каждый элемент массива1 и выбрать элементы массива2, массив3, массив4 так, чтобы их сумма была минимальной (когда я говорю сумма, я могу взять a1[k] +-a2[j]+-a3[m] +-a4 [t]. Я думаю, что это похоже на проблему слияния K Dimension. Может ли кто-нибудь указать на литературу / реализацию / эвристику, чтобы сделать то же самое. С уважением, Аллахбакш


matching algorithm minimum
person Allahbaksh Asadullah    schedule 04.04.2012    source источник
comment
1. Пример будет очень полезен. 2. Вы можете использовать знак ±.   -  person Adam Matan    schedule 04.04.2012
comment
То, что вы просите на словах, тривиально - возьмите минимальные элементы из массива2, 3 и 4, независимо от элемента массива1, тогда и сумма будет минимальной. Но я подозреваю, что вы хотите знать что-то другое.   -  person Doc Brown    schedule 04.04.2012

Ответы (2)


arrow_upward
0
arrow_downward

Шаг 1. Для массива1[k] найдите число в массиве2, массив3 или массив4, модуль которого ближе к массиву1[k].

eg . 
array1 = {1, 3, 67}
array2 = {-31, 7, 47}
array3 = {-1, 2, 10}
array4 = {14, 15, 66}

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1

Шаг 2 Затем из оставшихся двух массивов найдите пару чисел, которые ближе друг к другу. (снова рассмотрим модуль)

eg . 
array2 = {-31, 7, 47}
array4 = {14, 15, 66}

Closest elements are 7 and 14 with -7 + 14 = 7.

В конце концов вы получите min(a1[k] +-a2[j]+-a3[m]+-a4[t]) из всех 4 массивов.

person Tejas Patil    schedule 04.04.2012
comment
Итак, для 1 из массива1 это дает: 1 - 1 - 7 + 14 = 7? Но можно и лучше: 1+7+10-14=4. - person Henrik; 04.04.2012
comment
Это взорвет решение в геометрической прогрессии. Я думаю, что грубый способ сделать это - поместить его в цикл for. Таким образом, 4 для цикла для четырех массивов, которые требуют огромных вычислительных мощностей по мере увеличения N. Есть ли какой-нибудь эвристический алгоритм для слияния KDM. - person Allahbaksh Asadullah; 04.04.2012
comment
На самом деле ближайшим будет 3,7,10,14 -> расстояние равно 11 - person Rrr; 22.08.2012

arrow_upward
0
arrow_downward

Я думаю, что эту проблему можно решить за O(n), объединить все массивы в объединенный набор, чтобы вторым значением был номер массива. Перебрать его и на каждой итерации сформировать ответ из 4 значений, на каждом шаге вычислить максимальное расстояние между выбранными числами -> минимизировать это значение.
Инициировать массив результатов с наименьшими числами из каждого массива.

public Integer[] findClosest(int[][] unionSet, Integer[] result) {

    for (int i = 0; i < unionSet.length; i++) {
        int value = unionSet[i][0];
        int position = unionSet[i][1];
        int currentDistance = getDistance(result);
        Integer[] temp = Arrays.copyOf(result, result.length);
        temp[position] = value;
        int newDistance = getDistance(temp);
        if (newDistance <= currentDistance) {
            result = temp;
        }
    }
    return result;
}

private int getDistance(Integer[] result) {
    int max = 0;
    int min = 0;
    for (int i = 1; i < result.length; i++) {
        if (result[i] != null) {
            if (result[i] > result[max]) {
                max = i;
            }
            if (result[min] != null && result[i] < result[min]) {
                min = i;
            }
        }
    }

    return Math.abs(result[max] - result[min]);
}
person Rrr    schedule 21.08.2012