Java Сортировать по расстоянию

Question

У меня есть двумерный массив, подобный этому:

{1,3,5,6,2,2}

{6,2,4,7,2,1}

{17,28,32,1,35,45}

...

У меня есть функция, которая может вычислить евклидово расстояние между любыми двумя массивами.Предполагая, что функция расстояния работает правильно, каков наилучший способ сортировки 2-мерного массива так, чтобы массивы в 2-мерном массиве менялись местами так, чтобы самые близкие друг к другу (по расстоянию) были бы близки друг к другу вдвумерный массив?

Редактировать

Это опять сводится к проблеме коммивояжера?

Answer 1

Я бы использовал TreeSet и компаратор.

public class EuclidComparator implements Comparator<int[]> {

    @Override
    public int compare(int[] o1, int[] o2) {

        return euclid_distance(o1, o2);

    }

}

Сортировать по:

    TreeSet<int[]> sort = new TreeSet<int[]>(new EuclidComparator());
    sort.addAll(Arrays.asList(arrays));

Или еще проще:

    Arrays.sort(arrays, new EuclidComparator());

Answer 2

Возможно, искомая структура данных "после сортировки" - это карта каждой точки с двумя ближайшими соседями, а не двумерный массив?Если я не пропущу какое-либо свойство вашей проблемной области, которое делает это возможным, вы не можете применить линейный порядок к точкам в вашей проблемной области.

Answer 3

Вы должны увидеть, что не существует «идеального» решения, где «совершенное» означало бы, что «Если записи A и B смежны в моем массиве, то ни одна точка не ближе к A, чем B, и ни одна точка не ближе к Bчем "А".

Это просто невозможно.

Answer 4

Размышляя над проблемой, я считаю, что вам нужно рассчитать расстояние от каждой точки до любой другой точки, чтобы узнать, какая из них ближе всего.Таким образом, вам нужно эффективно иметь сетку NxN для N точек, не так ли?

Затем, когда у вас есть расстояние от Nsubn до любого другого Nsubn, вам нужен метод ранжирования, чтобы уменьшить полученную матрицу в виде линейной алгебры,нет?

Я предполагаю, что она сводится к матрице, подобной этой:

A {1,1,1}

B {3,3,3}

C {5,5,5}

И поскольку расстояние между каждым из них должно быть квадратным корнем из 12, то у вас будетМатрица выглядит следующим образом:

         A         B         C
A        0  sqrt(12)  sqrt(48)
B sqrt(12)         0  sqrt(12)
C sqrt(48)  sqrt(12)         0

Так как это верхняя и нижняя диагонали, вы можете устранить половину сетки и решить другую половину ... На этом этапе это должна быть решаемая проблема, не так ли?

Для справки приведем другой пример:

см. Также: http://www.wolframalpha.com/input/?i=distance+between+(5,1,3)+and+(3,5,1)

A {1,3,5}

B {5,1,3}

C {3,5,1}

Тогда у вас будет матрица, подобная этой:

         A         B         C
A        0  sqrt(24)  sqrt(24)
B sqrt(24)         0  sqrt(24)
C sqrt(24)  sqrt(24)         0

и это говорит нам, что все точки равноудалены друг от друга.

Или я ушел далеко в левое поле на этом?Что я пропустил?

Answer 5

Написать быструю сортировку и использовать функцию расстояния, когда вам нужно сравнить два элемента В Википедии есть алгоритм для вас.

Answer 6

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