Programmazione parallela con funzioni ricorsive?

Question

Background del problema: sto provando a scrivere un algoritmo di soluzione di puzzle che sfrutta processori multi-core e elaborazione parallela. Tuttavia, la soluzione ideale/più semplice è una semplice funzione ricorsiva.

Qual è il modo migliore per abbattere la soluzione per entrambi usufruire di elaborazione parallela E la funzione ricorsiva?

Il codice seguente è una soluzione per un semplice algoritmo di risoluzione di problemi (funziona correttamente). Il puzzle in questo esempio è semplice: ci sono 14 slot numerati 1-14. Ogni pezzo del puzzle ha un ID univoco, un intervallo che ti dice dove può iniziare e fermarsi (per esempio 6-8 significa che solo inserisce negli slot 6-8) e un prezzo. L'algoritmo tenta di trovare la soluzione che massimizzi il prezzo della soluzione. Solo 1 pezzo può occupare uno slot e gli slot vuoti sono accettabili. La soluzione ti direbbe quali pezzi sono usati e il costo totale. (Per semplificare le cose, si supponga anche che lo slot 1 DEVE essere riempito).

La mia tentata soluzione di combinare il parallelismo e la ricorsione è ciò che viene utilizzato di seguito: creare un'attività per ogni pezzo che utilizza lo slot 1, quindi all'interno del task guardare in modo ricorsivo attraverso il resto dei pezzi, inserendoli negli spazi rimanenti e massimizzandoli il costo. È la soluzione migliore (probabilmente no, ecco perché sono qui). Come può essere migliorato? Qualche altro buon consiglio quando si usano soluzioni parallele/ricorsive?

Mentre la semplice ricorsione funzionerebbe bene qui, sto immaginando questo in esecuzione con un Puzzle che ha 200 slot e 5000 pezzi.

Ecco la soluzione a questo esempio così:

ID=1 Price=10.0 Range=1-6 
ID=12 Price=8.0 Range=9-14 
ID=15 Price=3.0 Range=7-8 


public class Puzzle 
{ 

    public PuzzleSet calculateResults(PuzzleSet input) throws Exception 
    { 
     System.out.println(System.currentTimeMillis()); 
     PuzzleSet results = getPriceMultithread((PuzzleSet)SerializationUtils.clone(input)); 
     System.out.println(System.currentTimeMillis()); 
     return results; 
    } 

    private PuzzleSet getPriceMultithread(PuzzleSet input) throws Exception 
    { 
     PuzzleSet initial = input.startsAtPoint(1); 

     ExecutorService exec = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors()+1); 
     Collection<Callable<PuzzleSet>> tasks = new ArrayList<Callable<PuzzleSet>>(); 

     for (int i=0; i<initial.size(); i++) 
     { 
      final PuzzleData d = initial.get(i); 
      final PuzzleSet start = input.higherThan(initial.get(i).rangeUpper); 
      tasks.add(new Callable<PuzzleSet>() { 
       public PuzzleSet call() { 
        PuzzleSet s = new PuzzleSet(); 
        s.add(d); 
        s.addAll(getPrice(start)); 
        return s; 
       } 
      }); 
     } 

     List<Future<PuzzleSet>> results = exec.invokeAll(tasks); 
     PuzzleSet max = new PuzzleSet(); 
     double maxD = 0.0; 
     for (int i=0; i<results.size(); i++) 
     { 
      PuzzleSet temp = results.get(i).get(); 
      double sum = temp.sum(); 
      if (sum > maxD) 
      { 
       maxD = sum; 
       max = temp; 
      } 
     } 
     return max; 
    } 

    private PuzzleSet getPrice(PuzzleSet input) 
    { 
     if (input == null || input.size() == 0) return new PuzzleSet(); 

     double maxD = 0.0; 
     PuzzleSet max = new PuzzleSet(); 
     for (int i=0; i<input.size(); i++) 
     { 
      PuzzleSet vs = input.higherThan(input.get(i).rangeUpper); 
      PuzzleSet s = getPrice(vs); 
      double d = s.sum(); 
      double pTemp = input.get(i).price + d; 
      if (pTemp > maxD) 
      { 
       maxD = pTemp; 
       s.add(input.get(i)); 
       max = s; 
      } 
     }  
     return max; 
    } 

    public static void main(String arg[]) throws Exception 
    { 
     PuzzleSet s = new PuzzleSet(); 

     PuzzleData v1 = new PuzzleData(); 
     v1.rangeLower = 1; 
     v1.rangeUpper = 6; 
     v1.price = 10; 
     v1.ID = 1; 
     s.add(v1);  

     PuzzleData v2 = new PuzzleData(); 
     v2.rangeLower = 7; 
     v2.rangeUpper = 11; 
     v2.price = 0; 
     v2.ID = 2; 
     s.add(v2); 

     PuzzleData v3 = new PuzzleData(); 
     v3.rangeLower = 12; 
     v3.rangeUpper = 14; 
     v3.price = 7; 
     v3.ID = 3; 
     s.add(v3);  

     PuzzleData v5 = new PuzzleData(); 
     v5.rangeLower = 7; 
     v5.rangeUpper = 9; 
     v5.price = 0; 
     v5.ID = 4; 
     s.add(v5); 

     PuzzleData v6 = new PuzzleData(); 
     v6.rangeLower = 10; 
     v6.rangeUpper = 14; 
     v6.price = 5; 
     v6.ID = 5; 
     s.add(v6); 

     PuzzleData v7 = new PuzzleData(); 
     v7.rangeLower = 1; 
     v7.rangeUpper = 3; 
     v7.price = 5; 
     v7.ID = 6; 
     s.add(v7); 

     PuzzleData v8 = new PuzzleData(); 
     v8.rangeLower = 4; 
     v8.rangeUpper = 9; 
     v8.price = 0; 
     v8.ID = 7; 
     s.add(v8); 

     PuzzleData v10 = new PuzzleData(); 
     v10.rangeLower = 1; 
     v10.rangeUpper = 5; 
     v10.price = 3; 
     v10.ID = 8; 
     s.add(v10); 

     PuzzleData v11 = new PuzzleData(); 
     v11.rangeLower = 6; 
     v11.rangeUpper = 11; 
     v11.price = 2; 
     v11.ID = 9; 
     s.add(v11); 

     PuzzleData v12 = new PuzzleData(); 
     v12.rangeLower = 12; 
     v12.rangeUpper = 14; 
     v12.price = 7; 
     v12.ID = 10; 
     s.add(v12); 

     PuzzleData v14 = new PuzzleData(); 
     v14.rangeLower = 4; 
     v14.rangeUpper = 8; 
     v14.price = 1; 
     v14.ID = 11; 
     s.add(v14); 

     PuzzleData v15 = new PuzzleData(); 
     v15.rangeLower = 9; 
     v15.rangeUpper = 14; 
     v15.price = 8; 
     v15.ID = 12; 
     s.add(v15); 

     PuzzleData v16 = new PuzzleData(); 
     v16.rangeLower = 1; 
     v16.rangeUpper = 5; 
     v16.price = 3; 
     v16.ID = 13; 
     s.add(v16); 

     PuzzleData v17 = new PuzzleData(); 
     v17.rangeLower = 6; 
     v17.rangeUpper = 8; 
     v17.price = 1; 
     v17.ID = 14; 
     s.add(v17); 

     PuzzleData v18 = new PuzzleData(); 
     v18.rangeLower = 7; 
     v18.rangeUpper = 8; 
     v18.price = 3; 
     v18.ID = 15; 
     s.add(v18); 

     PuzzleSet x = new Puzzle().calculateResults(s); 
     for (int i=0; i<x.size(); i++) 
     { 
      System.out.println(x.get(i)); 
     } 

    } 
} 

