Percolation

[invite6b1a864b]

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..
-----

[Médiat]

Je ne suis pas certain d'avoir compris, mais si vous avez un graphe avec deux sommets A et B, et 100 sommets X_i, ainsi que toutes les arêtes (A, X_i), et (X_i, 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).

[invite986312212]

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!

[invite6b1a864b]

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)
{

}

[A voir en vidéo sur Futura]

[invite6b1a864b]

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

[invite986312212]

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.

[invite6b1a864b]

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)

[invite6b1a864b]

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...)

[invite6b1a864b]

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.. )