Ответ 1
JSR-166Y предназначен для облегчения реализации параллельной рекурсии в Java 7, заботясь о координации потоков. Вы можете найти их обсуждения, код и документы (особенно документ Doug Lea Java Fork/Join Framework).
Параллельное программирование с рекурсивными функциями?
Предыстория проблемы: Я пытаюсь написать алгоритм решения головоломок, который использует многоядерные процессоры и параллельную обработку. Однако идеальным/простым решением является простая рекурсивная функция.
Каков наилучший способ разбить решение на оба преимущества параллельной обработки и рекурсивную функцию?
Код ниже - это решение для простого алгоритма решения головоломок (он работает правильно). В этом примере головоломка проста: есть 14 слотов с номером 1-14. Каждая головоломка имеет уникальный идентификатор, диапазон, который сообщает вам, где он может начинаться и останавливаться (например, 6-8 означает, что он подходит только в слотах 6-8) и цене. Алгоритм пытается найти решение, которое максимизирует цену решения. Только 1 штука может занимать слот, и пустые слоты приемлемы. Решение сообщит вам, какие части используются и общая стоимость. (Чтобы все было в порядке, предположим, что слот 1 ДОЛЖЕН быть заполнен).
Мое попытку объединить parallelism и рекурсию - это то, что используется ниже: создать задачу для каждой части, которая использует слот 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();
}
}
Ответы
Ответ 2
Тип проблемы напоминает мне генетические алгоритмы. У вас уже есть функция фитнеса (стоимость), и макет проблемы кажется подходящим для кроссовера и мутации. Вы можете использовать один из доступных G.A. и запускать несколько пулов/поколений параллельно. G.A склонны находить хорошие решения довольно быстро, хотя найти абсолютное лучшее решение не гарантируется. С другой стороны, я считаю, что головоломка, которую вы описываете, в любом случае не обязательно имеет единственное оптимальное решение. Г.А. решения часто используются для планирования (например, для создания списка учителей, классных комнат и классов). Найденные решения, как правило, "надежны" в том смысле, что разумное решение, предлагающее изменение ограничений, часто можно найти с минимальным количеством изменений.
Что касается распараллеливания данного рекурсивного алгоритма. Я попробовал это недавно (используя Terracotta) для проблемы n-Queens и сделал что-то похожее на то, что вы опускаете. Королева первой строки помещается в каждый возможный столбец для создания n подзадач. Существует пул рабочих потоков. Планировщик заданий проверяет, есть ли в пуле поток рабочих потоков, и назначает ему подзадачу. Рабочий поток работает через подзадачу, выводит все найденные решения и возвращается в состояние ожидания. Поскольку, как правило, гораздо меньше рабочих потоков, чем подзадачи, это не большая проблема, если подзадачи не принимают равное количество времени для решения.
Мне любопытно услышать другие идеи.
Ответ 3
вы можете использовать monte carlo и запускать их параллельно. добавьте некоторую случайность в период выбора фрагмента, чтобы получить основываясь на ограничениях.