TP1 Artificial Intelligence
Gautier Boëda
Steven Le Rouzic

Question 1)
	L'algorithme BFS est complet et optimal (La solution choisie est la solution la plus courte. Il en trouve toujours une s'il en existe.) alors que l'algorithme DFS est ni complet ni optimal (La solution choisie est la première trouvée. Il peut ne pas en trouver s'il tombe dans une branche infinie.)

Question 2)
	Si l'on souhaite un objet constant, on peut utiliser une matrice de booléens représentant la carte (Vrai s'il y a un fromage).
	Sinon, on peut utiliser une liste de positions. (On peut donc avoir plusieurs fromages par case.)

Question 3)
	L'heuristique choisie est le maximum des distances en norme 1 entre Pacman et chaque fromage non mangé.
	C'est admissible par l'inégalité triangulaire suivant cette norme. En effet, le chemin pour aller d'un point A à un point B est inférieur ou égal à celui pour rejoindre ces deux points en passant par un point intermédiaire.