Dynamische Programmierung für string schneiden

Den divide and conquer Ansatz scheint mir der beste für diese Art von problem. Hier ist eine Java-Implementierung des Algorithmus:

Hinweis: array m sollten in aufsteigender Reihenfolge sortiert werden (verwenden Sie Arrays.sort(m);)

public int findMinCutCost(int[] m, int n) {
   int cost = n * m.length;
   for (int i=0; i<m.length; i++) {
      cost = Math.min(findMinCutCostImpl(m, n, i), cost);
   }
   return cost;
}

private int findMinCutCostImpl(int[] m, int n, int i) {
   if (m.length == 1) return n;
   int cl = 0, cr = 0;
   if (i > 0) {
      cl = Integer.MAX_VALUE;
      int[] ml = Arrays.copyOfRange(m, 0, i);
      int nl = m[i];
      for (int j=0; j<ml.length; j++) {
         cl = Math.min(findMinCutCostImpl(ml, nl, j), cl);
      }
   }
   if (i < m.length - 1) {
      cr = Integer.MAX_VALUE;
      int[] mr = Arrays.copyOfRange(m, i + 1, m.length);
      int nr = n - m[i];
      for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[i];
      }
      for (int j=0; j<mr.length; j++) {
         cr = Math.min(findMinCutCostImpl(mr, nr, j), cr);
      }
   }
   return n + cl + cr;
}

Beispiel :

 int n = 20;
 int[] m = new int[] { 10, 3 };

 System.out.println(findMinCutCost(m, n));

Drucken 30

** Bearbeiten **

Implementierte ich zwei andere Methoden zu beantworten, das problem in die Frage.

1. Median-cut-approximation

Diese Methode cut rekursiv immer der größte Brocken. Die Ergebnisse sind nicht immer die beste Lösung, bietet aber einen nicht zu vernachlässigenden Gewinn (in der Größenordnung von +100000% Gewinn aus meinen tests) für eine vernachlässigbar minimale Schnitt-Verlust Differenz aus den besten Kosten.

public int findMinCutCost2(int[] m, int n) {
   if (m.length == 0) return 0;
   if (m.length == 1) return n;
      float half = n/2f;
      int bestIndex = 0;
      for (int i=1; i<m.length; i++) {
         if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
            bestIndex = i;
         }
      }
      int cl = 0, cr = 0;
      if (bestIndex > 0) {
         int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
         int nl = m[bestIndex];
         cl = findMinCutCost2(ml, nl);
      }
      if (bestIndex < m.length - 1) {
         int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
         int nr = n - m[bestIndex];
         for (int j=0; j<mr.length; j++) {
         mr[j] = mr[j] - m[bestIndex];
      }
      cr = findMinCutCost2(mr, nr);
   }
   return n + cl + cr;
}

2. Eine Konstante Zeit multi-cut

Statt Berechnung die minimalen Kosten, nur verwenden verschiedene Indizes und Puffer. Da diese Methode führt in konstanter Zeit, es gibt immer n. Plus, die Methode eigentlich split die Zeichenfolge in Teilzeichenfolgen.

public int findMinCutCost3(int[] m, int n) {
   char[][] charArr = new char[m.length+1][];
   charArr[0] = new char[m[0]];
   for (int i=0, j=0, k=0; j<n; j++) {
      //charArr[i][k++] = string[j];   //string is the actual string to split
      if (i < m.length && j == m[i]) {
         if (++i >= m.length) {
            charArr[i] = new char[n - m[i-1]];
         } else {
            charArr[i] = new char[m[i] - m[i-1]];
         }
         k=0;
      }
   }
   return n;
}

Hinweis: dass diese Letzte Methode könnte leicht geändert werden, um zu akzeptieren String str argument statt n - und set -n = str.length(), und geben Sie einen String[] array von charArr[][].

python-code:

mincost(n, cut_list) =min {   n+ mincost(k,left_cut_list) + min(n-k, right_cut_list) }


import sys

def splitstr(n,cut_list):

        if len(cut_list) == 0: 
            return [0,[]]
        min_positions = []
        min_cost = sys.maxint
        for k in cut_list:
            left_split = [ x for x in cut_list if x < k]
            right_split = [ x-k for x in cut_list if x > k] 
            #print n,k, left_split, right_split
            lcost = splitstr(k,left_split)
            rcost = splitstr(n-k,right_split)      
            cost = n+lcost[0] + rcost[0]
            positions = [k] + lcost[1]+ [x+k for x in rcost[1]] 
            #print "cost:", cost, " min: ", positions
            if cost < min_cost:
                min_cost = cost
                min_positions = positions

        return ( min_cost, min_positions) 



print splitstr(20,[3,10,16])  # (40, [10, 3, 16])

print splitstr(20,[3,10]) # (30, [10, 3])

print splitstr(5,[1,2,3,4,5]) # (13, [2, 1, 3, 4, 5])

print splitstr(1,[1]) # (1, [1]) # m cuts m+1 substrings