Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 46 sur 46

Complexité algo recherche degré de connexité...



  1. #31
    Sylvestre

    Re : Complexité algo recherche degré de connexité...


    ------

    Citation Envoyé par djar Voir le message
    Attends... Tu veux dire que meme si j'ai une factorielle, ce n'est pas si grave ? Cela veut dire que ce serait polynomial quand meme ?!!? Ce serait super parce que la demo est deja faite !
    Mais non ! Une factorielle n'est pas polynomiale.
    Je croyais que tu avais trouvé quelque chose qui te permettait d'éviter cette factorielle. Donc, si je résume, tu n'as pas vraiment d'algorithme polynomial pour résoudre ce problème.
    Si tu penses pouvoir arriver à en trouver un bientôt c'est bien. Je serai très curieux de lire ta solution dans un grand journal d'informatique (ou bien sur Futura, si tu acceptes).

    -----

  2. #32
    djar

    Re : Complexité algo recherche degré de connexité...

    C'est bien ce que je pensais. Je vais chercher encore, mais a mon avis pas de miracle... Mais j'ai une petite idee qui accelererais beaucoup les choses !

    Ce que j'ai donne comme complexite, c'est le pire des cas...

    A bientot...

  3. #33
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Ce que j'ai donne comme complexite, c'est le pire des cas...
    Malheureusement, expérience faite, on découvre souvent que le pire des cas arrive finalement assez souvent.
    Bonne chance pour tes améliorations.
    Si tu veux, tu peux expliquer ton algorithme et on pourra en parler plus précisément sur le forum. Je ne crois pas que qui que ce soit puisse te voler tes idées. Au pire, le forum fournit la preuve que c'est toi qui a eu l'idée.

  4. #34
    djar

    Re : Complexité algo recherche degré de connexité...

    Bon, ok...

    Alors c'est parti !
    Note: Desole pour les accents je suis en clavier qwerty...

    Voici un algo qui utilise un theoreme que j'ai trouvé, je ne sais pas si c'est une decouverte mais quoiqu'il en soit, il est correcte et facile a demontrer:

    ============================== =========
    Soit f une fonction qui pour tout point p, donne un ordre de grandeur que nous expliquerons apres.

    tf[] tableau de n couples. le premier representant f(p) et le second, l'indice du point calculé.

    structure Coupe {
    f : tresGrandEntier
    indice : entier
    }
    Pour i<-1 a n
    tf[i] <- Couple(f(pi), i)
    fpour

    trier tf par ordre croissant du premier entier du couple.
    i <- 1
    tantque graphe G connexe,
    G <- supprimer(G, t[i].indice)
    i <- i + 1
    fintq
    ============================== =========
    Comment calculer f(p) ?
    Soit E = {p1, p2, ..., pn} l'ensemple des sommets d'un graphe.
    Voici comment on defini f(p)
    f : E -> N

    pour le point p appartenant au graphe, on calcule:
    Somme i <- 1 a n
    (nombre de chaines simples de longueur i)*2i
    finsomme

    Avantage: on a directement l'ordre des points a supprimer pour deconnecter le graphe.

    Premier inconvenients: le nombre de chaines simple de longueur i est loin d'etre simple a calculer. Si on resous ce probleme, alors c'est gagné.

    Deuxieme inconvenient: on ne sait pas quand s'arreter... Mais il doit exister une facon simple de le savoir... Je suis plus optimiste pour cet inconvenient.

    Mais pour le premier inconvenient, on est pas obligé de calculer exactement le nombre de chaines simples, si on a une expression avec une factorielle, on va juste chercher a la comparer avec les autres f(p)

    Celui qui me donne une solution algebrique (meme avec des factorielles) pour connaitre le nombre de chaines simples de longueur n dans un graphe, alors c'est bon, on devient celebre ...

  5. #35
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    pour le point p appartenant au graphe, on calcule:
    Somme i <- 1 a n
    (nombre de chaines simples de longueur i)*2i
    finsomme
    Avantage: on a directement l'ordre des points a supprimer pour deconnecter le graphe.
    Tu veux dire que le théorème que tu as démontré est que le minimum de points à supprimer pour déconnecter le graphe est obtenu en prenant les points qui ont des valeurs minimales pour ta fonction ?

    Sinon, concernant le second inconvénient. Est-ce qu'il s'agit bien de savoir en temps polynomial si un graphe est connexe ? Il me semble qu'un algorithme consistant à énumérer les points atteignables à partir d'un point devrait fonctionner.

    Sinon, pour le calcul de ta fonction, je n'y ai pas encore réfléchi.

    A bientôt

  6. #36
    djar

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    Tu veux dire que le théorème que tu as démontré est que le minimum de points à supprimer pour déconnecter le graphe est obtenu en prenant les points qui ont des valeurs minimales pour ta fonction ?
    Exactement, tu as bien compris. Je peux faire une démonstration, mais là, je dois t'avouer que je n'en ai pas le temps.

    Citation Envoyé par Sylvestre Voir le message
    Sinon, concernant le second inconvénient. Est-ce qu'il s'agit bien de savoir en temps polynomial si un graphe est connexe ? Il me semble qu'un algorithme consistant à énumérer les points atteignables à partir d'un point devrait fonctionner.

    Sinon, pour le calcul de ta fonction, je n'y ai pas encore réfléchi.

    A bientôt
    Oui, j'ai vu ça; ce dernier probleme n'est pas compliqué et se résous en temps polynomial.

    Il ne reste plus qu'a enumérer le nombre de chaines simples de longueur n, et ainsi le probleme n'en sera plus un...

  7. #37
    invite986312212
    Invité

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Il ne reste plus qu'a enumérer le nombre de chaines simples de longueur n, et ainsi le probleme n'en sera plus un...
    j'ai l'impression que ce nombre est grand. Pour le graphe complet à n sommets, le nombre de chaînes de longueur 1 partant d'un sommet donné est n-1, pour les chaînes de longueur 2 c'est (n-1)(n-2), etc. On retombe sur de la factorielle, non?

  8. #38
    djar

    Re : Complexité algo recherche degré de connexité...

    Le probleme se complique quand on enleve plusieurs points...
    En fait, je pense que c'est un probleme insolvable meme si le contraire n'a pas encore été démontré...
    J'ai reduit le probleme a un seul probleme garanti insolvable en temps polynomial (a mon avis)...

    Celui qui me prouve le contraire a gagné un million de dollars.

  9. #39
    invite986312212
    Invité

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Celui qui me prouve le contraire a gagné un million de dollars.
    mais est-ce que ce n'est pas impossible par construction? si par "énumérer" tu entends écrire une liste des chaînes, alors cet si ensemble croît de manière exponentielle tu ne peux pas le faire en un temps polynomial (ou bien j'ai une vision trop naïve de la chose?)

  10. #40
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par ambrosio Voir le message
    mais est-ce que ce n'est pas impossible par construction? si par "énumérer" tu entends écrire une liste des chaînes, alors cet si ensemble croît de manière exponentielle tu ne peux pas le faire en un temps polynomial (ou bien j'ai une vision trop naïve de la chose?)
    Je crois que Djar n'a besoin que du nombre de chaîne, il n'a pas besoin de les énumérer.
    Cela laisse un espoir.

  11. #41
    sahdow

    Re : Complexité algo recherche degré de connexité...

    t'est sur que c'est juste essaye de faire le test
    avec un graph de petersen
    car moi je croit que je viens de demonter que
    le probleme np complet est insoluble
    en temps polynomial ma demonstration n'est encore
    parfaite il ya encore des points a mieux eclaircire
    mais je pense que c'est juste
    j'ai deja une structure graph complete est bien comente
    implemente en "c" si ca t'intersse pour
    faire tes tests plus rapidement

  12. #42
    djar

    Re : Complexité algo recherche degré de connexité...

    Merci, mais en fait tant que ce probleme de factorielle n'est pas résolu, tout tombe à l'eau...

  13. #43
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par djar Voir le message
    Merci, mais en fait tant que ce probleme de factorielle n'est pas résolu, tout tombe à l'eau...
    Je ne vois pas, a priori, pourquoi le fait que le nombre de chaînes simples est non polynomiale est un problème. Il est peut-être possible de le calculer tout de même en temps polynomial (même si j'en doute fortement). Une façon de faire serait d'énumérer les éléments de la composante connexe d'un sommet en stokant uniquement le nombre de chaînes simple menant à chacun des autres sommets. Comme l'algorithme permettant de voir qu'un graphe est connexe est polynomial et qu'il ressemble à celui dont je parle maintenant, il est possible que le calcul du nombre de chaîne simple soit polynomial.

  14. #44
    Sylvestre

    Re : Complexité algo recherche degré de connexité...

    Citation Envoyé par Sylvestre Voir le message
    il est possible que le calcul du nombre de chaîne simple soit polynomial.
    J'ai passé un moment à essayer de chercher un algorithme polynomial faisant cela, mais je pense maintenant que l'on ne peut pas le faire. Je suis maintenant convaincu qu'il faut effectivement stocké les chaînes entières et pas seulement leur nombre. Ce qui rend le problème exponentiel.

  15. #45
    djar

    Re : Complexité algo recherche degré de connexité...

    Moi aussi, j'ai passé pas mal de temps à chercher... Mais merci d'avoir trouvé la faille de mon algo (qui reste cependant très bon pour résoudre le probleme sur un graphe avec peu d'arretes)!

  16. #46
    championnet

    Re : Complexité algo recherche degré de connexité...

    Ce n'est pas NP-complet pour rien

    En même temps, tu vois, je ne peux pas m'empêcher de penser que si tu avais donné ton algo dès le début, tout le monde aurait pu voir qu'il avait un défaut. Ca marche comme ça la recherche

Page 2 sur 2 PremièrePremière 2

Discussions similaires

  1. besoin d'aide a propos d'un petit algo
    Par boukmi34 dans le forum Logiciel - Software - Open Source
    Réponses: 16
    Dernier message: 02/09/2007, 17h17
  2. Chercher Algo
    Par yacine1 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 15/03/2007, 17h24
  3. transformée de Fourier (algo numérique)
    Par Heimdall dans le forum Mathématiques du supérieur
    Réponses: 8
    Dernier message: 07/03/2007, 04h52
  4. Retrouver algo à partir de résultats
    Par Delfart dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 26/02/2007, 20h30
  5. Graphes:lien entre connexite et degre
    Par Suzanna dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 25/02/2006, 16h22