Алгоритм бин-упаковки, нуждающийся в ускорении

Question

Я ищу разумный способ приблизиться к версии общей проблемы упаковки корзины. Учитывая количество пакетов (как я их называю) с определенной пропускной способностью и список предметов, занимающих определенное пространство, задача состоит в том, чтобы определить, могут ли все предметы помещаться в сумочки; и если да, то как. Сейчас у меня есть исчерпывающий DFS, но это требуется ... навсегда. Моя DFS является итеративной и требует копирования целых состояний на каждом шаге, что очень дорого. Вот мой код для конкретной проблемы с 4 мешками с 10 емкостью (действительно важными частями этого кода являются только метод pack() и класс State, если вы не хотите смотреть на все это):

import java.util.ArrayList; 
import java.util.Stack; 

public class BagProblem { 
    int numBags; 
    int bagCapacity; 
    ArrayList<Item> items = new ArrayList<Item>(); 

    public static void main(String[] args) { 
     BagProblem bp = new BagProblem(4, 10); 
     bp.pack(); 
    } 

    public BagProblem(int numBags, int bagCapacity) { 
     this.numBags = numBags; 
     this.bagCapacity = bagCapacity; 
     items = new ArrayList<Item>(); 
     items.add(new Item("item0", 6)); 
     items.add(new Item("item1", 6)); 
     items.add(new Item("item2", 6)); 
     items.add(new Item("item5", 3)); 
     items.add(new Item("item6", 3)); 
     items.add(new Item("item7", 3)); 
     items.add(new Item("item8", 2)); 
     items.add(new Item("item9", 2)); 
     items.add(new Item("item10", 2)); 
     items.add(new Item("item11", 2)); 
     items.add(new Item("item12", 2)); 
     items.add(new Item("item13", 2)); 
     items.add(new Item("item14", 1)); 
    } 

    // find a valid way to pack and print the items in each Bag, or 
    // print failure 
    public void pack() { 
     Stack <State> s = new Stack<State>(); 
     Bag[] currBags = new Bag[numBags]; 
     for (int i = 0; i < numBags; i++) { 
      currBags[i] = new Bag(bagCapacity); 
     } 
     s.push(new State(currBags)); 
     while(!s.isEmpty()) { 
      State currState = s.pop(); 
      for (Item i : items) { 
       if (!currState.containsItem(i)) { 
        State newState = new State(currState.bags); 
        newState.numItems = currState.numItems; 
        if (newState.addItem(i)) { 
         s.push(newState); 
         if (newState.numItems == items.size()) { 
          System.out.println("success"); 
          System.out.println(newState); 
          return; 
         } 
        } 
       } 
      } 
     } 
     System.out.println("failure"); 
    } 

    private class State { 
     Bag[] bags; 
     int numItems; 

     public State(Bag[] currBags) { 
      bags = new Bag[numBags]; 
      for (int i = 0; i < numBags; i++) { 
       bags[i] = new Bag(bagCapacity); 
      } 

      // figure out how to actually copy this 
      for (int j = 0; j < numBags; j++) { 
       Bag bagToCopy = currBags[j]; 
       for (Item item : bagToCopy.contents) { 
        Item newItem = new Item(item.name, item.size); 
        bags[j].size = bagToCopy.size; 
        bags[j].contents.add(newItem); 
       } 
      } 
     } 

     public boolean addItem(Item i) { 
      for (Bag b : bags) { 
       if (b.addItem(i)) { 
        numItems++; 
        return true; 
       } 
      } 
      return false; 
     } 

     public boolean containsItem(Item i) { 
      for (Bag b : bags) { 
       for (Item item : b.contents) { 
        if (item.name.equals(i.name)) 
         return true; 
       } 
      } 
      return false; 
     } 

     public String toString() { 
      String output = ""; 
      for (Bag b : bags) { 
       for (Item j : b.contents) { 
        output += j.name + " "; 
       } 
       output += "\n"; 
      } 
      return output; 
     } 

    } 

    private class Bag { 
     int capacity; 
     int size; 
     ArrayList<Item> contents; 

     public Bag(int capacity) { 
      this.capacity = capacity; 
      this.size = 0; 
      contents = new ArrayList<Item>(); 
     } 

     public boolean addItem(Item i) { 
      if(size + i.size > capacity) 
       return false; 
      contents.add(i); 
      size += i.size; 
      return true; 
     } 

     public String toString() { 
      String output = ""; 
      for (Item i : contents) { 
       output += i.name + " "; 
      } 
      return output + "\n"; 
     } 

    } 

    private class Item { 
     String name; 
     int size; 

     public Item(String name, int size) { 
      this.name = name; 
      this.size = size; 
     } 

     public String toString() { 
      return name; 
     } 

    } 
} 

примерно через один миллион лет, это выплюнуть правильный ответ (вероятно, вы не хотите, чтобы на самом деле долго ждать, если вы попытаетесь запустить это):

success 
item14 item7 item6 item5 
item13 item12 item2 
item11 item10 item1 
item9 item8 item0 

Каждая линия обозначает отдельную сумку. Как я могу ускорить это? Я знаю, что есть эвристика о попытке разместить самый большой элемент в первую очередь и т. Д., Но меня действительно интересует получение базовой DFS (или, может быть, я должен попробовать вернуться), чтобы иметь меньше накладных расходов; Я постараюсь поучаствовать позже.

Любая помощь была бы принята с благодарностью.

Answer 1

Я не использую Java, но ваша реализация кажется довольно неэффективной (как вы уже упоминали) из-за чрезмерного ее использования. Сам алгоритм также очень странный, я не пытался его реплицировать и просто использовал очевидный алгоритм грубой силы O (bags^items), который пытается поместить первый элемент в каждый мешок, поскольку каждый из этих случаев пытается поставить второй элемент в каждый мешок, и т.д. ...

Вместо репликацию всего государства неоднократно в стеке, вы можете положить товар в сумке, исследовать ветвь дерева с этим изменением, то взять деталь из сумки.

Вот пример, который немедленно завершается для вашего тестового примера на C#.

static int[] itemSize; 
    static int[] bagFreeSpace; 
    static bool[,] doesBagContainItem; // in case this looks weird, [,] is a matrix, in java it would be [][] 

    static bool pack(int item) 
    { 
     // output the solution if we're done 
     if (item == itemSize.Length) 
     { 
      for (int i = 0; i < bagFreeSpace.Length; i++) 
      { 
       Console.WriteLine("bag" + i); 
       for (int j = 0; j < itemSize.Length; j++) 
        if (doesBagContainItem[i, j]) 
         Console.Write("item" + j + "(" + itemSize[j] + ") "); 
       Console.WriteLine(); 
      } 
      return true; 
     } 

     // otherwise, keep traversing the state tree 
     for (int i = 0; i < bagFreeSpace.Length; i++) 
     { 
      if (bagFreeSpace[i] >= itemSize[item]) 
      { 
       doesBagContainItem[i,item] = true; // put item into bag 
       bagFreeSpace[i] -= itemSize[item]; 
       if (pack(item + 1))     // explore subtree 
        return true; 
       bagFreeSpace[i] += itemSize[item]; // take item out of the bag 
       doesBagContainItem[i,item] = false; 
      } 
     } 

     return false; 
    } 

    static void Main(string[] args) 
    { 
     itemSize = new int[] { 6, 6, 6, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1 }; 
     bagFreeSpace = new int[] { 10, 10, 10, 10 }; 
     doesBagContainItem = new bool[bagFreeSpace.Length, itemSize.Length]; 

     if (!pack(0)) 
      Console.WriteLine("No solution"); 
    } 

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