Предпосылки проблемы: я пытаюсь написать алгоритм решения головоломки, который использует преимущества многоядерных процессоров и параллельной обработки. Однако идеальным / самым простым решением является простая рекурсивная функция.
Каков наилучший способ разбить решение, чтобы использовать преимущества параллельной обработки И рекурсивной функции?
Приведенный ниже код является решением для простого алгоритма решения головоломки (он работает правильно). Загадка в этом примере проста - 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();
}
}