Алгоритм вложенных коробок - основанный на вложенных куклах, но принципиально другой?

Question

Я попытался решить проблему, связанную с проблемой SPOJ Nested Dolls, где вместо кукол используются коробки с двумерным дном, которые отличаются одним параметром масштаба. У меня есть алгоритм, но я очень мутный относительно фактической теории проблемы и существуют ли лучшие подходы. Может ли кто-нибудь помочь мне лучше понять проблему и, возможно, найти лучший алгоритм?

Как освежителя, проблема матрешек следующим образом:

Учитывая N матрешки различного размера, найти наименьшее количество матрешек, которые остаются после того, как оптимально вложенности куклы внутри друг друга. Для каждой вложенной куклы, если внешняя кукла имеет размер S, то она либо не содержит кукол, либо содержит одну матрешку, размер которой строго меньше S.

Я не знаю полной специфики этой проблемы, но, читая ее, я считаю, что проблема с Nested Dolls может быть решена путем сортировки кукол путем увеличения размера и многократного извлечения самой длинной растущей подпоследовательности (LIS) из где привязки разрушаются, выбирая подпоследовательность, в которой используются самые большие куклы. Количество вложенных кукол будет количеством извлеченных подпоследовательностей. Я думаю, что этот жадный алгоритм работает, потому что:

а) сокращение длиной одного из этой подпоследовательности вводит новые куклы, которые не могут уменьшить количество матрешек, найденных в будущих шагах («меньше, тем лучше»)

б) Замена куклы в подпоследовательности обязательно заменяет меньшую куклу в наборе оставшихся кукол большой куклой, которая не может уменьшить количество вложенных кукол, найденных в будущих шагах («меньше, лучше»)

Это означает, что проблема может решается в O (N log N) с хорошим алгоритмом LIS.

Но проблема с коробками различна: Учитывая, что N открытых коробок с различными размерами нижних размеров, найдите наименьшее количество коробок, которые остаются после оптимального размещения коробок внутри друг друга. На каждой блок-стеке, если внешняя коробка имеет размерность Вт х Н, то она либо не содержит коробок, или содержит один бокс-стек, ширину и высоту строго меньше Вт и Н соответственно.

Это означает, что нет полного заказа коробок - если коробка A не подходит в коробке B, это не означает, что коробка B имеет тот же размер, что и A, или что она поместится в коробке A, в отличие от Matryoshka куклы.

Я понятия не имею, прав ли я, но я думаю, что уже не так, что оптимальное решение может быть найдено путем многократного извлечения LIS (а точнее, самой длинной последовательности ящиков, соответствующих друг другу), главным образом потому, что есть нет хорошего способа разорвать связи. Коробка с большей площадью может по-прежнему оказаться более полезной для будущих шагов, если, скажем, мы сравниваем поле 1x17 с коробкой 5x4. Попытка всех связанных LIS звуков, как экспоненциальное время исполнения. Правильно ли я, или действительно ли есть жадный способ сделать это?

Я нашел только одно сообщение об этом (Stacking boxes into fewest number of stacks efficiently?), в котором предлагается использовать подход теории графов для решения проблемы. У меня очень мало опыта в теории графов, поэтому я понятия не имею, как работает этот подход.Я в основном слепо взял свое слово, чтобы сделать двудольный граф ящиков, утверждая, что количество стеков ящиков = (количество ящиков - размер максимального соответствия). Затем я реализовал алгоритм Fork Fulkerson в Java на основе псевдокода без полного понимания того, как он фактически решает проблему. Я изо всех сил старался комментировать код с помощью моего мыслительного процесса, но меня раздражает, как этот подход настолько отличается от решения Nested Dolls, и что он принимает более 150 строк, когда мне было предложено сделать это за 1 час. Верно ли, что нет более простого способа решить проблему?

Код:

import java.util.*; 

public class NestedBoxes { 
    private static final int SOURCE_INDEX = -1; 
    private static final int SINK_INDEX = -2; 

    private NestedBoxes() { 
     // Unused 
    } 

