Activité.

par **vincentroumezy** » 07 Juil 2012, 10:22

Salut tout le monde.
J'ai l'impression que ce forum s'endort un peu, des idées pour le relancer ?

par **Micki28** » 07 Juil 2012, 10:34

Un petit tournoi d'échecs? :D

par **vincentroumezy** » 07 Juil 2012, 12:14

Si tu veux, mais je vois pas le rapport avec les maths :zen: .

par **Luc** » 07 Juil 2012, 19:12

vincentroumezy a écrit:Salut tout le monde.
J'ai l'impression que ce forum s'endort un peu, des idées pour le relancer ?

c'est les vacances scolaires... et peu de monde a répondu à mon post sur les oraux de l'agreg, pourtant il y a des notions du niveau de maths spé hein :lol3:

Luc

par **vincentroumezy** » 07 Juil 2012, 19:38

Je ne suis qu'en sup :lol3:

par **Zweig** » 07 Juil 2012, 19:42

vincentroumezy a écrit:Si tu veux, mais je vois pas le rapport avec les maths :zen: .

Et pourtant, la théorie des jeux est bien une branche des mathématiques ayant des applications profondes :lol3:

par **vincentroumezy** » 07 Juil 2012, 19:44

Vu comme ça en effet....
Il y avait même eu un exo de "topologie" une fois, avec un échiquier (chemins sur un échiquier, je crois).

par **Zweig** » 07 Juil 2012, 19:46

Sûrement ... Y a le jeu de l'ange et du démon de pas mal aussi (bon c'pas vraiment un jeu d'échec mais plutôt une variante du jeu de dames on va dire)

par **vincentroumezy** » 07 Juil 2012, 19:47

Je connais pas, je vais me renseigner.

par **Zweig** » 07 Juil 2012, 19:48

Enfin, c'est plus un jeu théorique :lol3:

par **Dlzlogic** » 07 Juil 2012, 20:28

Bon, je m'introduis dans votre discussion, mais je ne suis pas de votre niveau.
On a parlé de topologie.
Je suis depuis 2 ou trois jours sur un problème pas simple.
Soit un graphe non orienté. On cherche TOUS les trajets d'un noeud à un autre.
C'est peut-être pas le meilleure solution à adopter pour un problème que je connais pas, mais ce sont les hypothèses.
Voilà. Si ça vous intéresse.
Quand j'aurai fini, j'ai un défi à proposer, mais pour être honnête il faut que je le résolve d'abord.
Bonne soirée.

par **vincentroumezy** » 08 Juil 2012, 18:15

Tu peux détailler un peu s'il te plaît ?

par **Dlzlogic** » 08 Juil 2012, 19:09

vincentroumezy a écrit:Tu peux détailler un peu s'il te plaît ?

Oui, mais comme certains détails m'ont été donné par MP, je serai discrets sur ces points.
La base de départ (physique et intellectuelle) est un graphe non orienté. Je ne sais ni d'où il vient, ni à quoi il sert, mais l'hypothèse est de déterminer tous les chemins possibles d'un noeud à un autre.
Le seul moyen de montrer que ce n'est pas forcément la bonne solution est de commencer par le faire, puis de comparer avec une autre méthode.
J'ai déjà une organisation de chemins. J'appelle chemin un arc de topologie, c'est à dire qu'il joint 2 noeuds et deux noeuds, s'ils sont joints, il n'y a qu'un chemin. Deux chemins ne se coupent pas. Pour illustrer la façon dont ça se passe, j'ai pris comme base les limites de départements.
Les extrémités de chemins sont les noeuds. Dans ma structure de noeud, j'ai le matricule du point et la liste des noeuds directement reliés.

Donc étant donné deux noeuds, je cherche à déterminer TOUS les chemins possibles, sans se recouper.
Le principe de base est une fonction récurrente, mais pour l'instant, ça marche pas encore.

Pae contre, pour trouver le "meilleur" itinéraire entre un noeud et un point d'un chemin, c'est d'une rapidité déconcertante, mais bien sûr tout le monde a utilisé ce genre de truc.

C'est avec ce type d'organisation qu'on peut trouver les 4 couleurs, mais c'est une autre histoire.

par **vincentroumezy** » 08 Juil 2012, 19:22

On peut voir ton graphe ?

par **Dlzlogic** » 08 Juil 2012, 19:47

vincentroumezy a écrit:On peut voir ton graphe ?

Oui, mais sous quelle forme ?
En fait, ce n'est une liste de noeuds sous cette forme
typedef struct NOEUD
{
Point3D *point;
float parcouru;
NOEUD *precedent;
TList *Fils;
}TabNOEUD;
typedef TabNOEUD* ptrNoeud;

Le type Point3D définit le point (X,Y,matricule)
Parcouru ne sert pas ici
Précédent n'est pas utilisé non plus
Ces deux valeurs sont utilisées dans l'étude du plus court trajet.
TListe est une liste de pointeurs sur les noeuds fils.
On connait le Depart et la Fin.
En fait étant donné l'application réelle dont il s'agit, je n'ai aucune idée si les noeuds représentent physiquement des points (X,Y).
C'est du C++.
Dans le cas présent, normalement il n'y a que 3 fils, mais rien n'interdit qu'il y en ait plus. De toute façon, c'est pas un problème.

par **Joker62** » 09 Juil 2012, 19:47

Ce qui est compliqué avec les piles c'est qu'il faut en parcourir beaucoup...

Pour les graphes non orientés, on utilise la matrice d'adjacence.

Le terme (i,j) de A^n correspond au nombre de chemin de longueur n reliant i à j

On calcule donc les puissances successives de A tant que le terme de rang (i,j) est différent de 0 (pour qu'il existe au moins un chemin)

En plus, comme on est en non-orienté, la matrice est diagonalisable et les calcules se font hypra-vite.

par **fatal_error** » 09 Juil 2012, 19:49

subsiste les problèmes de cycle qui viennent ajouter des chemins qui ne nous intéressent pas.

le sujet initial est ici

par **Dlzlogic** » 09 Juil 2012, 20:38

fatal_error a écrit:subsiste les problèmes de cycle qui viennent ajouter des chemins qui ne nous intéressent pas.

le sujet initial est ici

Oui, tout cela est vrai, mais les hypothèses sont très précise, l'organisation est un graphe non orienté, l'utilisation de tableau d'adjacence est exclu, le but recherché est d'améliorer la rapidité.
Dans un premier temps, j'ai essayé de résoudre le problème selon les hypothèses proposées, j'avoue que je ne suis pas encore arrivé, probablement des problèmes de détail, l'optimisation viendra après.
De toute façon on ne peut parler de comparatif que si on a une solution qui tourne, ce qui n'est pas le cas pour moi, pour l'instant.

Activité.

Activité.

Qui est en ligne