Максимальное среднее расстояние между двумя числами по нескольким массивам

Question

Допустим, у вас есть k массивы размером N, каждый из которых содержит уникальные значения от 1 до N.

Как найти два числа, которые в среднем находятся дальше всего? друг от друга?

Например, с учетом массивов:

[1,4,2,3]
[4,2,3,1]
[2,3,4,1]

Тогда ответом будут элементы 1 и 2, потому что они на расстоянии 2 друг от друга в первом два массива и 3 числа друг от друга в последнем.

Мне известно о решении O (кН ^ 2) (путем измерения расстояния между каждой парой чисел для каждого из k массивов), но есть ли лучшее решение?

Я хочу реализовать такой алгоритм на C ++, но любое описание решения будет полезно.

Answer 1

После линейного преобразования времени, индексирующего числа, эта проблема сводится к вычислению диаметра набора точек относительно расстояния L1. К сожалению, эта проблема подвержена проклятию размерности.

Учитывая

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

, мы вычисляем

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

, а затем расстояние L1 между 1 и 2 равно |1-3| + |4-2| + |4-1| = 8, что является их средним расстоянием (в терминах задачи), умноженным на k = 3.

При этом можно применить алгоритм приближенного ближайшего соседа, используя приведенный выше ввод в качестве базы данных и изображение каждая точка в базе данных под N+1-v как запрос.

Answer 2

У меня есть предложение для лучшего случая . Вы можете использовать эвристический подход.

Например, вы знаете, что если N=4, N-1=3 будет максимальным расстоянием, а 1 будет минимальным. Среднее расстояние равно 10/6=1,66667 (суммы расстояний между парами в массиве / количество пар в массиве).

Тогда вы знаете, что если два числа находятся по краям для массивов k/2 (большинство раз), он уже находится на средней вершине (> = 2 расстояния), даже если они находятся на расстоянии 1 друг от друга в других k/2 массивах. Это может быть решением для лучшего случая в O(2k) = O(k).