TIPE Construction de graphe

Une petite question sur votre TIPE...

Messages : 11326

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » 08 oct. 2019 21:19

La route? En quoi est elle unique??
Tu veux une route qui reste sur l'eau? C'est le seul critère?
Tiens c'est marrant comme question...les algo auquels je pense donnent des routes rigolotes :)
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 9

Enregistré le : 20 avr. 2019 10:26

Classe : MPS1

Re: TIPE Construction de graphe

Message par Daner » 09 oct. 2019 18:16

Elle n'est pas forcement unique. En créant plusieurs routes, pour les differents ports entre eux il y aura des points intermédiaires. le but est ensuite de vérifier si certain de ces points peuvent se relier entre eux et si il en existe deux qui sont proches l'un de l'autre des les remplacer par un seul pour réduire le nombre de point et connexion totale.
Modifié en dernier par Daner le 09 oct. 2019 18:43, modifié 1 fois.

Messages : 1764

Enregistré le : 13 févr. 2018 09:22

Re: TIPE Construction de graphe

Message par matmeca_mcf1 » 09 oct. 2019 18:40

Ce n'est pas une construction de graphe mais un problème d'optimisation. La fonction de coût ici est la distance. Avec une telle fonction de coût, les trajectoires optimales vont par morceaux soit suivre des géodésiques de la sphère soit suivre le trait de côte. Ce n'est pas très réaliste, il faudrait probablement imposer un rayon de courbure minimale aux trajectoires d'un navire.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'Enseirb-Matmeca (Bordeaux INP)
Les opinions exprimées ci-dessus sont miennes et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

Messages : 10486

Enregistré le : 27 juil. 2016 19:38

Classe : shadow CCO nobo CMT

Re: TIPE Construction de graphe

Message par U46406 » 09 oct. 2019 19:35

Daner a écrit :
09 oct. 2019 18:16
s'il en existe deux qui sont proches l'un de l'autre, les remplacer par un seul pour réduire le nombre de points et connexions totales.
Certes, mais est-ce que ça fera un sujet de TIPE ?
(Et cette opération de simplification a-t-elle un intérêt pratique dans la réalité ?)
« Occupez-vous d’abord des choses qui sont à portée de main. Rangez votre chambre avant de sauver le monde. Ensuite, sauvez le monde. » (Ron Padgett, dans Comment devenir parfait) :mrgreen:

Messages : 11326

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » 09 oct. 2019 22:17

matmeca_mcf1 : Oui c'est un problème marrant que d'obtenir des trajectoires un peu réalistes.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 656

Enregistré le : 12 août 2018 17:03

Re: TIPE Construction de graphe

Message par zede » 10 oct. 2019 06:19

Peut-être ajouter une notion simple de courant ?

Messages : 11326

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » 10 oct. 2019 11:58

Non mais même sans courant....
Je te donne une image d'un planisphère avec des pixels 0/1 - mer/terre.
Quel algo pour tracer une route entre deux ports qui minimise la distance? sans meme parler de courant?
Déjà rien que ça c'est un pb fun (et tout algo plantera dans un cas particulier vu que c'est tout sauf convexe...il faudra mettre des heuristiques).
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Répondre