Как получить все крышки минимального набора?

Алгоритмы Set cover, как правило, предоставляют только одно решение для поиска минимального количества наборов для покрытия. Как найти все такие решения?

1 ответ

  1. Это зависит от того, что вы подразумеваете под «минимальным», поскольку это будет варьироваться количество установленных обложек, которые вы получаете. Например, если у вас целевой набор ABC и наборы AB,AC,C чтобы выбрать из вас может накрыть либо (AB,C) или (AB,AC) или все 3 (AB,AC,C) и если вы в определении «минимальный», как, например, 2 низкой выбором, т. е. с наименьшим количеством пересечений или наименьшим количеством повторяющихся элементов, то вы бы выбрали 1-й 2 ((AB,C) и (AB,AC)). «Минимальный» также может быть определен в терминах числа наборов, выбранных таким образом, для приведенного выше примера наименьшее число будет 2 и либо (AB,C) или (AB,AC) будет работать. Но если вы хотели все возможные крышки набора, то вы смогли начать с как раз грубой силой идя через каждое комбо так

    import java.util.*;
    public class f {
    
        // abcd
        static int target = 0b1111;
        // ab,ac,acd,cd
        static int[] groups = {0b1100,0b1010,0b1011,0b0011};
    
        // check if sets cover target
        // for example 1100 and 0011 would cover 1111
        static boolean covers(boolean[] A){
            int or = 0;
            for(int i=0;i<A.length;i++){
                if(A[i]) or = or | groups[i];
            }
            int t = target;
            while (t>0){
                if(t%2!=1 || or%2!=1)
                    return false;
                t = t>>1;
                or = or>>1;
            }
            return true;
        }
    
        // go through all choices
        static void combos(boolean A[],int i,int j){
            if(i>j){
                if(covers(A)) System.out.println(Arrays.toString(A));
                return;
            }
            combos(A,i+1,j);
            A[i]=!A[i];
            combos(A,i+1,j);
        }
    
        public static void main(String args[]){
            boolean[] A = new boolean[groups.length];
            combos(A,0,groups.length-1);
        }
    }