trouver un nombre minimal de la colonne

Question

Voici un exemple: Supposons que j'ai un 2D-tableau qui ne comprennent 0 et 1:

0,1,0,0 
0,0,0,1 
1,0,1,0 

Je dois trouver un nombre minimal de la colonne qui peut être ajouter à ceux vecteur. Par exemple, column0 + colonne1 + colonne3 = 0,0,1 + 1,0,0 + 0,1,0 = 1,1,1 Ainsi, le nombre minimal de la colonne est 3.

Answer 1

Ceci est essentiellement un Set cover problem, qui est NP-dur. Il peut être formulé et résolu (de manière optimale) en tant que problème de programmation linéaire en nombre entier.

Vous pouvez également traduire le problème en un autre problème de la même classe qui a de très bons solveurs, par ex. à booléen SAT. Enfin, vous pouvez le résoudre de manière sous-optimale en utilisant des algorithmes de recherche gourmands et/ou locaux, par ex. Recuit simulé.

Answer 2

code de combinaison Shamelessly copié à partir de: https://stackoverflow.com/a/34588366/1203882

import java.util.ArrayList; 
import java.util.List; 

public class Combin { 

    public static void main(String... banana) { 
     int[][] input = new int[][] { { 0, 1, 0, 0 }, { 0, 0, 0, 1 }, { 1, 0, 1, 0 } }; 
     List<int[]> columns = new ArrayList<int[]>(); 
     int min = Integer.MAX_VALUE; 

     //Set columns list 
     for (int column = 0; column < input[0].length; column++) { 
      int[] e = new int[input.length]; 
      int index = 0; 
      for (int row = 0; row < input.length; row++) { 
       e[index++] = input[row][column]; 
      } 
      columns.add(e); 
     } 

     //Sizes 0 1 2 3 and 4 
     for (int i = 0; i <= columns.size(); i++) 
     { 
      List<List<int []>> theList = getCombinations(i, columns); 
      for (List <int[]> a : theList) 
      { 
       if (check(a)) 
       { 
        if (a.size() < min) 
         min = a.size(); 

        //For the test returns 3, 3, and 4 as possibilities. 
        System.out.println("Found a possibility: " + a.size()); 
       } 
      } 
     } 
     System.out.println("Min value: " + min); 
    } 

    public static <T> List<List<T>> getCombinations(int k, List<T> list) { 
     List<List<T>> combinations = new ArrayList<List<T>>(); 
     if (k == 0) { 
      combinations.add(new ArrayList<T>()); 
      return combinations; 
     } 
     for (int i = 0; i < list.size(); i++) { 
      T element = list.get(i); 
      List<T> rest = getSublist(list, i+1); 
      for (List<T> previous : getCombinations(k-1, rest)) { 
       previous.add(element); 
       combinations.add(previous); 
      } 
     } 
     return combinations; 
    } 

    public static <T> List<T> getSublist(List<T> list, int i) { 
     List<T> sublist = new ArrayList<T>(); 
     for (int j = i; j < list.size(); j++) { 
      sublist.add(list.get(j)); 
     } 
     return sublist; 
    } 

    //Create a vector by "or"ing every value. 
    public static boolean check(List<int []> result) 
    { 
     if (result.size() == 0) 
      return false; 
     int [] a = new int [result.get(0).length]; 
     for(int [] j : result) 
      for (int index = 0; index < a.length; index++) 
       a[index] |= j[index]; 
     return equalsVec(a); 
    } 

    //If all values aren't 1, return false. (ones vector) 
    public static boolean equalsVec(int [] a) 
    { 
     for (int i = 0; i < a.length; i++) 
      if (a[i] != 1) 
       return false; 
     return true; 
    } 
} 

sortie:

Found a possibility: 3 
Found a possibility: 3 
Found a possibility: 4 
Min value: 3