Catch multiple pieces of cheese... more efficiently

Présentation & objectifs

Lors de la session précédente, vous avez découvert que capturer toutes les pièces de fromage en un nombre minimal d’actions est un problème très difficile à résoudre. Une approche alternative consiste à utiliser des heuristiques, c’est-à-dire des algorithmes approximatifs qui retourneront une solution généralement non optimale, mais suffisamment proche de l’optimal pour être acceptable, et qui peuvent être calculés en un temps réduit. Une heuristique très classique est l’algorithme “glouton” (greedy). Son objectif est d’approximer la solution globale d’un problème par une série de solutions localement optimales.

Les notions ci-dessus sont couvertes par quelques articles que vous devez étudier avant le cours. Dans l’activité pratique, vous devrez approximer une solution au problème du voyageur de commerce (TSP) basée sur une recherche gloutonne.

Avant le cours

Prérequis techniques

Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :

• Veuillez apporter votre propre ordinateur.
• Assurez-vous d’avoir une connexion réseau fonctionnelle.

Acquisition des connaissances préalables

Pour pouvoir commencer efficacement l’activité pratique, nous avons introduit certains concepts nécessaires à la fin de la session précédente. Voici les diapositives utilisées en cours :

• Diapositives de la session.

Ces diapositives couvrent uniquement les éléments principaux du cours, et beaucoup plus de détails sont donnés dans les articles associés. Ainsi, vous devez étudier les articles suivants chez vous avant la session :

• Heuristics.
• Greedy algorithms.
• Approximate solutions.

Vous pouvez vérifier votre compréhension de ces articles ici :

• Quiz d’auto-évaluation.

Pendant le cours

Quiz

Au tout début de la session, nous commençons par un quiz Wooclap évalué pour vérifier votre compréhension des articles que vous deviez étudier. Le lien sera donné par l’enseignant au début du cours. Assurez-vous d’être à l’heure !

Attribution des rôles

Lors de l’évaluation précédente, vous avez dû sélectionner un rôle, correspondant à votre responsabilité dans le livrable évalué. Cette fois, vous devez prendre un rôle différent. Utilisez le tableau suivant pour trouver le vôtre :

Comme décrit à la fin de cette page, vous devrez téléverser une archive, qui inclut un fichier README.md. Dans ce fichier, vous devrez indiquer qui est responsable de quoi.

Activité pratique

Le cours est dédié à une activité pratique. Une fois que vous avez terminé toutes les étapes ci-dessus, cliquez sur le lien ci-dessous pour commencer :

• Activité pratique.

Après le cours

Compléter la session en cours

Cette session est évaluée. La modalité d’évaluation est décrite sur la page principale du projet. Avant la prochaine session, vous devez donc :

• Revoir le contenu des articles ci-dessus.

• Compléter les parties non optionnelles de l’activité pratique.

• Créer une archive nommée student1_student2_student3.zip, où student1, student2 et student3 sont les noms de famille des membres de votre groupe. Cette archive doit être structurée comme suit :

  student1_student2_student3.zip
  |
  |_ games
  |  |_ # Put your game scripts here
  |
  |_ players
  |  |_ # Put your players here
  |
  |_ tests
  |  |_ # Put your unit tests here
  |
  |_ utils
  |  |_ # Put your additional codes here (if any)
  |
  |_ data
  |  |_ # Put your other files here (if any)
  |
  |_ README.md

  Le fichier README.md doit être un fichier texte formaté en Markdown. Téléchargez ce fichier pour l’utiliser comme base, et remplissez-le là où c’est demandé (remplacez tout ce qui est dans <...>).

• L’étudiant responsable du code doit téléverser cette archive sur Moodle avant le début de la session 6.

Préparer la prochaine session

• Consultez la section “Avant le cours” de la prochaine session, et assurez-vous de faire tout ce qui est nécessaire pour la préparer.
• La prochaine session commencera par un quiz évalué pour vérifier que vous avez compris les articles.