Description

Brian.Pulfer@unige.ch
Remarques:
Veuillez suivre attentivement les sp´ecifications de l’´enonc´e.
• R´eponses – Essayez d’ˆetre exhaustif dans vos r´eponses. Les r´eponses comme ”oui” et ”non” ne permettent pas d’´evaluer vos connaissances.
• Points extra – Le nombre maximum de points pouvant ˆetre marqu´es pour un TP est de 5, ce qui conduit `a une note de 6. Vous pouvez effectuer les exercices 2 et 3 pour obtenir des points suppl´ementaires. Marquer plus de 5 points est toujours arrondi `a la note 6.
• Trac´es – Mettez toujours des ´etiquettes d’axe et des titres pour les trac´es.
• Impl´ementation – Veuillez utiliser exactement les noms fournis pour les fonctions. Vous pouvez utiliser pytest avec le script de test donn´e pour v´erifier votre impl´ementation.
• Soumission
Merci de t´el´echarg´e vos devoirs sur moodle:
– NomPrenom.pdf avec votre rapport pour tout les exercices – tp5.py avec votre implementations
– Pas d’autres fichiers (.pyc, .ipynb, DS Store, pycache , …)
• Pour toute questions et remarques, merci d’utiliser le mail Brian.Pulfer@unige.ch.
1 Taquin (5 Points)
Dans le jeu du Taquin, on dispose d’une grille de 16 cases (4 × 4) dont 15 cases num´erot´ees et un trou, chaque case pouvant ˆetre couliss´ee si tant est qu’elle en ait la place, le but ´etant, `a partir d’un ´etat initial donn´e, de remettre la grille dans l’ordre de 1 `a 15 (voir Figure 1).

