Более быстрый способ найти ближайшую пару точек

Question

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

В ответах ниже я изменил этот код и подробно остановился на вопросе.

// Point from java.awt.Point;
private static void findShortestDistance(Point[] pt) {

  ArrayList<Double> distance = new ArrayList<Double>(1000);    

  for(int i=0; i<pt.length; i++) {
    for(int j=i+1; j<pt.length; j++) {
      double tmp = pt[i].distance(pt[j]);
      distance.add(tmp);        
    }
  }

  double min = distance.get(0);
  for(Double d : distance) {
    if(d < min) { min = d; }
  }

}

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

Answer 1

Взгляните на википедию.http://en.wikipedia.org/wiki/Closest_pair_of_points

И этот вопрос похоже на Алгоритм наименьшего расстояния между точками

Answer 2

for(int i=0; i<pt.length; i++) {
  for(int j=i; j--; ) {
     { /* do stuff */ }
  }
}

А, для полноты:

for(int i=pt.length; i--; ) {
  for(int j=i; j--; ) {
     { /* do stuff */ }
  }
}

Answer 3

Пока вы говорите, что приведенный выше код - это именно то, что вам нужно, следующая реализация будет именно такой, которую вы хотите:

for(int i=0; i<pt.length; i++) {
  for(int j = i + 1; j<pt.length; j++) {
     /* do stuff */
  }
}

Однако у меня есть ощущение, что вы действительно заинтересованы в сравнении значений массиваили я не прав?

Answer 4

for(int i=0; i<pt.length; i++) {
  for(int j=i+1; j<pt.length; j++) {
    if(pt[i] != pt[j]) { /* do stuff */ }
  }
}

Answer 5

Инициализация j до i+1 пропустит избыточные сравнения.

for(int i = 0; i < pt.length; i++) {
  for(int j = i + 1; j < pt.length; j++) {
    if(pt[i] != pt[j]) { /* do stuff */ }
  }
}

(Кстати, изменил оператор if, предполагая, что вы хотите использовать i и j в качестве индексов в массиве.)

Это лучшее из того, что вы можете получить для самого простого случая, когда вам нужно получить перекрестное произведение массива с самим собой, за вычетом всех элементов {x, y} | x == y. (то есть исчерпывающий список неупорядоченных пар различных элементов.) Если вам нужны упорядоченные пары различных элементов, тогда ваш код лучше.