Percolation
Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

Percolation



  1. #1
    invite6b1a864b

    Percolation


    ------

    Bonjour,

    Il s'agit d'une question sur lequel je but depuis pas mal de temps, à la limite entre mathématique et informatique .. et qui apparement n'a jamais été résolu..

    Voilà, étant donné un graph non orienté de forme quelquonque, j'ai besoin d'un algorithme qui donne rapidement l'ensemble des chemins entre deux points.. quand je dis rapidement ça veut dire en O(ln(n))..
    (autrement dit, le temps de résolution augmente avec le logarithme du nombre de point)

    Du point de vue informatique : on admet que les noeud ou les liens peuvent porter des informations mais qui doivent donc être mis à jour quand on ajoute ou enléve un lien de façon rapide.

    J'ai essayé plusieurs truc mais mon probléme vient principalement du fait que j'ai besoin de connaitre tout les chemins et non pas un seul..

    -----

  2. #2
    Médiat

    Re : Percolation

    Je ne suis pas certain d'avoir compris, mais si vous avez un graphe avec deux sommets A et B, et 100 sommets Xi, ainsi que toutes les arêtes (A, Xi), et (Xi, B).

    Même en considérant que seuls les chemins ne passsant pas deux fois par le même sommet sont à considérer, il me semble que lister les 100 solutions est en O(n).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  3. #3
    invite986312212
    Invité

    Re : Percolation

    si tu considères le graphe complet sur n+2 sommets, le nombre de chemins distincts entre deux sommets donnés est plus grand que le nombre de façons d'ordonner n objets, soit n!

  4. #4
    invite6b1a864b

    Thumbs up Re : Percolation

    L'idée c'est surtout que si on a un arbre vraiement quelquonque, avec donc un certain nombre de branche adjacente entre A et B (des branches qui partirait d'un point d'un point d'un chemin A entre B sans y retourner par un autre chemin), j'ai besoin d'ignorer ces branches..
    Comme par exemple si vous cherchiez les routes pour aller de Paris à marseille, vous n'iriez pas explorer l'intégralité du réseau routier..

    entre temps, j'ai eu l'idée d'un algorithme trés prometteur !!!



    Il s'agit de regrouper les points dans des ensembles de taille limité. (et de considéré ses ensembles comme des points)

    On pourrait imaginer qu'en ajoutant des liens entre les points, on construit un découpage administratif ou les liens représente des frontières communes, qui permet de savoir que de Paris à Marseille, il est inutile de passer par la Belgique..


    J'ai le mécanisme de construction

    ajoutdelien(a,b)
    {
    si (a.parent est null)
    {

    }

  5. A voir en vidéo sur Futura
  6. #5
    invite6b1a864b

    Re : Percolation

    Citation Envoyé par ambrosio Voir le message
    si tu considères le graphe complet sur n+2 sommets, le nombre de chemins distincts entre deux sommets donnés est plus grand que le nombre de façons d'ordonner n objets, soit n!
    sinon quand on dit o(ln(n)) il s'agit d'une moyenne..
    par exemple dans un arbre B, si on ne le remplis qu'avec des valeur à clef identique (ce qui serait illogique et rendrait l'arbre inutile, mais possible), l'algoritme de recherche donne logiquement toutes les valeurs en o(n)
    L'important en info c'est surtout que ça marche dans le cas général, ensuite on peut (on doit) ajouter des prises en charge pour les cas particulier

  7. #6
    invite986312212
    Invité

    Re : Percolation

    mouais, peut-être... n'empêche, le nombre de chemins dépend plutôt du nombre d'arêtes que du nombre de sommets, enfin ce n'est que mon humble avis.

  8. #7
    invite6b1a864b

    Re : Percolation

    Citation Envoyé par One Eye Jack Voir le message
    ajoutdelien(a,b)
    {
    si (a.parent est null)
    {

    }
    c'est une fausse manip.. j'ai voulu l'enlever. L'idée c'est de créer au fur et à mesure un graph simplifié au dessus du graph principal, dont chaque noeud est un ensemble de quelques noeuds lié du dessous.
    (et d'appliquer au besoin le même mécanisme au graph simplifié si besoin)

  9. #8
    invite6b1a864b

    Re : Percolation

    Citation Envoyé par ambrosio Voir le message
    mouais, peut-être... n'empêche, le nombre de chemins dépend plutôt du nombre d'arêtes que du nombre de sommets, enfin ce n'est que mon humble avis.
    Oui c'est vrai (disons que dans mon idée du cas moyen, le nombre de lien est grosso modo proportionnel au nombre de sommet...)

  10. #9
    invite6b1a864b

    Re : Percolation

    Citation Envoyé par One Eye Jack Voir le message
    Oui c'est vrai (disons que dans mon idée du cas moyen, le nombre de lien est grosso modo proportionnel au nombre de sommet...)
    Ce probléme est difficile uniquement quand on est au limite de la percolation, dans la transition de phase fractale (et oui.. )

Discussions similaires

  1. percolation de l'eau
    Par fenouille dans le forum Environnement, développement durable et écologie
    Réponses: 2
    Dernier message: 16/01/2005, 22h42