TIPE Construction de graphe

[fakbill]

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

[Daner]

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.

[matmeca_mcf1]

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.

[U46406]

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é ?)

[fakbill]

matmeca_mcf1 : Oui c'est un problème marrant que d'obtenir des trajectoires un peu réalistes.

[zede]

Peut-être ajouter une notion simple de courant ?

[fakbill]

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