Bonsoir,

J'utilise la librairie pthread pour créer mes threads et je suis face à un problème de synchronisation :
Je travaille sur la recherche bidirectionnelle dans un graphe.

J'ai donc créer une fonction qui fait une recherche de l'état initial vers l'état final (forward) et une autre qui fait dans l'autre sens (backward)

Les étapes de l'algorithme sont les suivants :
  1. Tant que la solution n'est pas trouvée :
  2. Récupérer le résultat de la recherche FORWARD
  3. Récupérer le résultat de la recherche BACKWARD
  4. Faire un test d'union entre les deux recherches
  5. Si ce test est concluant alors quitter l'algo sinon continuer


En séquentiel, ca marche très bien mais je n'arrive pas à paralléliser la recherche BACKWARD (la recherche FORWARD sera faite dans le thread principal).

L'idée serait :
  • Créer le thread de recherche pour BACKWARD (qui sera en boucle infinie)
  • Tant que la solution n'est pas trouvée : (thread principal)
  • Récupérer le résultat de la recherche FORWARD (thread principal)
  • Attendre que le thread ait fini le premier tour
  • Faire un test d'union entre les deux recherches (thread principal)
  • Si ce test est concluant alors quitter l'algo sinon continuer (thread principal)


Je dois utiliser les threads avec conditions (et peut être des mutex) mais voilà, je sèche.

A mon avis, c'est pas clair car ce n'est pas clar pour moi non plus

Avez vous une idée ?

Merci d'avance