Programmation parallèle avec fonctions récursives?

Contexte du problème: J’essaie d’écrire un algorithme de solution de casse-tête qui tire parti des processeurs multicœurs et du traitement en parallèle. Cependant, la solution idéale / la plus simple est une simple fonction récursive.

Quel est le meilleur moyen de décomposer la solution pour tirer parti du parallel processing ET de la fonction récursive?

Le code ci-dessous est une solution pour un algorithme simple de résolution de casse-tête (il fonctionne correctement). Le casse-tête dans cet exemple est simple: il y a 14 emplacements numérotés de 1 à 14. Chaque pièce du puzzle a un identifiant unique, une plage qui vous indique où il peut commencer et s’arrêter (par exemple, 6-8 signifie qu’il ne tient que dans les emplacements 6 à 8) et un prix. L’algorithme tente de trouver la solution qui maximise le prix de la solution. Une seule pièce peut occuper un emplacement et les emplacements vides sont acceptables. La solution vous indiquerait quelles pièces sont utilisées et le coût total. (Pour que les choses restnt simples, supposons également que l’emplacement 1 DOIT être rempli).

Voici ma tentative de combiner parallélisme et récursion: créez une tâche pour chaque pièce utilisant l’emplacement 1, puis, dans la tâche, parcourez le rest des pièces de manière récursive, en les plaçant dans les espaces restants tout en maximisant les coûts. Est-ce la meilleure solution (probablement pas, c’est pourquoi je suis ici). Comment peut-il être amélioré? D’autres bonnes recommandations lors de l’utilisation de solutions parallèles / récursives?

Bien que la récursion simple fonctionne bien ici, je pense à cette course avec un puzzle qui a 200 emplacements et 5000 pièces.

Voici la solution à cet exemple également:

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> tasks = new ArrayList<Callable>(); 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() { public PuzzleSet call() { PuzzleSet s = new PuzzleSet(); s.add(d); s.addAll(getPrice(start)); return s; } }); } List<Future> results = exec.invokeAll(tasks); PuzzleSet max = new PuzzleSet(); double maxD = 0.0; for (int i=0; i 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 maxD) { maxD = pTemp; s.add(input.get(i)); max = s; } } return max; } public static void main(Ssortingng 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 implements Serializable { public PuzzleSet higherThan(int lowBound) { PuzzleSet s = new PuzzleSet(); for (int i=0; i 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(); } }

JSR-166Y est destiné à faciliter la mise en œuvre de la récursion parallèle dans Java 7 en prenant en charge la coordination des threads. Vous trouverez peut-être leurs discussions, leur code et leurs documents (en particulier le document de Doug Lea intitulé A Java Fork / Join Framework ) utile.

Le type de problème me rappelle les algorithmes génétiques. Vous avez déjà une fonction de mise en forme (le coût) et la présentation du problème semble adaptée au croisement et à la mutation. Vous pouvez utiliser l’un des moteurs GA disponibles et exécuter plusieurs pools / générations en parallèle. Les GA ont tendance à trouver de bonnes solutions assez rapidement, bien que trouver la meilleure solution absolue ne soit pas garanti. D’autre part, je pense que le casse-tête que vous décrivez ne contient pas nécessairement une solution optimale unique. Les solutions d’AG sont souvent utilisées pour la planification (par exemple, pour créer une liste d’enseignants, de salles de classe et de classes). Les solutions trouvées sont généralement «robustes» en ce sens qu’une solution raisonnable tenant compte d’un changement des contraintes peut souvent être trouvée avec un nombre minimal de changements.

Quant à la parallélisation de l’algorithme récursif donné. J’ai récemment essayé ceci (en utilisant Terracotta) pour le problème n-Queens et j’ai fait quelque chose de similaire à ce que vous décrivez. La reine de première rangée est placée dans chaque colonne possible pour créer n sous-problèmes. Il existe un pool de threads de travail. Un planificateur de travaux vérifie s’il existe un thread de travail inactif dans le pool et lui atsortingbue un sous-problème. Le thread de travail traite le sous-problème, génère toutes les solutions trouvées et revient à l’état inactif. Parce qu’il y a généralement beaucoup moins de threads de travail que de sous-problèmes, le problème n’est pas grave si les sous-problèmes ne prennent pas autant de temps à résoudre.

Je suis curieux d’entendre d’autres idées.

vous pouvez utiliser monte carlo et les exécuter en parallèle. append un peu de hasard en terme de sélection de pièce à obtenir en fonction des contraintes.