Bonjour,  
 
j'ai créé un petit programme c++ dans le cadre d'un projet à faire pour mes cours.  
Voici l'énoncé, ensuite ma question. Je tiens cependant à préciser qu'il ne s'agit nullement de m'aider à faire ceci ou celà => lisez hein...  
 
On a un graphe cyclique non dirigé, à poids >= 0. Imaginons que ce graphe représente la carte d'une région, chaque ville étant représentée par un sommet. Des E.T. désirent tuer tous les habitants des dites villes.  
 
Le but recherché est de trouver le nombre minimal de villes ou débarquer de façon à ce que tous les habitants soient tués endéans un délais préétabli d.  
 
Jusque là, facile  
 
Le coté "chiant" (moi j'adore ce genre de casse tête), est le suivant.  
* Une fois sur une ville, un troupe peut soit attaquer la ville si elle ne l'est pas déjà par une autre troupe, soit passer son chemin auquel cas elle se "splite" et part dnas toutes les directions disponibles (= par toutes les arrêtes sortant du sommet concerné).  
* Une troupe ne peut arrêter d'attaquer une ville qu'une fois celle-ci détruite.  
Voilà.  
 
 
=> La grosse question pour résoudre ce problème est bien entendu de savoir si une troupe doit attaquer un ville ou passer son chemin et se "spliter" (tout en sachant qu'il va falloir revenir détruire la dite ville plutard).  
 
 
 
Ma question: (enfin se diront certains...)  
J'ai trouvé une solution qui n'est pas un backtracking (ni un backtrack optimisé hein ).  
En bref, dans tous les cas testé, elle fonctionne vraiment très bien. Pour donner un petit point de comparaison, solution instantanée vs 10 sec minimum... (et ça, c'est pour de petits graphes de l'ordre de 4/7 sommets).  
 
=> Qu'en faire ? mdr  
J'aurais voulu savoir si une quelconque utilité pour ce programme vous venait à l'esprit...  
Est-ce un algorithme intéressant ?

Le vendre à des matiens !  
 
pour revenir serieux, je sais pas, fait une publication, parles-en a des chercheurs ou à des industriels...

tout d'abord pour le parcours ya bien l'algorithme de Kruskal (suis en train d'étudier ça pour mon exam de vendredi) mais je suppose que tu connais. mais bon ça donnera pas un chemin mais un arbre sous-tendant de poids minimum. ça doit pouvoir s'adapter.
pour un graphe orienté ya l'algo de dijkstra pour trouver le chemin de coût minimum.
mais pour l'utilité de tout ça!!
ben les ptits hommes verts d'abord!    
non plus sérieusement tu peux sans doute imaginer la propagation d'une information dans un réseau multiserveur. (c'est pas un modèle de P2P au fait?) bref parfois c'est plus intéressant de passer à un noeud (serveur suivant) avant de propager l'information car à partir du suivant tu peux toucher plus de clients plus rapidement.
ca peut sans doute etre utilisé pour tout ce qui est congestionnement de réseau non?
etc... avec les graphes on peut imaginer plein de trucs!!!
synchronisation de clients en un minimum de temps etc...
bref c'est plutot orienté réseau (normal c'est des graphes!)
pê aussi pour l'intelligence de l'ordinateur dans des jeux command and conquer: c typiquement ton problème car le pc doit attaquer tes villes (ou camps) de manière à gagner. bref avec un peu d'adaptation on peut faire des chouettes trucs

à mon avis ils connaissent déjà
les graphes c'est une 'structure' de modélisation mathématique
les progs comme autoroute express doivent etre inspirés de ça non?

Oui... pourquoi pas...
 
Cependant, ça n'a absolument rien à voir avec les algos courants sur les graphes tels que dijkstra, ford, bellman, et autres...
 
Ici, il ne s'agit pas de trouver le chemin le plus court entre A et B mais de savoir sur quel(s) sommet(s) il faut débarquer pour réduire à zéro le compteur de chacun des sommets du graphe.
 
 
En "langage réseau" je suppose que ça pourrait donner un truc du genre:
 
On dispose d'un carte détaillant les vitesses de connection entre diverses machinnes (poids des arrêtes). Chaque machinne doit éxécuter un programme d'une certaine durée (compteur des sommets). Un programme ne peut tourner qu'en la présence d'un blop.
 
=> Quel est le nombre minimal de machines (et quelle sont-elles) où l'on doit lancer manuellement un blop afin que toutes les machines du réseau aient exécuté leur programme endéans un temps t, sachant qu'une fois arrivé sur une machine M, un blop peut soit s'occuper d'exécuter le programme de la dite machine (si ce n'est déjà fait) et partir ensuite, soit directement partir à destination de toute machine connectée à M.
 
Bien entendu, il faut partir du principe qu'un blop ne peut être stocké sur une machine. => soit il bosse, soit il se casse.
 
 
Majca

tu as fait un calcul de complexite?
ton algo se comporte bien par rapport
a quoi?
 
LeGreg

Complexité ?
 
J'ose pas mdr
 
Sérieusement, non, je ne l'ai pas fait. Ca ne m'a pas traversé l'esprit. Je vais le faire.
 
La comparaison n'est pas rigoureuse du tout. J'ai tout simplement lancer mon programme sur un graphe de 8 sommets => réponse instantanée.
Ensuite, un bactrack optimisé => 14 secondes.

moi la complexité ça me gave !!!!  
comprends pas qu'on "perde" autant de temps à ça
qqun pourrait m'expliquer l'idée et m'en convaincre pcq j'y arrive pas tout seul!

Wavyx a écrit a écrit : moi la complexité ça me gave !!!!   comprends pas qu'on "perde" autant de temps à ça qqun pourrait m'expliquer l'idée et m'en convaincre pcq j'y arrive pas tout seul!

 
Rah ! Démon de l'obscurantisme ... vade retro satanas !!!

Bon ben... Je ne connais pas la méthode exacte pour calculer une complexité. J'ai donc fait comme je m'en souviens plus ou moins
 
J'ai fais un rapide calcul qui donne ceci. Soit S le nombre de sommets, A la somme des arrêtes et T le temps maximal authorisé pour accomplire la tache.
 
Pour chaque tentative de débarquement, le programme à une complexité de O (T.A.S²) dans le pire des cas.
 
Pour le momment, je teste toute les combinaisons possible de débarquement de manière linéraire. C'est à dire que je commence par essayer les débarquements sur un seul sommet. Si aucune solution n'est trouvée, je passe aux combinaisons de deux sommets, etc...
Je compte remplacer celà par une recherche dichotomique, c'est-à-dire commencer par les combinaisons de S/2 débarquements. Si une solution est trouvée, on passe aux combinaisons de S/4 débarquements. Si non, on passe aux caombinaisons de (S-S/2)/2 débarquements, etc...
Ca devrait mieux équilibrer le temps de réponse du programme et non avoir une réponse très rapide en cas d'un seul débarquement nécessaire et une réponse très lente en cas de S-1 débarquements nécessaires
 
 
A noter le fait que le poids des arrêtes, le temps T et les compteurs doivent tous être à la même échelle. J'entends par là que si le temps est exprimé en seconde et qu'une arrête a un poids de 5, on parcourra cette arrête en 5 secondes. De même, un compteur à 4 sera réduit à 0 après 4 secondes.
 
 
Majca
 
 
ps:  cette complexité est sujet à des changements étant donné que je dois encore débrouissaler le programme.

Wavyx a écrit a écrit : moi la complexité ça me gave !!!!   comprends pas qu'on "perde" autant de temps à ça qqun pourrait m'expliquer l'idée et m'en convaincre pcq j'y arrive pas tout seul!

Est-ce que le mot "Optimisation" a une quelconque signification pour toi?

Faudrait quand même formaliser un peu mieux le pb.
Essayer de le généraliser en éliminant les hypothèses inutiles.
Etudier les cas limites qui recoupent d'autres pb pour lesquels on connaît des algos.
Avoir une idée des caractéristiques de la solution trouvée par l'algo par rapport aux autres solutions possibles.

 
 
Quels hypothèses sont selon toi inutiles ?
 
Cas limites recoupant d'autres problème connus, je ne vois pas... Mais bon, je suis loin de tous les connaîtres => si tu en connais...
 
Ton dernier point, je ne le comprends pas bien. Tu veux dire d'expliciter plus clairement ce qu'apporte de plus cet algo ?
Si oui ben... vitesse d'exécution

Je sais pas.  
J'ai pas compris l'énoncé.
Une troupe met combien de temps à conquérir une ville quand je la drope dessus.
Chaque morceau d'une troupe splitée à le même pouvoir offensif que la troupe initiale ?

Pour un cas donné, il y a plusieurs solutions non ?
En quoi celle trouvée par l'algo se distingue-t-elle des autres ?

 
 
Tout est à une même échelle. Si l'unité de temps est la seconde, un ville avec un poids de 5 sera détruite après 5 sec d'occupation par une troupe. De même, une arrête avec un poids de 7 sera parcourue en 7 seconde.
 
 

 
oui.
 
 

 
 
Pour un cas donné, plusieurs solutions peuvent effectivement être apportée. Ce que l'on désire, c'est connaître le nombre minimum de débarquements nécessaires.
=> si la réponse est 2, il se pourrait que débarquer sur le couple (A,B) ou (A,F) fonctionne. Donc, deux solutions.
Mon programme t'en fournira une. Laquelle n'a pas d'importance étant donné que de toute façon, on sait que les deux sont dans les temps.
 
Ce qui est certain par contre, c'est que le minimum de débarquements nécessaires est 2.
 
 
 
Majca

 
oui mais ya d'autres méthodes que la complexité.
et puis c plutôt "intuitif" que 4 boucles prennent plus de temps qu'une pour parcourir un vecteur. non ce que je peux pas capter c'est le temps qu'on passe à essayer de trouver une complexité X pour une méthode (backtracking) ou autre. pcq même en connaissant ta complexité O(n²logn) mettons, tu fais quoi après? t'essaye d'écrire des pré et des posts avec un complex maximum???? je crois pas non!
ok faut avoir une idée du temps d'exécution mais la complexité exacte elle sert à quoi?

Ca y est, j'ai modifié le code de manière à utilisé la dichotomie comme décrit ci-dessus.
 
A présent, je vais créer une grosse carte afin de voir ce que ça donne.
 
 
Avis à ceux qui ont du temps à predre !  Creez des cartes ! mdr
 
Au cas où certain n'aurait vraiment rien d'autre à faire, voici la structure des fichiers utilisés par le programme. Cette structure est loin d'être la meilleure manière de faire, mais c'est ce qui avait été donné dans l'énoncé du problème. Etant donné que ça ne change absolument rien à l'algo, on s'en fout
 
 
exemple de fichier:  
 
8    (nombre de sommets)
5    (temps max)
 
1    (sommet n°1)
2    (compteur du sommet)
2 5  (arc allant vers 2 de poids 5)
5 1  (arc allant vers 5 de poids 1)
6 3  (...)
 
2
2
1 5
3 4
5 3
6 3
7 1
 
3
3
2 4
4 2
6 2
7 3
8 2
 
4
1
3 2
7 2
8 3
 
5
2
1 1
2 3
6 1
 
6
3
1 3
2 3
3 2
5 1
7 2
 
7
1
2 1
3 3
4 2
6 2
8 4
 
8
2
3 1
4 3
 
 
 
 
Majca

 
L'exemple des boucles est débile. Ce qui compte c'est de ppouvoir comparer des algo DIFFERENTS pour voir le quel est le plus efficace. L'optimisation, ce n'est pas passer de i++ à ++i dans une boucle, ca c'est du chippotage qui varie selon les besoins et le comilateur.
Quand tu as 2 algos, et que tu dois traiter avec des données qui se chiffrent en million, tu est bien content de savoir lequel mettra 2 jours et lequel 1 semaine. La complexité, ca sert à ca.

ok mais quand t'écris ton algo ben tu t'arranges pour pas faire des trucs stupides qui prennent 3 fois le temps normal.
quand c qqch qu'on te fournit soit mais d'habitude on évite de fournir des algo dégueux qui sont hyper complexes.
ce que je voudrais c'est vraiment trouver une utilité directe à mon niveau qui m'incite à calculer les complexités de mes méthodes.
perso quand je me pose ce genre de questions j'ai jamais le courage de décomposer et de faire le calcul rigoureux avec les règles de O() et ça se termine en " cb de boucle imbriqués?" ou un truc du genre. et quand c'est récursif ça me tente encore moins!
oui je suis fainéant  

tout simplement parce que dans la vraie vie on  
ne te mache pas le travail, tu bosses
sur des problemes ouverts
et il ne suffit pas d'ouvrir un bouquin
pour avoir la solution.
 
LeGreg

Hey Majca ils sont plus rapide que  
la<-----cliquez ici?
 
n est pas ?
 
@->--

 
 
oui, en effet
 
Au début, je pensais ne le poster que sur le forum que tu indiques, me disant qu'il était plus spécialisé, donc plus rapide, que les gens seraient plus intéressés, etc...
 
En définitive, rien de tel que le bon vieux forum hfr
 
 
Pour en revenir au sujet principal, j'ai créé un graphe à 20 sommets. J'obtiens la réponse en 0.5 seconde. Je suis content
 
Pour ce qui est de la complexité, je tenterai de la calculer de manière regoureuse quand j'en aurai le temps. Ce qu'il y a, c'est que c'est loin dans ma tête... et que je ne sais plus où j'ai bien pu mettre mes notes à ce sujet.
Une chose est cependant certainne, ça va viiiite
 
 
Majca
 
 
edit: pour les mauvaises langues, j'ai pris un cas extrèmes de graphe. => 20 sommets, mais la solution est 1 débarquement.
Je vais tenter d'en créer un autre dont la solution serait 20 débarquement afin de bien tester les cas limites.

on peut avoir ton algorithme? ca peut toujours servir.

Non mais t'y fou ?
 
Sérieusement, je suis encore en train de le travailler. De plus, avant de le filer, j'aimerais savoir s'il a une quelconque utilité... qui sait...(c'est là le but de ce post mdr)

fais-en une these?
 
LeGreg

Une thèse ?
 
A la base, il s'agit d'un projet que j'ai du faire dans le cadre d'un cours d'algorithmique.
Seul hic, j' au eu une bonne cote non pas parce que la méthode à été jugée bonne mais parce que le correcteur a pu constater l'efficacité du programme bien qu'il n'ai rien compri à mon rapport... mdr
 
=> mon post (eh oui, encore )
Ce que j'en espérais (et continue d'en espérer), c'est que quelqu'un me dise "ça ne sert à rien parce que..." ou "ça peut servir pour..."
 
S'il s'avèrerait que j'ai fais un algo qui fonctionne impec pour un problème mais que ce problème, tout le monde s'en fou, ben... poubelle
S'il savérerait par contre que j'ai fais quelque chose d'intéressant, alors là oui, j'en ferais quelque chose.
 
 
 
Majca
 
 
edit:  Pour resumé la situation. Pouvoir résoudre un tel problème (cf plus haut) de manière efficace est-il intéressant ??
edit2: efficace efficace, tout est relatif hein Disons qu'à ma connaisance, c'est le plus rapide. Ca ne change rien au fait que pour un graphe à 100 sommets... (quelqu'un se lance pour en faire un fichier que je teste ?? mdr)

je ne vais pas te dire que ca ne sert a rien puisque ca
resout au moins ton probleme.
 
La difficulté de la question telle que tu la poses c'est que tu fais l'inverse de ce qu'il faudrait faire.
Tu dis: "j'ai une solution est-ce que vous n'auriez pas un probleme auquel cela pourrait s'appliquer?"
Or le plus souvent, on a un probleme particulier ou une classe de probleme dont on a montré qu'ils étaient équivalents et l'on propose une solution spécifique à ce problème, eventuellement en montrant que l'on est proche de la limite théorique en terme d'instructions, ou que la solution proposée marche bien dans certains cas particuliers etc..
 
Conclusion: quel est le travail du programmeur qui doit resoudre un probleme 'ouvert', c'est a dire dont on ne lui a pas donné la solution? Et bien tout simplement, il doit essayer de ramener ce probleme complexe à quelque chose de connu, quelque chose qui a déjà été traité auparavant par lui-meme ou par un théoricien, cela passe souvent par le découpage du probleme complexe en sous-problèmes simples.
 
Evidemment comme le temps lui est compté, il n'arrivera pas a la solution optimale pour son probleme particulier mais il arrivera a quelque chose d'acceptable (s'il est bon) ou montrera qu'on ne peut pas resoudre ce probleme en temps acceptable (s'il est tres bon) grace au calcul de complexite.
et si le probleme est trivial ou moyennement complexe, il
se fichera de calculer la complexite parce que de toute facon
il sera paye pareil à la fin du mois
 
LeGreg

 
Le fait est qu'ici, j'ai effectivement résolu un problème posé.
Cependant, étant donné que je pense avoir trouvé un très bonne méthode, je me demandais s'il n'y aurait pas moyen de l'appliquer à des cas plus courants ou plutôt devrais-je dire plus utiles.
 
Pour le moment, il ne servirait qu'à d'éventuels E.T. ce qui limite "un peu" son utilité

Bon ben... pour la complexité du bazard, ça attendra. Je n'ai pas le temps de la calculer, d'autant plus qu'elle n'est pas facile facile...
 
 
ciao ciao
 
Majca
 
 
ps: au fait, merci pour les réponses obtenues jusqu'à présent

j'sais pas ou t'en est ..mais moi j'aimme bien ce genre de petit defis !!
j'ai calmé ma prof la dernière fois avec un système de parcours de tableau !!
 
bref tout ca pour dire : j'comprend pas ton problème !
c aps clair !

problème => l'énoncé que j'ai donné ?
ou
problème => ma question ?