public class PuzzleData implements Serializable 
{ 
    public int rangeLower; 
    public int rangeUpper; 
    public int ID; 
    public double price; 

    public String toString() 
    { 
     return "ID=" + ID + " Price=" + price + " Range=" + rangeLower + "-" + rangeUpper; 
    } 
} 

public class PuzzleSet extends ArrayList<PuzzleData> implements Serializable 
{ 
    public PuzzleSet higherThan(int lowBound) 
    { 
     PuzzleSet s = new PuzzleSet(); 
     for (int i=0; i<size(); i++) 
     { 
      if (get(i).rangeLower > lowBound) 
       s.add(get(i)); 
     } 
     return s; 
    } 

    public PuzzleSet startsAtPoint(int point) 
    { 
     PuzzleSet s = new PuzzleSet(); 
     for (int i=0; i<size(); i++) 
     { 
      if (get(i).rangeLower == point) 
       s.add(get(i)); 
     } 
     return s; 
    } 

    public double sum() 
    { 
     double sum = 0.0; 
     for (int i=0; i<size(); i++) 
      sum += get(i).price; 
     return sum; 
    } 

    public String toString() 
    { 
     StringBuffer b = new StringBuffer(); 
     for (int i=0; i<size(); i++) 
     { 
      b.append(get(i).toString()); 
     } 
     return b.toString(); 
    } 
} 

Answer 1

JSR-166Y ha lo scopo di facilitare l'implementazione della ricorsione parallela in Java 7 curando il coordinamento dei thread. È possibile trovare utili discussioni, codice e documenti (in particolare il documento di Doug Lea A Java Fork/Join Framework).

Answer 2

Il tipo di problema mi ricorda algoritmi genetici. Hai già una funzione di fitness (il costo) e il layout del problema sembra adatto al crossover e alla mutazione. Potresti utilizzare uno dei G.A. disponibili motori ed eseguire più pool/generazioni in parallelo. G.A tende a trovare buone soluzioni abbastanza velocemente, sebbene non sia garantita la ricerca della migliore soluzione in assoluto. D'altra parte, credo che il puzzle che descrivi non abbia necessariamente una sola soluzione ottimale. G.A. le soluzioni sono spesso utilizzate per la pianificazione (ad esempio per creare un elenco di insegnanti, aule e classi). Le soluzioni trovate sono solitamente "robuste" nel senso che una soluzione ragionevole che soddisfa un cambiamento nei vincoli può spesso essere trovata con un numero minimo di modifiche.

Come parallelizzare l'algoritmo ricorsivo specificato. L'ho provato di recente (usando Terracotta) per il problema n-Queens e ho fatto qualcosa di simile a ciò che descrivi. La regina della prima riga viene posizionata in ogni colonna possibile per creare n sottoproblemi. C'è un pool di thread di lavoro. Un pianificatore di lavoro controlla se c'è un thread di lavoro inattivo disponibile nel pool e lo assegna come sottoproblema. Il thread worker funziona attraverso il sottoproblema, emette tutte le soluzioni trovate e torna allo stato di attesa. Poiché in genere ci sono molti meno thread di lavoro rispetto ai sottoproblemi, non è un grosso problema se i sottoproblemi non richiedono tempi di risoluzione uguali.

Sono curioso di sentire altre idee.

Answer 3

potresti usare monte carlo e gestirli in parallelo. aggiungere un po 'di casualità nel termine di selezione del pezzo per ottenere basato sui vincoli.