Figure 1: Example de jeu du Taquin
Nous avons vu en cours une description possible du probl`eme, ou` une 16`eme case fictive, la case vide, peut se d´eplacer dans au plus 4 directions `a chaque tour. Le but de cet exercice est d’´etudier une impl´ementation de strat´egie Branch-and-Bound pour la r´esolution du Taquin.
1.1 Fonction de couˆt
En cours, une fonction de couˆt ˆc(x) associ´ee `a l’´etat x a ´et´e propos´ee pour le jeu du Taquin :
cˆ(x) = h(x) + g(x) (1)
ou` h(x) est la profondeur de x dans l’arbre de recherche et g(x) le nombre de cases (hormis la
case vide) mal plac´ees.
• Quel est le rˆole de h(x) dans la fonction de couˆt? Et celui de g(x)? • A quel type de recherche correspond la fonction de couˆt (Equation 1)? Et dans le cas d’une fonction de couˆt ˆc(x) = h(x)?
• En se basant sur les crit`eres discut´es en cours concernant le propri´et´es de ˆc(x) (Equation 1) vis-`a-vis d’une fonction de couˆt id´eale c(x), montrez que si l’on fait une recherche Branch-andBound avec la fonction de couˆt d´efinie au point pr´ec´edent et que l’on trouve une solution, cette solution est optimale.
1.2 Impl´ementation
Impl´ementez en Python une m´ethode de r´esolution du Taquin en Branch-and-Bound, utilisant la fonction de couˆt ˆc(x) (Equation 1).
Notez que ce qui nous int´eresse ici n’est pas l’´etat final, puisque celui-ci est connu; la solution est le chemin, c’est-`a-dire la suite des directions prises par la case vide pour arriver `a cet ´etat-solution.
Impl´ementer la fonction de couˆt c_hat(board) ou` board est un E-node, node, ainsi que la fonction donnant le chemin solve_taquin(board) ou` board est la liste contenant l’´etat initial.
Le format de ce chemin doit ˆetre une liste ordonn´ee de chaˆınes de caract`eres pris dans l’ensemble
(“up”, “right”, “down”, “left”): en lisant de gauche `a droite cette liste, on obtient le chemin de l’´etat initial `a l’´etat solution.
Bien que solve_taquin doive fonctionner pour tout ´etat initial valide, on pourra au d´ebut prendre l’exemple donn´e en cours, avec l’´etat initial:
board = [
[1, 2, 3, 4],
[5, 6, 16, 8],
[9, 10, 7, 11],
[13, 14, 15, 12]
]
1
2
3
4
5
6
La solution correspondante est le chemin: [“down”, “right”, “down”].
1.3 Efficacit´e de l’algorithme
La fonction gen_disorder(board, n) d´esordonne un ´etat donn´e board (g´en´eralement l’´etat solution). Elle r´ealise n mouvements al´eatoires afin de g´en´erer en output un ´etat dont vous connaissez environ la distance `a l’´etat caract´eris´e par board. En effet, si gen_disorder prend soin de ne pas faire de cycles, alors on peut s’attendre `a ce que la longueur du chemin-solution soit en g´en´eral approximativement n, bien qu’inf´erieure parfois. Notez que le module random de Python permet de manipuler tr`es simplement l’al´eatoire.
Pour ´etudier l’efficacit´e de l’algorithme ou, plus pr´ecis´ement, de la fonction de couˆt utilis´ee, produisez un graphe du nombre de noeud k explor´es par l’algorithme par rapport au param`etre n utilis´e pour produire l’´etat initial avec la fonction gen_disorder. Incluez les graphiques produits dans votre rapport.
Faites ceci pour:
• Le cas ou` la fonction de couˆt est donn´ee par ˆc(x) = h(x), et pour n de 1 `a 6, en moyennant chaque valeur sur une cinquantaine d’it´erations au moins.
• Le cas de la fonction de couˆt (Equation 1), et pour n de 1 `a 11, en moyennant chaque valeur sur une cinquantaine d’it´erations au moins.
Et r´epondez aux questions suivantes:
• Que constatez-vous quant `a l’efficacit´e relative de ces deux fonctions de couˆt ?
• Que constatez-vous quant `a la complexit´e en temps de l’algorithme ?
2 Assignation de tˆaches (Extra 1 Point)
Dans ce probl`eme, on veut assigner n tˆaches `a n agents, sachant que chaque agent est r´emun´er´e et chaque tˆache est assign´ee `a un agent diff´erent.
C’est un probl`eme que l’on peut couramment rencontrer: assigner des emplacements `a des bˆatiments devant ˆetre construits, assigner des ´ev`enements `a des organisteurs candidats, etc… La r´emun´eration des agents peut ˆetre repr´esent´ee par une matrice des couˆts, ou` l’´el´ement (i,j) repr´esente le couˆt de l’ex´ecution de la tˆache i par l’agent j.
Le but de l’exercice est d’impl´ementer une strat´egie Branch-and-Bound pour r´esoudre ce probl`eme, avec la matrice des couˆts comme param`etre. Pour ce faire, nous proposons de d´ecrire un ´etat, ou solution partielle, par la liste des tˆaches d´ej`a assign´ees et des agents d´ej`a assign´es (on commence donc avec des listes vides). De cette mani`ere, on peut d´efinir le couˆt d’une solution partielle par la somme des couˆts minimaux pour chaque tˆache restante, augment´ee du couˆt effectif des assignations effectu´ees jusque l`a. Prenons par exemple la matrice des couˆts ci-dessous:
#example : cost of task 1 by agent 2 is 17 (numbering starts at index 0) cost_matrix = [ [11, 14, 11, 17],
[12, 15, 17, 14],
[18, 13, 19, 20],
[40, 22, 23, 28]
]
#the optimal assignement for this cost matrix is :
#agent0-task0, agent1-task2, agent2-task3, agent3-task1.
1
2
3
4
5
6
7
8
9
Dans ce cas, le couˆt de la solution partielle ’agent0-task0’ vaut 11 + min(task2) + min(task3) + min(task4) = 11 + 12 + 13 + 22 = 58, ou` ’min(task i)’ d´enote la couˆt minimal pour la tˆache i, en ignorant les agents d´ej`a assign´es (dans l’exemple, l’agent 0).
2.1 Optimalit´e
Une telle fonction de couˆt m`ene-t-elle `a une solution optimale?
2.2 Impl´ementation
Impl´ementez l’algorithme pour une matrice des couˆts de taille arbitraire n. La fonction solve_tasks
(cost_matrix) doit retourner la liste des assignations (par exemple, [0, 3, 1, 2] dans le cas de la matrice des couˆts cidessus).
3 Plus court chemin (Extra 1 Point)
Nous allons dans ce probl`eme ´etudier un algorithme Branch-and-Bound pour trouver le chemin le plus court entre deux points dans un espace bidimensionnel discret (n×m cellules). Pour rendre ce probl`eme int´eressant, on place des obstacles entre ces deux points. On peut repr´esenter cet espace par une matrice ou` chaque cellule peut prendre la valeur 0 (libre) ou 1 (obstacle). Le chemin ne peut ´evidemment pas passer par une cellule dont la valeur est ´egale `a 1. Les mouvements autoris´es sont gauche, droite, haut et bas (pas de mouvements en diagonale).
3.1 Fonction de couˆt
Trouvez une fonction de couˆt ˆc(x) qui remplisse les crit`eres n´ecessaires pour garantir l’optimalit´e d’une solution avec la m´ethode Branch-and-Bound.
3.2 Impl´ementation
Impl´ementez l’algorithme. La fonction solve_shortest_path(domain, a, b) retourne la liste des positions correspondant au chemin entre les points a et b du domaine.