TIPE Construction de graphe

Une petite question sur votre TIPE...

Modérateurs : Marc Ménétrier, Th. Zabulon

Daner
Messages : 9
Enregistré le : sam. avr. 20, 2019 10:26 am
Classe : MPS1

TIPE Construction de graphe

Message par Daner » lun. oct. 07, 2019 7:39 pm

Bonjour,
Voila mon sujet : Recherche de graphe adaptée à la navigation maritime.
Le but serait à partir de coordonnées de ports (longitude et latitude) de fournis un graphe représentant les chemins entre les ports en y ajoutant des points intermédiaires.

Le principe : on trace l'arc de cercle reliant les deux ports sur la terre, puis on regarde si le point du milieu de l'arc de cercle est bien dans l'océan. Si ce n'est pas le cas on le décale un peu a droite et un peu à gauche de l'arc de cercle puis on vérifie si ces points sont bien dans l'océan. On répète l’opération sur les demi arc délimité par le point milieu et les extrémités. On réitère ensuite l'opération, en notant uniquement les points que l'on a déplacé.

Pour déterminer si le point considérer est dans l'eau ou pas, j'ai le module Basemap avec la fonction is_land qui renvoie True / False.
Les coordonnées des ports seront entrées manuellement.

Tout d'abord mon prof me demande de la bibliographie, j'en ai regardé sur les graphe, cependant je ne pense pas que ce soit pertinent, ceux ci se concentre sur le parcours des graphes. Or moi je dois créer le graphe et je n'ai pas vraiment trouvé de ressource à ce sujet.
J'ai donc tout d'abord du mal à trouver de la documentation, je ne sais pas trop dans quel domaine chercher.


Merci pour ceux qui prendrons le temps de me lire.
Je me sens perdu dans le tipe, je ne sais pas si ce que je fais est pertinent.

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » lun. oct. 07, 2019 7:42 pm

Tu as prévu de gérer les récifs sous-marins (hauts-fonds) qui peuvent faire échouer ou couler le navire ?

Et par souci de simplification, le logiciel ne tient pas compte des cyclones ni des tempêtes ?
« 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:

Daner
Messages : 9
Enregistré le : sam. avr. 20, 2019 10:26 am
Classe : MPS1

Re: TIPE Construction de graphe

Message par Daner » lun. oct. 07, 2019 9:06 pm

non je ne gère pas les récifs sous marin de même que les trop petites iles. Je ne tiens pas aussi compte des tempêtes.

Avatar du membre
fakbill
Messages : 11270
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » mar. oct. 08, 2019 11:41 am

Je crois qu'il y a une confusion.
Un graphe c'est un ensemble de sommets relies par des arêtes. C'est abstrait.
Je ne comprends pas ce que tu cherches à faire avec tes arcs et tes points qui sont dans l'océan ou pas.. (façon polie de dire qu'un jury va raler+++)

Qu'est ce que tu as en entrée?
Qu'est ce que tu churches à calculer? optimiser exactement??
Les coordonnées des ports seront entrées manuellement.
On n'est plus dans les années 80. On s'en fout des "inputs". Tu écris un FONCTION qui prend ce qu'il faut en entrée et qui RETURN ce qu'il faut.
Si tu as N coordonnnés, tu les mets dans un fichier .txt et tu écris une fonction qui va lire tout ce fichier.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » mar. oct. 08, 2019 1:02 pm

Il cherche à établir le trajet pour aller d'un point à un autre, sans utiliser un graphe de chenaux pré-déterminés ou de routes maritimes...

Il veut créer des routes maritimes.
C'est intéressant d'un point de vue théorique, mais peu réaliste...

Par exemple quel chemin un navire chargé de soldats cubains et de matériel militaire allait-il d'un port donné de l'île de Cuba jusqu'au Mozambique ??
« 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:

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » mar. oct. 08, 2019 3:05 pm

Peut-être d'autres idées dans le Ocean Hackathon ?
https://www.campus-mondial-de-la-mer.fr ... 0-0-0.html
« 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:

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » mar. oct. 08, 2019 3:47 pm

Tu es maintenant en MP - MP option informatique ou s2i ? ou en PSI ?
- après tes difficultés l'année dernière en MPSI à trouver un sujet de TIPE : viewtopic.php?f=17&t=70278&p=957484#p958981

Ton sujet actuel me semble un peu trop simple, de créer un point (Phi, Lambda) par un programme...
« 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:

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Océan ?

Message par U46406 » mar. oct. 08, 2019 3:54 pm

Un sujet lié au thème Océan : simuler le naufrage du Titanic une fois que l'eau s'engouffre caisson par caisson par la brèche causée par l'iceberg fatal.

viewtopic.php?f=17&t=11673&p=130383#p130383
viewtopic.php?f=17&t=42375&p=530503#p530503
« 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:

Daner
Messages : 9
Enregistré le : sam. avr. 20, 2019 10:26 am
Classe : MPS1

Re: TIPE Construction de graphe

Message par Daner » mar. oct. 08, 2019 6:38 pm

U46406 a écrit :
mar. oct. 08, 2019 1:02 pm
Il cherche à établir le trajet pour aller d'un point à un autre, sans utiliser un graphe de chenaux pré-déterminés ou de routes maritimes...
C'est ça, je cherche à déterminer la route maritime entre deux ports.

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » mar. oct. 08, 2019 6:55 pm

Je te fais une remarque ou te pose une question mais par Message privé - pour ne pas casser la dynamique du forum.
« 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:

Avatar du membre
fakbill
Messages : 11270
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » mar. oct. 08, 2019 9:19 pm

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é.

Daner
Messages : 9
Enregistré le : sam. avr. 20, 2019 10:26 am
Classe : MPS1

Re: TIPE Construction de graphe

Message par Daner » mer. oct. 09, 2019 6:16 pm

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 mer. oct. 09, 2019 6:43 pm, modifié 1 fois.

matmeca_mcf1
Messages : 1536
Enregistré le : mar. févr. 13, 2018 10:22 am

Re: TIPE Construction de graphe

Message par matmeca_mcf1 » mer. oct. 09, 2019 6:40 pm

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.

Avatar du membre
U46406
Messages : 8853
Enregistré le : mer. juil. 27, 2016 7:38 pm
Classe : shadow CCO nobo CMT
Contact :

Re: TIPE Construction de graphe

Message par U46406 » mer. oct. 09, 2019 7:35 pm

Daner a écrit :
mer. oct. 09, 2019 6:16 pm
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:

Avatar du membre
fakbill
Messages : 11270
Enregistré le : mer. juil. 30, 2008 4:59 pm
Classe : Dr.-Ing

Re: TIPE Construction de graphe

Message par fakbill » mer. oct. 09, 2019 10:17 pm

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é.

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 4 invités