algorithm - 找到向量集的最小元素

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)}。我已经有了这个算法，但我认为它可以用更好的计算复杂度来完成。我的算法采用一个元素，将其标记为最小，然后采用另一个元素，比较它们，如果有不可比较的，则将两者都标记为最小，如果第二个较小，则仅将其标记为最小等... 是否可以使用合并排序或堆排序来优化此算法？感谢所有回复。

Answer 1

我创建了一个可运行的示例。它使用 Java 的内置函数Arrays.sort()和Comparator比较两个 size 向量的a L。Collections.sort()如果您更喜欢使用List数据结构而不是数组，则可以使用类似的方法。

来自Java API 规范：

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 2

我在文章http://repository.cmu.edu/cgi/viewcontent.cgi?article=2758&context=compsci中找到了我的问题的解决方案，其中是用于查找类似问题的向量集的最大元素的算法。它的计算复杂度比我的第一个直观算法要好得多。

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