    public static void main(String args[]) throws Exception { 
     // Get box dimensions from user input 
     Scanner sc = new Scanner(System.in); 
     int numBoxes = sc.nextInt(); 
     List<Rectangle> boxes = new ArrayList<>(); 
     for (int i = 0; i < numBoxes; i++) { 
      Rectangle box = new Rectangle(sc.nextInt(), sc.nextInt()); 
      boxes.add(box); 
     } 

     // Sort boxes by bottom area as a useful heuristic 
     Collections.sort(boxes, (b1, b2) -> Integer.compare(b1.width * b1.height, b2.width * b2.height)); 

     // Make a bipartite graph based on which boxes fit into each other, and 
     // add a source linking to all boxes and a sink linked by all boxes. 
     // Forward edges go from the left (lower index) nodes to the right (higher index) nodes. 
     // Each forward edge has a corresponding backward edge in the bipartite section. 
     // Only one of the two edges are active at any point in time. 
     Map<Integer, Map<Integer, BooleanVal>> graphEdges = new HashMap<>(); 
     Map<Integer, BooleanVal> sourceMap = new HashMap<>(); 
     graphEdges.put(SOURCE_INDEX, sourceMap); 
     graphEdges.put(SINK_INDEX, new HashMap<>()); // Empty adjacency list for the sink 
     for (int i = 0; i < numBoxes; i++) { 
      // TreeMaps make the later DFS step prefer reaching the sink over other nodes, and prefer 
      // putting boxes into the smallest fitting box first, speeding up the search a bit since 
      // log(N) is not that bad compared to a large constant factor. 
      graphEdges.put(i, new TreeMap<>()); 
      // Each node representing a box is duplicated in a bipartite graph, where node[i] 
      // matches with node[numBoxes + i] and represent the same box 
      graphEdges.put(numBoxes + i, new TreeMap<>()); 
     } 
     for (int i = 0; i < boxes.size(); i++) { 
      // Boolean pointers are used so that backward edges ("flow") and 
      // forward edges ("capacity") are updated in tandem, maintaining that 
      // only one is active at any time. 
      sourceMap.put(i, new BooleanPtr(true)); // Source -> Node 
      graphEdges.get(numBoxes + i).put(SINK_INDEX, new BooleanPtr(true)); // Node -> Sink 
      for (int j = i + 1; j < boxes.size(); j++) { 
       if (fitsIn(boxes.get(i), boxes.get(j))) { 
        BooleanVal opening = new BooleanPtr(true); 
        graphEdges.get(i).put(numBoxes + j, opening); // Small box -> Big box 
        graphEdges.get(numBoxes + j).put(i, new Negation(opening)); // Small box <- Big box 
       } 
      } 
     } 
     Deque<Integer> path; // Paths are represented as stacks where the top is the first node in the path 
     Set<Integer> visited = new HashSet<>(); // Giving the GC a break 
     // Each DFS pass takes out the capacity of one edge from the source 
     // and adds a single edge to the bipartite matching generated. 
     // The algorithm automatically backtracks if a suboptimal maximal matching is found because 
     // the path would take away edges and add new ones in if necessary. 
     // This happens when the path zigzags using N backward edges and (N + 1) forward edges - 
     // removing a backward edge corresponds to removing a connection from the matching, and using extra 
     // forward edges will add new connections to the matching. 
     // So if no more DFS passes are possible, then no amount of readjustment will increase the size 
     // of the matching, so the number of passes equals the size of the maximum matching of the bipartite graph. 
     int numPasses = 0; 
     while ((path = depthFirstSearch(graphEdges, SOURCE_INDEX, SINK_INDEX, visited)) != null) { 
      visited.clear(); 
      Integer current = SOURCE_INDEX; 
      path.pop(); 
      for (Integer node : path) { 
       // Take out the edges visited. 
       // Taking away any backward edges automatically adds back the corresponding forward edge, 
       // and similarly removing a forward edge adds back the backward edge. 
       graphEdges.get(current).get(node).setBoolValue(false); 
       current = node; 
      } 
      numPasses++; 
     } 

     // Print out the stacks made from the boxes. Here, deleted forward edges/available backward edges 
     // represent opportunities to nest boxes that have actually been used in the solution. 
     System.out.println("Box stacks:"); 
     visited.clear(); 
     for (int i = 0; i < numBoxes; i++) { 
      Integer current = i; 
      if (visited.contains(current)) { 
       continue; 
      } 
      visited.add(current); 
      boolean halt = false; 
      while (!halt) { 
       halt = true; 
       System.out.print(boxes.get(current)); 
       for (Map.Entry<Integer, BooleanVal> entry : graphEdges.get(current).entrySet()) { 
        int neighbor = entry.getKey() - numBoxes; 
        if (!visited.contains(neighbor) && !entry.getValue().getBoolValue()) { 
         System.out.print("->"); 
         visited.add(neighbor); 
         current = neighbor; 
         halt = false; 
         break; 
        } 
       } 
      } 
      System.out.println(); 
     } 
     System.out.println(); 

     // Let a box-stack be a set of any positive number boxes nested into one another, including 1. 
     // Beginning with each box-stack being a single box, we can nest them to reduce the box-stack count. 
     // Each DFS pass, or edge in the maximal matching, represents a single nesting opportunity that has 
     // been used. Each used opportunity removes one from the number of box-stacks. so the total number 
     // of box-stacks will be the number of boxes minus the number of passes. 
     System.out.println("Number of box-stacks: " + (numBoxes - numPasses)); 
    } 

