TP — Séance 3 — L’IA qui cherche

Le réseau du Sud et l’emploi du temps des examens

TP de la séance 3 d’Introduction à l’intelligence artificielle : formuler un problème, explorer un espace d’états.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Implémenter BFS, la recherche à coût uniforme et A* sur un réseau routier, compter les nœuds qu’ils sortent, comparer des heuristiques, puis résoudre un problème d’emploi du temps par hill climbing et par recuit simulé. Durée : une séance de TP (2 à 3 heures).

Mise en place

Le code de départ est le notebook TP_S03_depart.ipynb, dans l’archive TP_S03_code_depart.zip. Il demande Python 3.10 ou plus récent et matplotlib.

unzip TP_S03_code_depart.zip
cd code_depart
jupyter lab TP_S03_depart.ipynb

Les cellules marquées # A COMPLETER contiennent des ... à remplacer par le code demandé ; la cellule qui suit chacune affiche les résultats que la fiche interroge. Les fonctions reprennent celles du cours (Noeud, chemin, bfs, meilleur_dabord, hill_climbing, recuit), avec un seul ajout : la liste sortis des nœuds sortis de la frontière, dans l’ordre, but compris. À rendre : le notebook exécuté, avec les réponses aux questions dans des cellules de texte.

Étape 0 : le réseau du Sud

Le réseau compte quatorze villes du Sud du Sénégal, avec Farafenni, en Gambie, sur la route transgambienne. Les distances sont des distances routières arrondies, en kilomètres ; les villes sont placées selon leurs coordonnées GPS.

  1. Observer. Exécuter les quatre premières cellules. Combien de villes et de routes le réseau compte-t-il ? Que rend voisins("Kaolack") ?
  2. Expliquer. Pourquoi chaque route est-elle rangée deux fois dans G ? Quel serait l’effet de n’en ranger qu’un sens ?

Étape 1 : la recherche en largeur

Un enseignant de Kaffrine rejoint son nouveau lycée à Kolda.

  1. Compléter bfs : retirer le nœud le plus ancien, puis ajouter en bout de file chaque voisine non atteinte.
  2. Observer. Donner le chemin rendu de Kaffrine à Kolda, sa longueur en kilomètres, son nombre de routes, puis le nombre et l’ordre des nœuds sortis.
  3. Expliquer. Ce chemin est-il le plus court en kilomètres ? Qu’est-ce que BFS garantit ?
  4. Modifier. Compléter bfs_generation, qui teste le but dès qu’un fils est généré. Donner le chemin rendu et le nombre de nœuds sortis ; expliquer la différence avec (b).

Étape 2 : la recherche à coût uniforme

  1. Compléter la boucle intérieure de meilleur_dabord : le coût g du chemin par n, l’écart d’une voisine déjà connue à un coût au moins aussi bon, la mise à jour de meilleur et l’insertion dans le tas avec la priorité f(g, v).
  2. Observer. Avec f = lambda g, v: g, donner le chemin de Kaffrine à Kolda, sa longueur et le nombre de nœuds sortis.
  3. Expliquer. Pourquoi UCS sort-elle Kaolack, Fatick et Sokone, alors qu’elles s’éloignent de Kolda ? Pourquoi sort-elle moins de nœuds que BFS sur ce trajet ?

Étape 3 : l’heuristique à vol d’oiseau

  1. Compléter haversine (formule du cours). Donner la distance à vol d’oiseau de Kaffrine à Kolda et le dictionnaire H des distances arrondies à Kolda.
  2. Observer. La fonction couts_vers, fournie, calcule le vrai coût restant \(h^*\). Compléter la cellule qui calcule la marge \(h^*-h\) en chaque ville autre que le but ; donner la plus petite marge et la ville où elle est atteinte.
  3. Observer. Compléter la cellule qui calcule, pour chaque route, la marge \(c-|h(a)-h(b)|\). L’heuristique est-elle consistante ? Quelle route a la plus petite marge ?
  4. Expliquer. Pourquoi la distance à vol d’oiseau est-elle admissible ? Pourquoi l’arrondi au kilomètre aurait-il pu casser la consistance, et pourquoi ne l’a-t-il pas fait ici ?

Étape 4 : A*, la recherche gloutonne et le poids de l’heuristique

  1. Observer. Exécuter la cellule qui compare UCS, la recherche gloutonne et A*. Rassembler dans un tableau le chemin, sa longueur et le nombre de nœuds sortis.
  2. Expliquer. Quelles villes UCS sort-elle qu’A* ne sort pas ? Le justifier par \(f=g^*+h\) et \(C^*\).
  3. Modifier. Compléter la cellule qui exécute A* avec la priorité \(g+w\,h\) pour \(w=0\), 1, 2, 4, 5 et 10. Pour quelles valeurs de \(w\) le chemin reste-t-il optimal ? Comment varie le nombre de nœuds sortis ? Vers quel algorithme la recherche tend-elle quand \(w\) grandit ?

Étape 5 : mesures sur toutes les paires de villes

  1. Compléter la boucle qui, pour chacune des \(14\times13\) paires (départ, but), exécute UCS, A* (avec la distance à vol d’oiseau jusqu’au but) et A* pondéré (\(w=2\)), et vérifie qu’A* rend le même coût qu’UCS.
  2. Observer. Donner le nombre moyen de nœuds sortis par chacun, le nombre de paires où A* pondéré reste optimal, et son plus grand excès de coût, en pourcentage.
  3. Expliquer. Que gagne-t-on, et que perd-on, avec \(w=2\) ?

Étape 6 : l’emploi du temps des examens

Douze unités d’enseignement (UE) de L2 doivent passer leur examen dans l’un de quatre créneaux. Deux UE en conflit ont des étudiants en commun et ne doivent pas tomber dans le même créneau ; la liste CONFLITS en donne les 25 paires. Un état affecte un créneau à chaque UE ; son coût est le nombre de paires en conflit placées dans un même créneau.

  1. Compléter cout et voisins_e (un voisin change le créneau d’une seule UE). Donner le coût de l’état où toutes les UE sont dans le créneau 0, et son nombre de voisins.
  2. Compléter hill_climbing, sur le modèle du cours. Donner le résultat depuis l’état précédent.
  3. Observer. Sur 300 départs tirés au hasard (graine 221), donner le nombre de succès, le nombre moyen de pas des succès et le coût moyen à l’arrêt.
  4. Observer. Avec des redémarrages aléatoires, donner le nombre moyen et le nombre maximal de lancers. Comparer à l’inverse du taux de succès de (c).
  5. Compléter la règle d’acceptation de recuit. Sur les mêmes 300 départs, donner le nombre de succès et le nombre moyen de pas.
  6. Modifier. Comparer \(\alpha=0{,}9\), \(0{,}99\), \(0{,}995\) et \(0{,}999\) : succès et nombre moyen de pas. Expliquer l’effet de \(\alpha\).
  7. Observer. Afficher un emploi du temps sans conflit, créneau par créneau.

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet