Multi-threaded algorithme pour résoudre sudoku?
j'ai un devoir à faire pour écrire un solveur sudoku multi-threadé, qui trouve toutes les solutions à un puzzle donné. J'ai déjà écrit un solveur sudoku mono-fileté très rapide, donc je n'ai pas besoin d'aide avec l'aspect de résolution sudoku.
mon problème est probablement lié à la concurrence grokking pas vraiment, mais je ne vois pas comment ce problème bénéficie de multi-threading. Je ne comprends pas comment vous pouvez trouver des solutions différentes au même problème à la même temps sans conserver plusieurs copies du puzzle. Compte tenu de cette hypothèse (veuillez prouver que c'est faux), Je ne vois pas comment la solution multi-threadée est plus efficace qu'un mono-threadé.
j'apprécierais si quelqu'un pouvait me donner quelques suggestions de départ pour l'algorithme (s'il vous plaît, pas de code...)
j'ai oublié de mentionner, le nombre de threads à utiliser est spécifié comme argument au programme, donc autant que je peux dire c'est pas liés à l'état de la réflexion en quelque sorte...
En outre, il n'y a peut - être pas de solution unique-une entrée valide peut être une carte totalement vide. J'ai de rapport min(1000, number of solutions) et l'affichage de l'un d'entre eux (si elle existe)
13 réponses
plutôt simple en fait. Le concept de base est que dans votre solution de backtracking vous vous ramifiez quand il y avait un choix. Vous avez essayé une branche, retracé et ensuite essayé l'autre choix.
maintenant, lancez un thread pour chaque choix et essayez les deux simultanément. Ne lancer un nouveau thread que s'il y a < un certain nombre de threads déjà dans le système (ce serait votre argument d'entrée), sinon utilisez simplement un simple (I. e votre solution existante) mono-filetée. Pour l'ajout efficacité, obtenez ces threads ouvriers d'un pool de threads.
il s'agit à bien des égards d'une technique de diviser pour mieux régner, vous utilisez les choix comme une occasion de diviser l'espace de recherche en deux et allouer une moitié à chaque fil. Probablement la moitié est plus dur que les autres sens fil des durées de vie varient, mais c'est ce qui rend l'optimisation intéressante.
la manière la plus simple de gérer les problèmes de syncronisation évidents est de copier l'état actuel de la carte et passer dans chaque instance de votre fonction, c'est donc un argument de fonction. Cette copie signifie que vous n'avez pas à vous soucier de la concurrence partagée. Si votre solution monofiletée utilise une variable globale ou membre pour stocker l'état de la carte, vous aurez besoin d'une copie de celle-ci soit sur la pile (facile) ou par thread (plus dur). Tous votre fonction doit retourner au conseil d'administration de l'état et un certain nombre de coups pris pour l'atteindre.
chaque routine qui invoque plusieurs fils pour faire du travail devrait invoquer n-1 threads quand il y a n morceaux de travail, faire le nième morceau de travail et puis attendre avec un objet de syncronisation jusqu'à ce que tous les autres threads sont finis. Vous évaluez alors leurs résultats - vous avez n états de bord, retourner celui avec le moins de mouvements.
multi-threading est utile dans n'importe quelle situation où un seul thread doit attendre une ressource et vous pouvez exécuter un autre thread dans l'intervalle. Cela inclut un thread en attente d'une demande d'E/S ou d'un accès à la base de données pendant qu'un autre thread continue avec le travail CPU.
Multi-threading est également utile si les fils individuels peuvent être affinés vers des CPU (ou des noyaux) diffus car ils fonctionnent alors vraiment en même temps, bien qu'ils devront généralement partager des données pour qu'il y ait toujours un peu de contention.
Je ne vois pas pourquoi un solveur Sudoku multi-threadé serait plus efficace qu'un simple-threadé, simplement parce qu'il n'y a pas de ressources à attendre. Tout sera fait dans la mémoire.
mais je me souviens de certains des devoirs que j'ai fait à Uni, et il était tout aussi inutile (Fortran code pour voir comment profond un tunnel a obtenu quand vous avez creusé à 30 degrés pour un mile puis 15 degrés pour un autre mile - Oui, je suis assez vieux :-). Le point est d' montrez que vous pouvez le faire, pas que ce soit utile.
Sur l'algorithme.
j'ai écrit un seul solveur fileté qui a essentiellement couru une série de règles dans chaque passe pour essayer de peupler un autre carré. Une règle d'échantillonnage était: si la rangée 1 a seulement un carré libre, le nombre est évident de tous les autres nombres dans la rangée 1.
il y avait des règles similaires pour toutes les rangées, toutes les colonnes, toutes les mini-grilles 3x3. Il y a aussi des règles qui cochent les intersections ligne/colonne (par exemple si une carré ne pouvait contenir que 3 ou 4 en raison de la rangée et 4 ou 7 en raison de la colonne, puis il était 4). Il y avait des règles plus complexes que je ne détaillerai pas ici, mais elles sont essentiellement de la même façon que vous les résolvez manuellement.
je soupçonne que vous avez des règles similaires dans votre mise en œuvre (depuis autre que la force brute, Je ne peux penser à aucune autre façon de résoudre, et si vous avez utilisé la force brute, il n'y a aucun espoir pour vous :-).
ce que je suggère est d'attribuer chaque règle à un thread et de les avoir partager la grille. Chaque fil ferait sa propre règle et seulement cette règle.
mise à Jour:
Jon, basé sur votre edit:
[edit] j'ai oublié de mentionner, le nombre de threads à utiliser est spécifié comme argument au programme, donc autant que je peux dire c'est pas liée à l'état de la réflexion en quelque sorte...
en outre, il n'y a peut - être pas de solution unique-une entrée valide peut être une carte totalement vide. Je dois signaler min (1000, nombre de solutions) et afficher l'une d'elles (si elle existe)
il semble que votre enseignant ne veut pas que vous divisiez en fonction des règles mais plutôt des fourchettes (où plusieurs règles pourraient s'appliquer).
par cela je veux dire, à n'importe quel point dans la solution, s'il y a deux ou plusieurs avances possibles, vous devriez attribuer chaque possibilité à un thread séparé (toujours en utilisant vos règles pour l'efficacité mais en vérifiant simultanément chaque possibilité). Ce cela vous donnerait une meilleure simultanéité (en supposant que les threads puissent être exécutés sur des CPU/noyaux séparés) puisqu'il n'y aura pas de conflit pour la carte; chaque thread obtiendra sa propre copie.
de plus, puisque vous limitez le nombre de threads, vous devrez faire un peu de magie pour y arriver.
ce que je suggère est d'avoir une file d'attente de travail et n Fils. La file d'attente de travail est initialement vide lorsque votre thread principal démarre tous les threads worker. Puis le fil principal met l'état de début de puzzle dans la file d'attente de travail.
Les threads de simplement attendre pour un état d'être placé sur la file d'attente de travail et l'un d'eux l'attrape pour le traitement. Le thread de travail est votre solveur à filetage simple avec une petite modification: lorsqu'il y a X possibilités d'aller de l'avant (X > 1), votre travailleur remet X-1 de ceux-ci sur la file d'attente de travail puis continue à traiter l'autre possibilité.
alors, disons qu'il n'y a qu'une solution (vrai Sudoku :-). Le le premier worker thread va tailler loin à la solution sans trouver de fourches et ce sera exactement comme dans votre situation actuelle.
mais avec deux possibilités au mouvement 27 (disons, 3 ou 4 pourrait aller dans la cellule supérieure gauche), votre fil va créer une autre planche avec la première possibilité (mettez 3 dans cette cellule) et placez cela dans la file d'attente de travail. Puis il en mettait 4 dans sa propre copie et continuait.
un autre fil va prendre la planche avec 3 dans cette cellule et continuer. De cette façon, vous avez deux threads lancés simultanément pour gérer les deux possibilités.
quand n'importe quel fil décide que sa planche est insoluble, il la jette et retourne à la file d'attente de travail pour plus de travail.
quand n'importe quel fil décide que sa planche est résolue, il avertit le fil principal qui peut le stocker, en sur-écrivant n'importe quelle solution précédente (la première-trouvée est la solution) ou la jeter si elle a déjà une solution (la dernière-trouvée est la solution) alors le fil ouvrier va retour à la file d'attente de travail pour plus de travail. Dans un cas comme dans l'autre, le fil principal doit augmenter le nombre de solutions trouvées.
lorsque tous les threads sont inactifs et que la file d'attente de travail est vide, main aura ou non une solution. Il y aura aussi un grand nombre de solutions.
gardez à l'esprit que toutes les communications entre les travailleurs et le fil principal devront être altérées (je suppose que vous le savez sur la base des informations contenues dans votre question).
l'idée derrière le multi-threading est de profiter d'avoir plusieurs CPU, vous permettant de faire plusieurs calculs simultanément. Bien sûr, chaque thread va avoir besoin de sa propre mémoire, mais ce n'est généralement pas un problème.
la plupart du temps, ce que vous voulez faire est de diviser l'état de solution possible en plusieurs sous-espaces qui sont aussi indépendants que possible( pour éviter d'avoir à gaspiller trop de ressources sur la création de thread overhead), et pourtant "adapter" votre algorithme (pour bénéficier réellement d'avoir plusieurs threads).
Voici une gourmande force brute single-threaded solveur:
- sélectionnez la case vide suivante. Si pas plus de cellules vides, de victoire!
- valeur possible de la cellule = 1
- vérifier si la solution partielle n'est pas valide (duplicata dans la rangée, la colonne ou le bloc 3x3).
- si la solution partielle est invalide, incrémenter la valeur de la cellule et revenir à l'étape 3. Sinon, passez à l'étape 1.
Si vous regardez ce qui précède, la combinaison des étapes 2 et 3 sont évidents les candidats pour le multithreading. Des solutions plus ambitieuses impliquent la création d'une exploration récursive qui engendre des tâches qui sont soumises à un pool de threads.
éditer pour répondre à ce point: "je ne comprends pas comment vous pouvez trouver des solutions différentes au même problème en même temps sans maintenir plusieurs copies du puzzle."
Vous ne pouvez pas. C'est l'ensemble de point. Cependant, un exemple concret de 9 fils pourrait rendre les avantages plus claire:
- commencer par un problème d'exemple.
- Trouver la première cellule vide.
- créer 9 threads, où chaque thread a sa propre copie du problème avec son propre index comme valeur candidate dans la cellule vide.
- dans chaque thread, exécutez votre algorithme original sur ce thread-copie locale modifiée du problème.
- Si l'un des threads trouve une réponse, arrêtez tous les autres threads.
Comme vous pouvez le imaginez, chaque thread est maintenant en train d'exécuter un espace de problème légèrement plus petit et chaque thread a le potentiel d'exécuter sur son propre noyau CPU. Avec un algorithme simple-fileté seul, vous ne pouvez pas récolter les avantages d'une machine multi-noyau.
a-t-il besoin de bénéficier de la multithreading, ou tout simplement faire usage de la multithreading afin que vous puissiez apprendre pour la tâche?
si vous utilisez un algorithme de force brute, il est assez facile de le diviser en plusieurs threads, et si la tâche est axée sur le codage des threads qui peut être une solution acceptable.
quand vous dites toutes les solutions à un puzzle donné, voulez-vous dire la dernière et la seule solution pour le puzzle? Ou les différentes façons d'arriver à une solution? J'étais d'accord que par définition, un puzzle sudoku ne pouvait avoir qu'une seule solution...
Pour les anciens, soit approche fondée sur les règles de Pax ou Tom Leys " prendre sur le multi-threading votre mandature algorithme peut-être le chemin à parcourir.
si ce dernier, vous pouvez implémenter une sorte d'algorithme de branchement qui lance un nouveau fil (avec sa propre copie du puzzle) pour chaque mouvement possible à chaque étape du puzzle.
selon la façon dont vous avez codé votre résolveur fileté unique, vous pourriez être en mesure de réutiliser la logique. Vous pouvez coder un solveur multi-threadé pour démarrer chaque thread en utilisant un ensemble différent de stratégies pour résoudre le puzzle.
en utilisant ces différentes stratégies, votre solveur multi-threadé peut trouver l'ensemble des solutions en moins de temps que votre seul solveur threadé (gardez à l'esprit cependant qu'un vrai puzzle Sudoku n'a qu'une seule solution...tu n'es pas le seul à avoir eu affaire à ce jeu terrible de Dieu en classe)
quelques points généraux: Je n'exécute pas les processus en parallèle à moins que 1) il soit facile de diviser le problème 2) je sais que je vais obtenir un avantage à le faire - par exemple, Je ne vais pas frapper un autre goulot d'étranglement. J'évite totalement de partager des valeurs mutables entre les threads - ou de les minimiser. Certaines personnes sont assez intelligentes pour travailler en toute sécurité avec des Mutex. Je ne suis pas.
vous devez trouver des points dans votre algorithme qui créent des branches naturelles ou de grandes unités de travail. Une fois que vous avez identifié une unité à travailler, vous le déposez dans un file d'attente pour un fil à ramasser. Comme un exemple insignifiant. 10 bases de données à mettre à jour. Lancez la mise à niveau async sur les 10 serveurs. Attendez que tout soit terminé. Je peux facilement éviter de partager l'état entre les threads / processus, et peut facilement agréger les résultats.
ce qui vient à l'esprit pour sudoku est qu'une solution suduko efficace devrait combiner 2-3 (ou plus) stratégies qui ne dépassent jamais une certaine profondeur. Quand je fais Sudoku, il est évident qu'à tout moment, différents algorithmes fournissent solution avec le moins de travail. Vous pourriez simplement lancer une poignée de stratégies, les laisser enquêter à une profondeur limitée, attendre le rapport. Rincez, répétez. Cela évite de" forcer la solution". Chaque algorithme a son propre espace de données, mais vous combinez les réponses.
Sciam.com il y avait un article là - dessus il y a un an ou deux, mais on dirait que ce n'est pas public.
vous avez dit avoir utilisé le retraçage arrière pour résoudre le problème. Ce que vous pouvez faire est de diviser l'espace de recherche en deux et de manipuler chaque espace à un fil, puis chaque fil ferait la même chose jusqu'à ce que vous atteigniez le dernier noeud. J'ai une solution à ce qui peut être trouvé www2.cs.uregina.ca/~hmer200a mais en utilisant un seul fil, mais le mécanisme de fractionnement de l'espace de recherche est-il à l'aide de branch and bound.
il y a quelques années, lorsque j'ai examiné la résolution de sudoku, il semblait que la solution optimale utilisait une combinaison d'algorithmes d'analyse logique et ne retombait sur la force brute qu'en cas de nécessité. Cela a permis au solveur de trouver la solution très rapidement, et aussi de classer la carte par difficulté si vous vouliez l'utiliser pour générer un nouveau puzzle. Si vous avez adopté cette approche, vous pourriez certainement introduire une certaine concurrence, bien que le fait d'avoir les fils fonctionnent réellement ensemble pourrait être délicat.
j'ai une idée qui est assez amusant ici.. le faire avec l'Acteur de Modèle! Je dirais en utilisant erlang.. Comment? Vous commencez avec la carte d'origine, et..
- 1) à la première cellule vide créer 9 enfants avec le nombre différent, puis commettre le suicide
- 2) chaque enfant vérifie s'il est invalide, s'il se suicide, sinon
- s'il y a une cellule vide, passez à 1)
- si complet, cet acteur est une solution
Clairement tous les survivants de l'acteur est une solution au problème =)
juste une petite note. En fait, j'ai mis en place un solveur sudoku optimisé et j'ai regardé dans le multithreading, mais deux choses m'ont arrêté.
tout d'abord, le simple survol du démarrage d'un thread a pris 0,5 millisecondes, alors que la résolution totale a pris entre 1 et 3 millisecondes (J'ai utilisé Java, d'autres langages ou environnements peuvent donner des résultats différents).
Deuxièmement, la plupart des problèmes ne nécessitent pas de retour en arrière. Et ceux qui le font, n'en ont besoin que tard dans la résolution du problème, une fois que toutes les règles du jeu ont été épuisées et nous avons besoin de faire une hypothèse.
Voici mon propre penny. Espérons que cela aide.
rappelez-vous que les communications entre processeurs/entre threads sont coûteuses. Ne pas multi-thread, à moins que vous . S'il n'y a pas beaucoup de travail/calcul à faire dans d'autres threads, vous pourriez aussi bien continuer avec un simple thread.
Essayez autant que possible de éviter partage de données entre les threads. Utilisez - les uniquement si nécessaire
profitez de extensions SIMD dans la mesure du possible. Avec les Extensions vectorielles, Vous pouvez effectuer des calculs sur plusieurs données en un seul swoop. Il peut vous aider à profusion.