Mais non ! Une factorielle n'est pas polynomiale.Envoyé par djar
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).
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...
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.
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...
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
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.
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...
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?
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.
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.
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
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.
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.
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)!
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
