Параллельное программирование с рекурсивными функциями?

Предпосылки проблемы: я пытаюсь написать алгоритм решения головоломки, который использует преимущества многоядерных процессоров и параллельной обработки. Однако идеальным / самым простым решением является простая рекурсивная функция.

Как лучше всего разбить решение, используя преимущества параллельной обработки И рекурсивной функции?

Приведенный ниже код представляет собой решение для простого алгоритма решения головоломок (он работает правильно) , Загадка в этом примере проста - 14 слотов пронумерованы 1-14. Каждая часть головоломки имеет уникальный идентификатор, диапазон, который говорит вам, где он может начинаться и останавливаться (например, 6-8 означает, что он только помещается в слоты 6-8), и цена. Алгоритм пытается найти решение, которое максимизирует цену решения. Только 1 часть может занимать слот, и пустые слоты допустимы. Решение скажет вам, какие части используются и общую стоимость. (Для простоты предположим также, что слот 1 ДОЛЖЕН быть заполнен.)

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

В то время как простая рекурсия здесь хорошо сработала, я представляю этот прогон с головоломкой, которая имеет 200 слотов и 5000 штук.

Вот и решение этого примера:

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();
    }
}