Programación paralela con funciones recursivas?

Question

Antecedentes del problema: Estoy tratando de escribir un algoritmo de solución de rompecabezas que aproveche los procesadores multi-core y el procesamiento en paralelo. Sin embargo, la solución ideal/más fácil es una función recursiva simple.

¿Cuál es la mejor manera de desglosar la solución para que ambos aprovechen el procesamiento paralelo Y la función recursiva?

El siguiente código es una solución para un algoritmo simple de solución de acertijos (funciona correctamente). El enigma en este ejemplo es sencillo: hay 14 espacios numerados del 1 al 14. Cada pieza del rompecabezas tiene una ID única, un rango que le indica dónde puede comenzar y detener (por ejemplo, 6-8 significa que solo cabe en las ranuras 6-8), y un precio. El algoritmo intenta encontrar la solución que maximiza el precio de la solución. Solo 1 pieza puede ocupar una ranura y las ranuras vacías son aceptables. La solución le indicará qué piezas se utilizan y el costo total. (Para mantener las cosas simples, asuma también que la ranura 1 DEBE llenarse).

Mi intento de solución para combinar paralelismo y recursividad es lo que se utiliza a continuación: crear una Tarea para cada pieza que utiliza la ranura 1, luego dentro de la Tarea buscar recursivamente el resto de las piezas, ubicarlas en los espacios restantes mientras se maximiza el costo. Es esta la mejor solución (probablemente no, por eso estoy aquí). ¿Cómo puede ser mejorado? ¿Alguna otra buena recomendación al usar soluciones paralelas/recursivas?

Si bien la recursividad simple funcionaría bien aquí, me imagino que esto se ejecuta con un rompecabezas que tiene 200 ranuras y 5000 piezas.

Aquí está la solución a este ejemplo, así:

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 está destinado a facilar la implementación de la recursión paralela en Java 7 teniendo en cuenta la coordinación del subproceso. Puede encontrar útil sus discusiones, códigos y documentos (especialmente el documento de Doug Lea A Java Fork/Join Framework).

Answer 2

El tipo de problema me recuerda a los algoritmos genéticos. Ya tiene una función de acondicionamiento físico (el costo) y el diseño del problema parece adecuado para el cruce y la mutación. Puede usar uno de los G.A. motores y ejecutar múltiples grupos/generaciones en paralelo. G.A tiende a encontrar buenas soluciones bastante rápido, aunque no se garantiza la mejor solución absoluta. Por otro lado, creo que el rompecabezas que describes no necesariamente tiene una sola solución óptima de todos modos. GEORGIA. Las soluciones a menudo se utilizan para programar (por ejemplo, para crear una lista de maestros, aulas y clases). Las soluciones encontradas suelen ser "robustas" en el sentido de que a menudo se puede encontrar una solución razonable que atienda un cambio en las restricciones con un número mínimo de cambios.

En cuanto a la paralelización del algoritmo recursivo dado. Intenté esto recientemente (utilizando Terracotta) para el problema n-Queens e hice algo similar a lo que descifras. La reina de la primera fila se coloca en cada columna posible para crear n subproblemas. Hay un grupo de hilos de trabajo. Un planificador de tareas comprueba si hay un subproceso de trabajo inactivo disponible en el grupo y le asigna un subproblema. El subproceso de trabajo trabaja a través del subproblema, generando todas las soluciones encontradas y regresa al estado inactivo. Como normalmente hay muchos menos hilos de trabajo que subproblemas, no es un gran problema si los subproblemas no requieren la misma cantidad de tiempo para solucionarlos.

Tengo curiosidad por escuchar otras ideas.

Answer 3

puede usar monte carlo y ejecutarlos de forma paralela. agregue algo de aleatoriedad en el término de la selección de la pieza para obtener en función de las limitaciones.