Найти минимальные элементы набора векторов

Question

У меня есть набор векторов, и мне нужно написать алгоритм в java, чтобы найти минимальные элементы этого набора. Проблема в том, что существуют несравнимые элементы. Например. minset {(1,4,6), (3,2,5), (2,3,4), (5,4,6)} = {(1,4,6), (3,2,5), (2,3,4)}. Для набора минимального элемента «minset» следующие трюки: каждый вектор из исходного набора либо находится в «minset», либо> =, чем какой-либо вектор в новом наборе в каждом компоненте. Например. minset {(2,3,4), (2,3,5)} = {(2,3,4)}. У меня уже есть алгоритм для этого, но я думаю, что это можно сделать с лучшей усложнением. Мой алгоритм берет один элемент, помечает его как минимальный, затем берет другой элемент, сравнивает их, если есть несравнимые, отмечаю как минимальный, если второй меньше, то отмечаем только его как минимальный и т. Д. ... Можно ли использовать mergesort или heapsort для оптимизации этого алгоритма? Спасибо за все ответы.

Answer 1

Я нашел решение моей проблемы в статье http://repository.cmu.edu/cgi/viewcontent.cgi?article=2758&context=compsci, где есть алгоритм нахождения максимальных элементов множества векторов, который является подобная проблема. Он работает намного более усложняющей сложностью, чем мой интуитивно понятный алгоритм.

Answer 2

Я создал a runnable example. Он использует встроенный Java Arrays.sort() и Comparator, который сравнивает два вектора размера L. Вы можете сделать что-то подобное, используя Collections.sort(), если вы предпочитаете использовать структуры данных по массивам List.

От Java API Specification:

This algorithm offers guaranteed n*log(n) performance. 

import java.util.*; 
import java.lang.*; 

class Main 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     final int L = 3; 

     int[][] vectors = { 
      {1, 4, 6}, 
      {3, 2, 5}, 
      {2, 3, 4}, 
      {5, 4, 6}, 
      {7, 7, 7}, 
      {3, 3, 5}, 
      {8, 8, 8}, 
     }; 

     Comparator<int[]> cmp = new Comparator<int[]>() { 
      public int compare(int[] v1, int[] v2) { 
       int cmp0 = Integer.signum(v1[0] - v2[0]); 
       for (int i = 0; i < L; i++) { 
       int cmp1 = Integer.signum(v1[i] - v2[i]); 
        if (cmp1 != 0) { 
         if (cmp1 != cmp0) { 
          return 0; 
         } 
         cmp0 = cmp1; 
        } 
       } 
       return cmp0; 
      } 
     }; 

     Arrays.sort(vectors, cmp); 

     System.out.println("minset:"); 
     int i = 0; 
     int[] vPref = vectors[0]; 
     while (cmp.compare(vectors[i], vPref) == 0) { 
      for (int x : vectors[i]){ 
       System.out.print(x + ", "); 
      } 
      System.out.println(); 
      vPref = vectors[i]; 
      i++; 
     } 
    } 
} 

Answer 3

псевдокод:

foreach inputVector in vectors 
    foreach minVector in minSet 
     if (all components of inputVector <= components of minVector 
      delete minVector 
     elseif (all components of inputVector >= components of minVector)  
      skip to next inputVector 
    if inputVector made it through the entire minSet, then add it to minSet