Discussion :

[olivier_1970]

Bonjour,
je n'arrive pas à créer un algorithme permettant de résoudre mon problème. J'ai pensé à une fonction récursive mais je n'y arrive pas. Voici mon problème :
Je possède un fichier (environ 100000 lignes) de la forme suivante
1 : 2
1 : 3
1 : 4
2 : 6
2 : 7
4 : 6
4 : 7
6 : 1
6 : 7
7 : 2
8 : 1

Ce fichier peut aussi être écrit comme cela :
1 : (2,3,4)
2 : (6,7)
4 : (6,7)
6 : (1,8)
7 : (2)
8 : (1)

Ce que je veux faire, c'est trouver tous les cycles possibles. Par exemple :
1 -> 2 -> 6 -> 1
1 -> 4 -> 6 -> 1
2 -> 7 -> 2
6 -> 8 ->1 -> 2 -> 6.
Les chemins suivants sont à ignorer :
1 -> 3 qui n'existe pas : on s’arrête.
Si un chemin ne donne pas de cycle il doit être ignoré.

Pour chaque valeur, j'ai une liste de 0 à 10 éléments.
Si quelqu'un peut me donner une idée...
Merci

[10_GOTO_10]

Pour commencer, je suppose que la deuxième ligne 6 est "6 : 8", vu les cycles que tu donnes ensuite.

En fait, ton problème est une recherche de cycles dans un graphe orienté, chaque ligne correspondant à un arc dans ton graphe.

Il y a une discussion là dessus ici : http://www.developpez.net/forums/d10...cles-d-graphe/

Et tu as des algorithmes ici : http://en.wikipedia.org/wiki/Cycle_detection

[olivier_1970]

Et tu as des algorithmes ici : http://en.wikipedia.org/wiki/Cycle_detection

Merci, je viens de regarder cette page mais est-ce qu'elle s'applique à mon cas ? Moi je n'ai pas forcément une 'fonction'.
En effet, le 1 par exemple peut donner 2, 3 ou 4. C'est ça que je n'arrive pas à écrire récursivement.
Olivier

[lautrec1]

Merci, je viens de regarder cette page mais est-ce qu'elle s'applique à mon cas ? Moi je n'ai pas forcément une 'fonction'.
En effet, le 1 par exemple peut donner 2, 3 ou 4. C'est ça que je n'arrive pas à écrire récursivement.
Olivier

Pour pouvoir t'aider précisément, nous avons besoin d'en connaitre plus sur ta méthode actuelle.
Utilises-tu une matrice d'adjacences ? Un tableau global avec les valeurs envisagées successives ?
Tes données sont de grande taille, n'emploie pas un tableau local à la récursion pour éviter un dépassement de mémoire.

Sinon, la fonction de récursion devrait fort ressembler à cela

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
MaFonction (premierElementDeLaPile,tableauDAdjacences)
si l'élément est égal au premier élément de la pile globale,
    {imprimer la liste}
 
sinon
{
    générer les éléments adjacents à l'élément courant de la pile (tous les j | T[élémentCourant][j]==1]
    {
        ajouter l'élément généré à la pile
        appel de MaFonction(premierElementDeLaPile,tableauDAdjacences)
        dépiler l'élément courant de la pile
    }
}

Bon courage!