Aperçu des sections

  • Déplacements dans le plan.

    Dans cette partie, nous allons nous intéresser au fameux problème du voyageur de commerce. On considère un plan avec un nuage de points, définis par leurs coordonnées. L'objectif du voyageur de commerce est de visiter tous les points du parcours et de revenir au point de départ, en parcourant la plus petite distance.


    • Icône Dossier
      Ressources disponibles Dossier

      Quelques fichiers utiles:

      • Point.java: une interface de point.
        • laisse la possibilité de marquer un point
        • notez la méthode distanceTo(T otherPoint) qui vous renvoie la distance Euclidienne.
      • Point2D.java: l'implémentation de point utilisée.
      • SalesmanTour.java: une interface vous permettant de stocker un parcours des points
        • Le tour est simplement stocké comme une liste des points dans l'ordre de visite.
        • La méthode getWeight calcule le poids du tour
      • TourDrawing.java: Une interface permettant de dessiner dans une même fenêtre plusieurs tours.
      • StdDraw.java: une interface pour simplifier l'usage de Swing. (déjà utilisée pour la tortue en S3)
      • SalesmanTest.java: une fonction principale qui crée un tour en prenant les points dans l'ordre, et le dessine.
    • Icône Devoir
      1-Algorithmes glouton et brute-force Devoir
    • Icône Devoir
      2-Approximation Devoir
      Non disponible à moins que : L’activité 1-Algorithmes glouton et brute-force soit marquée comme achevée
    • Icône Devoir
      3-Recherche locale Devoir
      Non disponible à moins que : L’activité 2-Approximation soit marquée comme achevée
    • Icône Devoir
      4-Approximation améliorée Devoir
      Non disponible à moins que : L’activité 3-Recherche locale soit marquée comme achevée