    private static Deque<Integer> depthFirstSearch(Map<Integer, Map<Integer, BooleanVal>> graphEdges, 
              int source, int sink, Set<Integer> visited) { 
     if (source == sink) { 
      // Base case where the path visits only one node 
      Deque<Integer> result = new ArrayDeque<>(); 
      result.push(sink); 
      return result; 
     } 

     // Get all the neighbors of the source node 
     Map<Integer, BooleanVal> neighbors = graphEdges.get(source); 
     for (Map.Entry<Integer, BooleanVal> entry : neighbors.entrySet()) { 
      Integer neighbor = entry.getKey(); 
      if (!visited.contains(neighbor) && entry.getValue().getBoolValue()) { 
       // The neighbor hasn't been visited before, and the edge is active so the 
       // DFS attempts to include this edge into the path. 
       visited.add(neighbor); 
       // Trying to find a path from the neighbor to the sink 
       Deque<Integer> path = depthFirstSearch(graphEdges, neighbor, sink, visited); 
       if (path != null) { 
        // Adds the source onto the path found 
        path.push(source); 
        return path; 
       } else { 
        // Pretend we never visited the neighbor and move on 
        visited.remove(neighbor); 
       } 
      } 
     } 
     // No paths were found 
     return null; 
    } 

    // Interface for a mutable boolean value 
    private interface BooleanVal { 
     boolean getBoolValue(); 
     void setBoolValue(boolean val); 
    } 

    // A boolean pointer 
    private static class BooleanPtr implements BooleanVal { 
     private boolean value; 

     public BooleanPtr(boolean value) { 
      this.value = value; 
     } 

     @Override 
     public boolean getBoolValue() { 
      return value; 
     } 

     @Override 
     public void setBoolValue(boolean value) { 
      this.value = value; 
     } 

     @Override 
     public String toString() { 
      return "" + value; 
     } 
    } 

    // The negation of a boolean value 
    private static class Negation implements BooleanVal { 
     private BooleanVal ptr; 

     public Negation(BooleanVal ptr) { 
      this.ptr = ptr; 
     } 

     @Override 
     public boolean getBoolValue() { 
      return !ptr.getBoolValue(); 
     } 

     @Override 
     public void setBoolValue(boolean val) { 
      ptr.setBoolValue(!val); 
     } 

     @Override 
     public String toString() { 
      return "" + getBoolValue(); 
     } 
    } 

    // Method to find if a rectangle strictly fits inside another 
    private static boolean fitsIn(Rectangle rec1, Rectangle rec2) { 
     return rec1.height < rec2.height && rec1.width < rec2.width; 
    } 

    // A helper class representing a rectangle, or the bottom of a box 
    private static class Rectangle { 
     public int width, height; 

     public Rectangle(int width, int height) { 
      this.width = width; 
      this.height = height; 
     } 

     @Override 
     public String toString() { 
      return String.format("(%d, %d)", width, height); 
     } 
    } 
} 

Answer 1

Да, есть более простой (и более эффективное) решение.

Давайте сортировать коробки по их ширине (и в обратном порядке их высоты, если ширина двух ящиков одинаковая). Понятно, что мы можем вложить ящик только в коробку, которая идет за ней. Таким образом, мы хотим разбить его на несколько увеличивающихся подпоследовательностей (учитывая теперь только высоты). Существует теорема, в которой говорится, что минимальное число возрастающих подпоследовательностей, которые можно разбить на последовательность, равно длине самого длинного, не увеличивающегося (т. Е. Не строго убывающей подпоследовательности).

Подводя итог, решение выглядит следующим образом:

1. Сортировать коробки по ширине. Если ширина одинаковая, сравните их по высоте в обратном порядке.

2. Отбросьте ширину и просто вычислите длину самой длинной невозрастающей подпоследовательности высот (в порядке, который мы получили после сортировки). Это ответ на проблему. Вот и все.

Понятно, что это решение может работать в O(N log N) времени, если выполнено правильно.