IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

algorithme récursif et itératif


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Profil pro
    Inscrit en
    Février 2008
    Messages
    130
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 130
    Points : 80
    Points
    80
    Par défaut algorithme récursif et itératif
    Bonjour, je me pose une question par rapport à un graphe quelconque comportant n nœuds tel que n > 100000 (donc au max (n*(n-1))/2 arêtes).
    Dans un tel cas, quel type d'algorithme est le plus adapté : le récursif ou l'itératif par exemple dans le parcours en profondeur ?

    Personnellement je dirais l'itératif qui a moins de chance de saturer la pile d'exécution, mais là pareil transformer un algorithme récursif en itératif signifie simuler la pile créer par la récursivité par une structure de données de type pile, et je me demande si cette pile (la structure de données est plus performante que la pile d'exécution créer par la récursivité). En bref quoi privilégier ?

  2. #2
    Membre éclairé
    Avatar de bricecol
    Homme Profil pro
    Consultant informatique
    Inscrit en
    Avril 2007
    Messages
    364
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 364
    Points : 654
    Points
    654
    Par défaut
    Personnellement je dirais l'itératif qui a moins de chance de saturer la pile d'exécution
    j'aurais dit que le récursif est mieux si tu ne fais que parcourir l'arbre, on peut, je pense, sans peine, libérer de la mémoire au fur et à mesure. non ? je n'en suis pas sûr ^^
    "Computers are like Old Testament gods ; Lots of rules and no mercy"
    [ Les ordinateurs sont comme les dieux de l’Ancien testament ; Beaucoup de règles et aucune pitié. ] Joseph Campbell

  3. #3
    Membre régulier
    Profil pro
    Inscrit en
    Février 2008
    Messages
    130
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 130
    Points : 80
    Points
    80
    Par défaut
    le truc c'est que j'ai l'intention de modifier le parcours en profondeur pour lui permettre de détecter les cycles dans le graphe

  4. #4
    Membre éclairé
    Avatar de bricecol
    Homme Profil pro
    Consultant informatique
    Inscrit en
    Avril 2007
    Messages
    364
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : Avril 2007
    Messages : 364
    Points : 654
    Points
    654
    Par défaut
    il y a le DFS (depth first search), parcours en profondeur d'un graphe
    [ame]http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur[/ame]
    (une boucle pour chaque fils et un appel récursif pour chacun...)

    après sinon tu as le le BFS (Breadth First Search), le parcours en largeur !
    il utilise une file de type FIFO (first in first out
    )
    [ame]http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur[/ame]

    le truc c'est que j'ai l'intention de modifier le parcours en profondeur pour lui permettre de détecter les cycles dans le graphe
    je te conseilles d'utiliser le DFS en le modifiant à ta sauce. cependant, compter les cycles en même temps... il y a une algo je crois : [ame]http://en.wikipedia.org/wiki/Cycle_detection[/ame] (il est très drôle tu vas voir). je ne pense pas que ce sera de la tarte pour coupler (si c'est possible) le DFS et le "tortoise and hare"

    bonne chance en tout cas !
    "Computers are like Old Testament gods ; Lots of rules and no mercy"
    [ Les ordinateurs sont comme les dieux de l’Ancien testament ; Beaucoup de règles et aucune pitié. ] Joseph Campbell

  5. #5
    Expert éminent Avatar de Graffito
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    5 993
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 993
    Points : 7 903
    Points
    7 903
    Par défaut
    quel type d'algorithme est le plus adapté : le récursif ou l'itératif ?
    - Le récursif pour la facilité de programmation.
    - La transformation en iteratif pour la performance et l'occupation mémoire.

    Comme tu le penses, Un récursif (bien) transformé est en principe moins gourmand que le récursif.
    " Le croquemitaine ! Aaaaaah ! Où ça ? " ©Homer Simpson

  6. #6
    Membre actif
    Inscrit en
    Juin 2008
    Messages
    189
    Détails du profil
    Informations forums :
    Inscription : Juin 2008
    Messages : 189
    Points : 268
    Points
    268
    Par défaut
    Un algorithme itératif de parcours de graphe est finalement assez simple.

    On se base en général sur 2 ensembles :
    - 1 ensemble des éléments visité
    - 1 ensemble des éléments à visiter

    Je pense que tu imagines le reste :
    - on initialise les visité à vide, les "à visiter" avec le sommet de départ
    - Puis on boucle tant qu'il reste des éléments à visiter (en ajoutant évidemment chaque enfants du sommet courant dans l'ensemble des éléments à visiter). pis si le sommet courant est déjà visité, on saute l'étape

  7. #7
    Membre régulier
    Profil pro
    Inscrit en
    Février 2008
    Messages
    130
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 130
    Points : 80
    Points
    80
    Par défaut
    merci pour vos réponses
    Donc si j'ai bien compris il me faudrait faire un algorithme itératif pour viser la rapidité d'exécution ?

  8. #8
    Membre régulier
    Inscrit en
    Septembre 2007
    Messages
    114
    Détails du profil
    Informations forums :
    Inscription : Septembre 2007
    Messages : 114
    Points : 120
    Points
    120
    Par défaut
    L'algorithm des rangs permet de détécter assez simplement si oui ou non il existe des cycles. Normalement il ne retourne pas ces cycles ( il s'arrête au premier) mais tu devrais pouvoir en sortir quelque chose.

Discussions similaires

  1. [PHP 5.3] Transformer algorithme récursif en itératif
    Par Bakura dans le forum Langage
    Réponses: 2
    Dernier message: 29/12/2010, 20h16
  2. Algorithme récursif (Poker)
    Par MagicTux dans le forum Débuter
    Réponses: 5
    Dernier message: 31/01/2009, 15h12
  3. Algorithme récursif de calcul de moyenne
    Par kromartien dans le forum Mathématiques
    Réponses: 25
    Dernier message: 23/10/2007, 12h05
  4. [SQL] Tree : algorithme récursif
    Par Fabouney dans le forum PHP & Base de données
    Réponses: 4
    Dernier message: 03/08/2007, 16h39
  5. problème algorithme récursif
    Par seb888 dans le forum Général Java
    Réponses: 11
    Dernier message: 04/06/2005, 22h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo