Discussion :

[Cyberstein]

Bonjour,

Je dois développer un programme capable de résoudre des problèmes de type voyageur de commerce en C/C++ et CUDA. J'ai trouvé beaucoup d'algorithmes (Foumis, Génétique, recuit simulé, etc...) mais j'ai besoin d'un algorithme qui soit suffisamment parallélisable pour qu'il puisse s'effectuer sur la carte graphique. Le résultat peut n'être qu'une approximation, même si avoir un résultat exact est plus intéressant.

Connaissez-vous une méthode que l'on puisse appliquer en parallèle sur un grand nombre de données, ou alors un algorithme qui applique un traitement identique sur une matrice de données (la parallélisation est alors limpide) ?

J'ai aussi trouvé une méthode appelée "Match Twice and Stitch" (l'explication de la méthode est dans le fichier joint) qui semble beaucoup s'appuyer sur les matrices mais je ne la maitrise vraiment pas. Si quelqu'un pouvait me l'expliquer et me dire si elle conviendrait également, cela m'aiderais beaucoup.

Merci pour votre aide.

[SpiceGuid]

CUDA
Tu as droit aux pointeurs et à la récursion ?
Ou juste à des données numériques sous forme de matrices ?
Dans ce dernier cas je crois que tu devrais abandonner l'idée que le voyageur de commerce est une application pour CUDA.

Le résultat peut n'être qu'une approximation, même si avoir un résultat exact est plus intéressant.

L'optimum c'est un problème NP-difficile, non ?

[Cyberstein]

Bonjour et merci de vouloir m'aider.

Non, pas de pointeur ni de récursion, juste une ou plusieurs fonctions exécutées en parallèle sur différentes données, qui peuvent exploiter des variables partagées entre elles, faire des boucles (à essayer d'éviter quand même), des calculs, des conditions (à éviter un peu aussi)... A noter que chaque thread dispose par nature d'un petit identifiant, souvent utilisé pour répartir le travail.

Bien sûr TOUT n'est pas obligatoirement à faire sur la carte graphique, je peux aussi faire des calculs un peu complexe sur le CPU de manière classique et passer à CUDA pour des morceaux de calcul intensifs et parallélisables.

Pour l'optimum, oui c'est un problème NP-difficile, et je me doute qu'il n'existe pas de solution en temps polynomial. Mais un algorithme exponentiel est également acceptable pour mon projet, c'est justement pour ça que je dois utiliser la puissance de la carte graphique : Pour accélérer le calcul (entre 100 et 200 fois plus rapide que le CPU !).

Pour l'instant, je pensais utiliser un algorithme approché, si possible optimisé avec CUDA, et affiner la réponse jusqu'à l'optimum avec un second algorithme "Branch and Bound" (très ressemblant à un BrutForce classique). Reste à trouver un moyen également de répartir toutes les possibilités à essayer entre les différents threads (ABC, ACB, BCA, etc).