{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Les Piles" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Présentation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En Informatique, une **pile** (en anglais **stack**) est une structure de données basée sur le principe que l'on nomme traditionnellement **LIFO**\n", " (pour **Last In First Out**) consistant à manipuler une liste dans laquelle les éléments rentrent ou sortent mais uniquement à partir de la fin de la liste : l'élément que l'on supprime d'une pile\n", "est toujours l'élément qui en est entré en dernier.\n", "\n", "Concrètement, il suffit d'imaginer une pile d'assiettes posées sur une table.\n", "\n", "Cette pile d'assiettes correspond à une liste dont le premier terme (le terme d'index $[0]$) est l'assiette posée\n", " sur la table, en dessous de la pile et le \n", "dernier élément (d'index $[-1]$) est l'assiette au-dessus de la pile. On ne peut modifier la pile que de deux façons :\n", "\n", "$\\quad$ $\\rhd$ soit en **empilant** une nouvelle assiette sur la pile : c'est la méthode **push** implémentée en *Python* \n", "par la méthode **.append()**\n", "\n", "$\\quad$ $\\rhd$ soit en désempilant une assiette de la pile : c'est la méthode **.pop()**.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Fonctions primitives associées aux piles" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "En langage *Python*, les piles sont des listes que l'on traite d'une certaine manière. Lorsque l'on manipule une pile, il existe essentiellement trois \n", "fonctions fondamentales que l'on utilise souvent, ces fonctions fondamentales étant appelées **primitives**.\n", "\n", "Considérons une pile $P$. Voici ces trois fonctions primitives :\n", "\n", "$\\longrightarrow$ test de la pile vide, implémenté à travers le branchement **if** : if $P == []$ :\n", "\n", "$\\longrightarrow$ empilement d'une assiette *'nlleassiette'* : $P.append('nlleassiette')$\n", "\n", "$\\longrightarrow$ désempilement d'une assiette (celle du dessus) : $P.pop()$\n", "\n", "\n", "Il est à noter que la méthode **.pop()** fait deux choses :\n", "\n", "$\\qquad$ $\\bullet$ elle crée l'assiette désempilée\n", "\n", "$\\qquad$ $\\bullet$ elle supprime de la pile cette assiette désempilée\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Pile initiale :\n", "['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5', 'assiette6', 'assiette7', 'assiette8', 'assiette9', 'assiette10']\n", " \n", " \n", "Désempilement numéro 1\n", "assiette désempilée : assiette10 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5', 'assiette6', 'assiette7', 'assiette8', 'assiette9']\n", "\n", "\n", "Désempilement numéro 2\n", "assiette désempilée : assiette9 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5', 'assiette6', 'assiette7', 'assiette8']\n", "\n", "\n", "Désempilement numéro 3\n", "assiette désempilée : assiette8 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5', 'assiette6', 'assiette7']\n", "\n", "\n", "Désempilement numéro 4\n", "assiette désempilée : assiette7 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5', 'assiette6']\n", "\n", "\n", "Désempilement numéro 5\n", "assiette désempilée : assiette6 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4', 'assiette5']\n", "\n", "\n", "Désempilement numéro 6\n", "assiette désempilée : assiette5 / pile restante : ['assiette1', 'assiette2', 'assiette3', 'assiette4']\n", "\n", "\n", "Désempilement numéro 7\n", "assiette désempilée : assiette4 / pile restante : ['assiette1', 'assiette2', 'assiette3']\n", "\n", "\n", "Désempilement numéro 8\n", "assiette désempilée : assiette3 / pile restante : ['assiette1', 'assiette2']\n", "\n", "\n", "Désempilement numéro 9\n", "assiette désempilée : assiette2 / pile restante : ['assiette1']\n", "\n", "\n", "Désempilement numéro 10\n", "assiette désempilée : assiette1 / pile restante : []\n", "\n", "\n" ] } ], "source": [ "P=[\"assiette\"+str(k) for k in range(1,11)]\n", "\n", "print(\"Pile initiale :\")\n", "print(P)\n", "\n", "### on procède au désempilement ###\n", "\n", "print(\" \\n \")\n", "\n", "def Depilement(P) :\n", " \"\"\" désemplie totalement une pile \"\"\"\n", " P_Temp=P.copy()\n", " while P_Temp != [] : #tant que la pile est non vide\n", " print(\"Désempilement numéro \",len(P)-len(P_Temp)+1)\n", " print(\"assiette désempilée : \",P_Temp.pop(),\" / pile restante :\",P_Temp)\n", " print(\"\\n\")\n", "\n", "Depilement(P)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Un exemple d'application : exploration dans un environnement" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Présentation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Etant donné un labyrinthe considéré comme une grille pourvue d'obstacles, on définit un point de départ. \n", "On désire implémenter un algorithme de parcours de la composante connexe de la case de départ dans le labyrinthe, les mouvements ne pouvant être qu'horizontaux ou verticaux.\n", "\n", "\n", "Voici le principe, en gérant le problème à l'aide d'une pile :\n", "\n", "$\\quad$ $\\rhd$ on crée $Liste$_$Cases$ qui est la liste de toutes les cases admissibles (c'est-à-dire sans obstacles)\n", "\n", "$\\quad$ $\\rhd$ on crée $Case$_$Dep$ indiquant la position de départ\n", "\n", "$\\quad$ $\\rhd$ la pile $P$ correspond à la trajectoire en temps réel dans notre labyrinthe :\n", "\n", "$\\qquad$ $\\longrightarrow$ on empile $Case$_$Dep$ dans $P$\n", "\n", "$\\qquad$ $\\longrightarrow$ on enlève $Case$_$Dep$ de $Liste$_$Cases$ ($Liste$_$Cases$ n'est pas une pile mais plutôt \n", "un stock d'assiettes en libre service)\n", "\n", "\n", "$\\qquad$ $\\longrightarrow$ d'une étape à l'autre, on considère une case de $Liste$_$Cases$ adjacente à $P[-1]$ : on procède\n", "à l'empilement de cette case et on la supprime de $Liste$_$Cases$ ; si aucune case de $Liste$_$Cases$ n'est adjacente à \n", "$P[-1]$, on désempile $P$ \n", "\n", "$\\quad$ $\\rhd$ on recommence tant que la pile est non vide.\n", "\n", "$\\quad$ $\\rhd$ en sortie de boucle **while**, la pile est vide : on a exploré toutes les cases admissibles.\n", "\n", "**Remarque** : le mouvement est toujours en avant si cela est possible. Si on rencontre un obstacle, on choisit aléatoirement une direction.\n" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "from pylab import *\n", "from tkinter import *\n", "\n", "\n", "### calibrage de la taille du canevas\n", "c=20\n", "largeur=30\n", "hauteur=20\n", " \n", "\n", "Taille_largeur=c*largeur\n", "Taille_hauteur=c*hauteur\n", "\n", "### initialisation : aucun obstacle\n", "Liste_Cases=[[i,j] for i in range(largeur+1) for j in range(hauteur+1)]\n", "direction=[1,0] # par défaut, on va à droite au début\n", "\n", "### initialisation : aucune case remplie dans la trajectoire\n", "Pile=[]\n", "\n", "### initialisation : case en dehors du canevas\n", "Case_Dep=[-1,0]\n", "\n", "def click_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c) # index de la case cliquée\n", " j=int(y/c) \n", " \n", " if [i,j] in Liste_Cases :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')\n", " Liste_Cases.remove([i,j])\n", " ### création de la case noire d'obstacle\n", " ### comptabilisation dans Liste_Cases\n", "\n", "\n", "def declick_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " \n", " if not([i,j] in Liste_Cases) :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='white')\n", " Liste_Cases.append([i,j])\n", " ### effets contraires à l'autre commande\n", "\n", "\n", "def obstacles() :\n", " global b2,b3\n", " canevas.bind(\"\", click_case)\n", " canevas.bind(\"\", declick_case)\n", " b2.destroy() # on détruit le widget 'Mettre les obstacles'\n", " b3=Button(fenetre,text='Mettre la case de départ',command=depart)\n", " b3.pack(side =RIGHT, padx =3, pady =3)\n", "\n", "Nbre_choix=0\n", "\n", "def click_depart(event) :\n", " global Liste_Cases,Case_Dep,Pile,b3,Nbre_choix,b4\n", " \n", " canevas.bind(\"\", inutile) # on désactive le clic droit\n", " ### on aurait pu mettre le .bind en mémoire et détruire cette mémoire par .destroy()\n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " if [i,j] in Liste_Cases : # case cliquée blanche initialement\n", " Nbre_choix+=1 # comptabilisation du choix\n", " if Case_Dep != [-1,0] : # ce n'est pas le premier choix\n", " canevas.delete(Pile[0][1]) # destruction de la case graphique\n", " Pile.pop() # suppression de la case de départ de la pile\n", " Case_Dep=[i,j]# on met à jour la case de départ\n", " Pile.append([[i,j],canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green')]) \n", " # on met à jour la pile\n", " if Case_Dep!=[-1,0] and Nbre_choix == 1 : # une case déjà choisie\n", " ### on détruit le widget 'Mettre al case de départ à la première bonne case cliquée\n", " b3.destroy()\n", " b4=Button(fenetre,text='Explorer',command=sortie)\n", " b4.pack(side =RIGHT, padx =3, pady =3) \n", " ### on crée un nouveau widget mais une seule fois !!\n", " \n", "def depart() :\n", " global Case_Dep\n", " \n", " canevas.bind(\"\", click_depart)\n", "\n", "def inutile(event) :\n", " pass \n", " \n", " \n", " \n", "def sortie():\n", " global Liste_Cases,Case_Dep,Pile,b4,direction\n", " canevas.bind(\"\", inutile) # on désactive le clic gauche\n", " Liste_Cases.remove(Case_Dep)## maintenant que la case départ est définitive, on l'enlève des cases admissibles\n", " b4.destroy() # destruction du widget \"sortie\"\n", " c1,c2=1,0 # c1 : nombre de cases visitées,c2=nbre de mouvements\n", " while Pile!=[] :\n", " i,j=Pile[-1][0]\n", " dx,dy=direction\n", " if [i+dx,j+dy] in Liste_Cases :\n", " Pile.append([[i+dx,j+dy],canevas.create_rectangle((i+dx)*c, (j+dy)*c, (i+dx+1)*c, (j+dy+1)*c, fill='magenta')])\n", " Liste_Cases.remove([i+dx,j+dy])\n", " c1+=1\n", " c2+=1\n", " \n", " else : #il faut changer de direction\n", " Voisins=[[i+k,j] for k in [-1,1] if [i+k,j] in Liste_Cases]+[[i,j+l] for l in [-1,1] if [i,j+l] in Liste_Cases]\n", " \n", " if Voisins==[] :\n", " canevas.create_rectangle((Pile[-1][0][0])*c, (Pile[-1][0][1])*c, (Pile[-1][0][0]+1)*c, (Pile[-1][0][1]+1)*c, fill='#58FAF4')\n", " Pile.pop()\n", " c2+=1\n", " else :\n", " I,J=Voisins[randint(len(Voisins))] # choix d'un voisin au hasard\n", " \n", " Pile.append([[I,J],canevas.create_rectangle(I*c, J*c, (I+1)*c, (J+1)*c, fill='magenta')])\n", " Liste_Cases.remove([I,J])\n", " direction=[I-i,J-j]\n", " c1+=1\n", " c2+=1\n", " \n", " fenetre.after(20)\n", " fenetre.update()\n", " \n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green') \n", " fenetre_fin=Tk()\n", " for k in range(3) : # on fait clignoter le texte trois fois \n", " texte1=Label(fenetre_fin,text=\"Fin de l'exploration !!\",font='Arial 20',fg=\"red\")\n", " texte1.pack()\n", " texte2=Label(fenetre_fin,text=\"Nbre de cases visitées : \"+str(c1),font='Arial 20',fg=\"blue\")\n", " texte2.pack()\n", " texte3=Label(fenetre_fin,text=\"Nbre de mouvements : \"+str(c2),font='Arial 20',fg=\"blue\")\n", " texte3.pack()\n", " fenetre_fin.after(300)\n", " fenetre_fin.update()\n", " texte1.destroy()\n", " texte2.destroy()\n", " texte3.destroy()\n", " fenetre_fin.after(200)\n", " fenetre_fin.update()\n", " texte1=Label(fenetre_fin,text=\"Fin de l'exploration !!\",font='Arial 20',fg=\"red\")\n", " texte1.pack()\n", " texte2=Label(fenetre_fin,text=\"Nbre de cases visitées : \"+str(c1),font='Arial 20',fg=\"blue\")\n", " texte2.pack()\n", " texte3=Label(fenetre_fin,text=\"Nbre de mouvements : \"+str(c2),font='Arial 20',fg=\"blue\")\n", " texte3.pack() # le texte est finalement apparent \n", " b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit)\n", " b.pack(side =BOTTOM)\n", " fenetre_fin.mainloop()\n", " fenetre_fin.destroy() \n", " \n", " \n", "def dessiner_grille(): \n", " \"\"\" dessine la grille \"\"\"\n", " for i in range(largeur+2) :\n", " canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black')\n", " for j in range(hauteur+2) :\n", " canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black')\n", " \n", " fenetre.update()\n", "\n", "\n", " \n", " \n", " \n", "########## interface graphique ##########\n", "\n", "\n", "fenetre = Tk()\n", "canevas = Canvas(fenetre, width =Taille_largeur+c, height =Taille_hauteur+c, bg ='white')\n", "\n", " \n", "canevas.pack(side =TOP, padx =5, pady =5)\n", "dessiner_grille()\n", "\n", "\n", "b1 = Button(fenetre, text ='Quitter', command =fenetre.quit)\n", "b1.pack(side =RIGHT, padx =3, pady =3)\n", "\n", "b2=Button(fenetre,text='Mettre les obstacles',command=obstacles)\n", "b2.pack(side =RIGHT, padx =3, pady =3)\n", "fenetre.mainloop()\n", "fenetre.destroy()\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Voici le script amélioré :\n", "\n", "$\\rhd$ on peut mettre des obstacles aléatoirement\n", " \n", "$\\rhd$ le robot a un radar : il détecte les cases adjacentes éventuellement libres et qu'il n'emprunte pas encore : cela lui permet de savoir s'il lui reste d'autres cases à explorer ou non sans pour autant entièrement dépiler la pile." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "from pylab import *\n", "from tkinter import *\n", "\n", "\n", "### calibrage de la taille du canevas\n", "c=20\n", "largeur=50\n", "hauteur=30\n", " \n", "\n", "Taille_largeur=c*largeur\n", "Taille_hauteur=c*hauteur\n", "\n", "### initialisation : aucun obstacle\n", "Liste_Cases=[[i,j] for i in range(largeur+1) for j in range(hauteur+1)]\n", "direction=[1,0] # par défaut, on va à droite au début\n", "\n", "### initialisation : aucune case remplie dans la trajectoire\n", "Pile=[]\n", "\n", "### initialisation : case en dehors du canevas\n", "Case_Dep=[-1,0]\n", "\n", "def click_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c) # index de la case cliquée\n", " j=int(y/c) \n", " \n", " if [i,j] in Liste_Cases :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')\n", " Liste_Cases.remove([i,j])\n", " ### création de la case noire d'obstacle\n", " ### comptabilisation dans Liste_Cases\n", "\n", "\n", "def declick_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " \n", " if not([i,j] in Liste_Cases) :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='white')\n", " Liste_Cases.append([i,j])\n", " ### effets contraires à l'autre commande\n", "\n", "Test_bouton_dep=True\n", "\n", "def obstacles() :\n", " global b2,b3,Test_bouton_dep\n", " canevas.bind(\"\", click_case)\n", " canevas.bind(\"\", declick_case)\n", " b2.destroy() # on détruit le widget 'Mettre les obstacles manuellement'\n", " if Test_bouton_dep :\n", " \n", " b3=Button(fenetre,text='Mettre la case de départ',command=depart)\n", " b3.pack(side =RIGHT, padx =3, pady =3)\n", " Test_bouton_dep=False\n", "\n", "def obstacles_alea():\n", " global b_alea,Liste_Cases,Test_bouton_dep,b3\n", " for i in range(largeur+1) :\n", " for j in range(hauteur+1) :\n", " if binomial(1,0.4) :\n", " Liste_Cases.remove([i,j])\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')\n", " b_alea.destroy()\n", " if Test_bouton_dep :\n", " b3=Button(fenetre,text='Mettre la case de départ',command=depart)\n", " b3.pack(side =RIGHT, padx =3, pady =3)\n", " Test_bouton_dep=False\n", " \n", "Nbre_choix=0\n", "\n", "def click_depart(event) :\n", " global Liste_Cases,Case_Dep,Pile,b3,Nbre_choix,b4\n", " \n", " canevas.bind(\"\", inutile) # on désactive le clic droit\n", " ### on aurait pu mettre le .bind en mémoire et détruire cette mémoire par .destroy()\n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " if [i,j] in Liste_Cases : # case cliquée blanche initialement\n", " Nbre_choix+=1 # comptabilisation du choix\n", " if Case_Dep != [-1,0] : # ce n'est pas le premier choix\n", " canevas.delete(Pile[0][1]) # destruction de la case graphique\n", " Pile.pop() # suppression de la case de départ de la pile\n", " Case_Dep=[i,j]# on met à jour la case de départ\n", " Pile.append([[i,j],canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green')]) \n", " # on met à jour la pile\n", " if Case_Dep!=[-1,0] and Nbre_choix == 1 : # une case déjà choisie\n", " ### on détruit le widget 'Mettre la case de départ à la première bonne case cliquée\n", " b3.destroy()\n", " b4=Button(fenetre,text='Explorer',command=sortie)\n", " b4.pack(side =RIGHT, padx =3, pady =3) \n", " ### on crée un nouveau widget mais une seule fois !!\n", " \n", "def depart() :\n", " global Case_Dep,b2,b_alea\n", " try :\n", " b2.destroy()\n", " except :\n", " pass\n", " try :\n", " b_alea.destroy()\n", " except :\n", " pass\n", " \n", " canevas.bind(\"\", click_depart)\n", "\n", "def inutile(event) :\n", " pass \n", " \n", " \n", " \n", "def sortie():\n", " global Liste_Cases,Case_Dep,Pile,b4,direction\n", " canevas.bind(\"\", inutile) # on désactive le clic gauche\n", " Liste_Cases.remove(Case_Dep)## maintenant que la case départ est définitive, on l'enlève des cases admissibles\n", " b4.destroy() # destruction du widget \"sortie\"\n", " c1,c2=1,0 # c1 : nombre de cases visitées,c2=nbre de mouvements\n", " i,j=Case_Dep\n", " Cases_encore=[[i+k,j] for k in [-1,1] if [i+k,j] in Liste_Cases]+[[i,j+l] for l in [-1,1] if [i,j+l] in Liste_Cases] # tient compte des cases non encore explorées\n", " \n", " while Pile!=[] :\n", " i,j=Pile[-1][0]\n", " Voisins=[[i+k,j] for k in [-1,1] if [i+k,j] in Liste_Cases]+[[i,j+l] for l in [-1,1] if [i,j+l] in Liste_Cases]\n", " Cases_encore.extend([pos for pos in Voisins if not(pos in Cases_encore)])\n", " dx,dy=direction\n", " if [i+dx,j+dy] in Voisins :\n", " Pile.append([[i+dx,j+dy],canevas.create_rectangle((i+dx)*c, (j+dy)*c, (i+dx+1)*c, (j+dy+1)*c, fill='magenta')])\n", " Liste_Cases.remove([i+dx,j+dy])\n", " c1+=1\n", " c2+=1\n", " if [i+dx,j+dy] in Cases_encore :\n", " Cases_encore.remove([i+dx,j+dy])\n", " \n", " \n", " else : #il faut changer de direction\n", " \n", " if Voisins==[] :\n", " canevas.create_rectangle((Pile[-1][0][0])*c, (Pile[-1][0][1])*c, (Pile[-1][0][0]+1)*c, (Pile[-1][0][1]+1)*c, fill='#58FAF4')\n", " Pile.pop()\n", " c2+=1\n", " else :\n", " I,J=Voisins[randint(len(Voisins))] # choix d'un voisin au hasard\n", " Pile.append([[I,J],canevas.create_rectangle(I*c, J*c, (I+1)*c, (J+1)*c, fill='magenta')])\n", " Liste_Cases.remove([I,J])\n", " direction=[I-i,J-j]\n", " c1+=1\n", " c2+=1\n", " if [I,J] in Cases_encore :\n", " Cases_encore.remove([I,J])\n", " \n", " fenetre.after(20)\n", " fenetre.update()\n", " \n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green') \n", " fenetre_fin=Tk()\n", " for k in range(3) : # on fait clignoter le texte trois fois \n", " texte1=Label(fenetre_fin,text=\"Fin de l'exploration !!\",font='Arial 20',fg=\"red\")\n", " texte1.pack()\n", " texte2=Label(fenetre_fin,text=\"Nbre de cases visitées : \"+str(c1),font='Arial 20',fg=\"blue\")\n", " texte2.pack()\n", " texte3=Label(fenetre_fin,text=\"Nbre de mouvements : \"+str(c2),font='Arial 20',fg=\"blue\")\n", " texte3.pack()\n", " fenetre_fin.after(300)\n", " fenetre_fin.update()\n", " texte1.destroy()\n", " texte2.destroy()\n", " texte3.destroy()\n", " fenetre_fin.after(200)\n", " fenetre_fin.update()\n", " texte1=Label(fenetre_fin,text=\"Fin de l'exploration !!\",font='Arial 20',fg=\"red\")\n", " texte1.pack()\n", " texte2=Label(fenetre_fin,text=\"Nbre de cases visitées : \"+str(c1),font='Arial 20',fg=\"blue\")\n", " texte2.pack()\n", " texte3=Label(fenetre_fin,text=\"Nbre de mouvements : \"+str(c2),font='Arial 20',fg=\"blue\")\n", " texte3.pack() # le texte est finalement apparent \n", " b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit)\n", " b.pack(side =BOTTOM)\n", " fenetre_fin.mainloop()\n", " fenetre_fin.destroy() \n", " \n", " \n", "def dessiner_grille(): \n", " \"\"\" dessine la grille \"\"\"\n", " for i in range(largeur+2) :\n", " canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black')\n", " for j in range(hauteur+2) :\n", " canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black')\n", " \n", " fenetre.update()\n", "\n", "\n", " \n", " \n", " \n", "########## interface graphique ##########\n", "\n", "\n", "fenetre = Tk()\n", "canevas = Canvas(fenetre, width =Taille_largeur+c, height =Taille_hauteur+c, bg ='white')\n", "\n", " \n", "canevas.pack(side =TOP, padx =5, pady =5)\n", "dessiner_grille()\n", "\n", "\n", "b1 = Button(fenetre, text ='Quitter', command =fenetre.quit)\n", "b1.pack(side =RIGHT, padx =3, pady =3)\n", "\n", "b2=Button(fenetre,text='Mettre les obstacles manuellement',command=obstacles)\n", "b2.pack(side =RIGHT, padx =3, pady =3)\n", "b_alea=Button(fenetre,text='Mettre les obstacles aléatoirement',command=obstacles_alea)\n", "b_alea.pack(side =RIGHT, padx =3, pady =3)\n", "fenetre.mainloop()\n", "fenetre.destroy()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Applications des piles : recherche en profondeur dans un graphe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes : premières notions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Un **graphe** est la donnée de deux choses :\n", "\n", "$\\quad$ $\\longrightarrow$ un ensemble $S$ de **sommets**\n", "\n", "$\\quad$ $\\longrightarrow$ un ensemble ${\\cal A}$ d'**arêtes**, qui sont des éléments de l'ensemble $S^2\\setminus \\lbrace (x,x)~;~x\\in S\\rbrace$.\n", "On considère que les arêtes ne peuvent joindre que deux sommets différents.\n", "\n", "On dit que le graphe est **orienté** si le sens de parcours des arêtes est pris en compte. On peut dès lors avoir $(x,y)\\in {\\cal A}$\n", " et $(y,x)\\notin {\\cal A}$.\n", "\n", "On dit que le graphe est **non orienté** si le sens de parcours des arêtes n'est pas pris en compte.\n", "Les arêtes peuvent alors être vues comme des paires $\\lbrace x,y\\rbrace$ au lieu de couples.\n", "\n", "On représente un graphe par un ensemble de points (les sommets) et par les lignes reliant ces points (les arêtes), en indiquant\n", "dans le cas des graphes orientés le sens de parcours.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes : exemples" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les graphes orientés sont souvent plus utiles que les graphes non orientés et trouvent d'ailleurs davantage d'applications.\n", "\n", "De manière générale, les graphes peuvent modéliser n'importe quelle relation ${\\cal R}$ non réflexive sur un ensemble $S$ : les arêtes\n", "sont exactement les couples $(x,y)$ tels que $x{\\cal R} y$. Lorsque la relation ${\\cal R}$ est symétrique, le graphe\n", "peut être vu comme un graphe non orienté.\n", "\n", "Voici des exemples de graphes :\n", "\n", "$\\quad$ $\\longrightarrow$ cartes routières : \n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les villes\n", "\n", "$\\qquad$ $\\bullet$ les arêtes sont les routes reliant des villes ; le fait que certaines routes soient à sens unique \n", "confèrent un caractère orienté à ce graphe\n", "\n", "$\\quad$ $\\longrightarrow$ arborescence dans un système d'exploitation\n", "\n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les dossiers\n", "\n", "$\\qquad$ $\\bullet$ les arêtes sont les couples (répertoire,sous-répertoire) ou (répertoire,sous-fichier)\n", "\n", "$\\quad$ $\\longrightarrow$ réseaux de communication\n", "\n", "\n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les individus\n", "\n", "$\\qquad$ $\\bullet$ les arêtes sont les couples (appelant,appelé) \n", "\n", "\n", "$\\quad$ $\\longrightarrow$ arbres généalogiques\n", "\n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les individus\n", "\n", "$\\qquad$ $\\bullet$ les arêtes indiquent les liens de parenté d'une génération à l'autre\n", "\n", "$\\quad$ $\\longrightarrow$ jeux\n", "\n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les phases possibles du jeu\n", "\n", "$\\qquad$ $\\bullet$ les arêtes sont les couples (position1,position2), où position2 est une position du jeu à partir de position1 après un coup\n", "\n", "\n", "$\\quad$ $\\longrightarrow$ colorations de cartes\n", "\n", "\n", "$\\qquad$ $\\bullet$ les sommets sont les régions de la carte\n", "\n", "$\\qquad$ $\\bullet$ les arêtes sont les couples de régions adjacentes : c'est un graphe non orienté.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graphes : vocabulaire supplémentaire" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Soit $G=(S,{\\cal A})$ un graphe.\n", "\n", "Si $s$ est un sommet, on appelle **degré de $s$** et on note $\\deg (s)$, le nombre de ses voisins, c'est-à-dire le nombre de \n", "sommets adjacents à $s$ : le nombre d'éléments de l'ensemble $\\lbrace t\\in S~|~(s,t)\\in {\\cal A}\\rbrace$.\n", "\n", "Si $(x,y)\\in {\\cal A}$, le somme $x$ est appelé **sommet-père** et le sommet $y$ est appelé **sommet-fils**.\n", "\n", "On appelle **chaîne de sommets**, toute liste $(s_0,\\cdots,s_n)$ de sommets tels que pour tout $k\\in\\lbrace 0,\\cdots,\n", "n-1\\rbrace$, $(s_k,s_{k+1})\\in {\\cal A}$. L'entier $n$ est appelé la **longueur** de la chaîne.\n", "\n", "On appelle **cycle**, toute chaîne de sommets de longueur supérieure ou égale à $3$ $(s_0,\\cdots,s_n)$ avec $s0=s_n$.\n", "\n", "On dit qu'un graphe est un **arbre** s'il n'admet aucun cycle.\n", "\n", "On dit qu'un graphe est **connexe par arcs** si pour tous sommets $x$ et $y$, il existe une chaîne de sommets reliant $x$ à $y$.\n", "\n", "On appelle **racine** d'un graphe, un sommet n'admettant aucun sommet-père. On appelle **feuille**, tout sommet n'admettant\n", "aucun sommet-fils. \n", "\n", "Dans le cas des graphes connexes par arcs et non orientés, on peut définir sur $S$ une distance : \n", "$d(x,y)$ est la longueur minimale des chaînes de sommets reliant $x$ à $y$. On a alors les propriétés suivantes :\n", "\n", " $\\quad$ $\\rhd$ $d(x,y)\\geq 0$ et $d(x,y)=0\\Longleftrightarrow x=y$\n", "\n", " $\\quad$ $\\rhd$ $d(x,y)=d(y,x)$\n", "\n", " $\\quad$ $\\rhd$ $d(x,z)\\leq d(x,y)+d(y,z)$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Problèmatique de la recherche dans un graphe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "Etant donnés un graphe $(S,{\\cal A})$, puis un sommet de départ $s_d$ et un autre sommet $s_a$, rechercher le sommet $s_a$\n", "à partir du sommet $s_d$ dans le graphe consiste à trouver une chaîne de sommets reliant $s_d$ à $s_a$.\n", "\n", "Il existe plusieurs algorithmes de recherche mais l'algorithme de recherche en profondeur fait intervenir des piles. En voici le principe :\n", "\n", "$\\quad$ $\\longrightarrow$ on part de $s_a$ et d'une pile vide $P$\n", "\n", "$\\quad$ $\\longrightarrow$ on empile $s_a$ dans $P$ et on marque $s_a$ (c'est-à-dire que l'on supprime $s_a$ de la liste des \n", "sommets non encore visités)\n", "\n", "$\\quad$ $\\longrightarrow$ tant que $P[-1]$ est différent de $s_d$ et a un sommet-fils, on empile un sommet-fils, tout en marquant à\n", "chaque fois les sommets pris en compte\n", "\n", "$\\quad$ $\\longrightarrow$ dès que $P[-1]$ est différent de $s_d$ et est une feuille, on désempile $P$\n", "\n", "$\\quad$ $\\longrightarrow$ deux cas se produisent en fin de boucle :\n", "\n", "$\\qquad$ $\\rhd$ soit la pile $P$ devient vide : on ne peut pas relier $s_d$ à $s_a$ par un chemin\n", "\n", "\n", "$\\qquad$ $\\rhd$ soit on arrive au sommet $s_d$ et la pile donne un chemin reliant $s_d$ à $s_a$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarques** : " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " $\\bullet$ on retrouve le raisonnement du labyrinthe où empiler revient à se déplacer une fois de plus dans notre labyrinthe et désempiler\n", "revient à revenir une fois en arrière\n", "\n", " $\\bullet$ tout problème dont la résolution consiste à construire une pile est en fait un problème de recherche en profondeur dans un graphe :\n", "les sommets de ce graphe sont les objets de la pile du problème et deux objets constituent une arête orientée\n", "si et seulement si le sommet-père est au cours du processus une assiette posée juste en dessous du sommet-fils.\n", "\n", "$\\bullet$ il existe d'autres algorithmes de recherche dans un graphe; en particulier, la recherche en largeur \n", "consiste non pas à explorer d'abord tous les chemins de longueur maximale avant de revenir en arrière éventuellement comme \n", "on le ferait pour une recherche en profondeur, mais à examiner les sommets de première génération (les sommets à distance \n", "égale à $1$ du sommet de départ), puis leurs voisins (les sommets de deuxième génération), etc. Cet algorithme met en place\n", "des files plutôt que des piles.\n", "\n", "$\\bullet$ les **files** sont d'autres structures de données de type **FIFO** pour (**First In First OUT**) pour lesquelles on manipule des listes où l'objet qui sort est toujours l'objet qui a été incorporé le premier parmi les éléments présents dans la liste. Ceci modélise les files d'attente. On examine lors d'une recherche en largeur les sommets de première génération et si le test n'est pas concluant, on incorpore les sommets de deuxième génération et on les examine dans l'ordre de leur arrivée." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implémentation d'une interface pour visualiser la recherche en profondeur " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le script ci-dessous répond au cahier des charges suivant :\n", "\n", "$\\bullet$ il implémente une interface graphique qui :\n", "\n", "$\\quad$ $\\rhd$ donne la possibilité à l'utilisateur de choisir par clic gauche les sommets d'un graphe ; au fur et à mesure de leur construction ces sommets sont numérotés par ordre croissant\n", "\n", "$\\quad$ $\\rhd$ donne la possiblité à l'utilisateur de choisir parmi les sommets présents de relier ces sommets par des arêtes orientées : les arêtes du graphe sont toujours orientées du sommet portant le plus petit numéro vers le sommet portant le plus grand numéro\n", "\n", "**Remarque :** une difficulté : gérer les clics intempestifs de l'utilisateur en prenant garde de ne relier que des sommets différents et en prenant garde de ne pas chevaucher les sommets\n", "\n", "$\\quad$ $\\rhd$ invite l'utilisateur à choisir un sommet de départ\n", "\n", "$\\quad$ $\\rhd$ invite l'utilisateur à choisir un sommet d'arrivée différent du sommet de départ\n", "\n", "$\\bullet$ il implémente le parcours de recherche en profondeur pour trouver une chaîne de sommets reliant les deux sommets choisis\n", "\n", "**Remarque :** la difficulté est de stocker les objets graphiques pour pouvoir les manipuler lors du parcours et ainsi modifier les couleurs\n", "\n", "$\\bullet$ affiche une fenêtre d'information de terminaison de l'algorithme ; en cas de succès, la chaîne trouvée est apparente et en cas d'échec, les sommets choisis clignotent." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "from tkinter import *\n", "\n", "\n", "\n", "rayon=15 ### rayon des disques autour des sommets\n", "Sommets,Aretes=[],[]\n", "compteur=0\n", "\n", "def Graphe() :\n", " global Sommets,Aretes,compteur\n", " \n", " canevas.bind(\"\",construire_sommets)\n", " canevas.bind(\"\",construire_aretes)\n", "\n", "def construire_sommets(event) :\n", " global Sommets,Aretes,compteur\n", " x,y=event.x,event.y\n", " \n", " if Test_Debordement([M[0] for M in Sommets],[x,y]) == [] :\n", " ### si le clic ne déborde pas sur un sommet existant\n", " Sommets.append([[x,y],compteur,canevas.create_oval(x-rayon,y-rayon,x+rayon,y+rayon,fill='#BE81F7'),canevas.create_text(x,y,text=str(compteur),font='bold',fill='black')])\n", " # on met tout en mémoire, y compris les graphismes\n", " compteur+=1\n", "\n", "def Test_Debordement(sommets,point) :\n", " global Sommets,Aretes,compteur\n", " Test=[]\n", " for S in sommets :\n", " if (S[0]-point[0])**2+ (S[1]-point[1])**2 <1600 :\n", " Test=S\n", " break\n", " return Test\n", " ### Soit Test=[], auquel cas pas de débordement, soit Test=S$ auquel débordement\n", " ### avec le sommet S\n", " \n", "compteur_Temp,L_Temp=0,[]\n", "\n", "### pour comptabiliser deux clics convenables et tracer l'arête entre les deux\n", "\n", "flag=1\n", "\n", "### pour ne créer qu'une seule fois le widget 'sommet_depart'\n", "\n", "def construire_aretes(event) :\n", " global Sommets,Aretes,compteur,compteur_Temp,L_Temp,s_Temp1,s_Temp2,flag,bouton_depart\n", " x,y=event.x,event.y\n", " \n", " s=Test_Debordement([M[0] for M in Sommets],[x,y])\n", " if s!=[] and compteur_Temp==0 :\n", " ### si on a empiètement sur l'un des sommets et premier clic\n", " s_Temp1=canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#F7FE2E')\n", " L_Temp.append(s)\n", " ### mise en mémoire du sommet \n", " compteur_Temp+=1\n", " construire_aretes\n", " \n", " if s!=[] and compteur_Temp==1 and s!=L_Temp[0] :\n", " ### on vient de cliquer sur un deuxième sommet\n", " ### si on a empiètement sur l'un des autres sommets et second clic\n", " s_Temp2=canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#F5A9A9')\n", " fenetre.update()\n", " L_Temp.append(s)\n", " Trace_Arete(L_Temp[0],L_Temp[1])\n", " fenetre.after(300)\n", " fenetre.update()\n", " ### attente d'une seconde\n", " canevas.delete(s_Temp1)\n", " canevas.delete(s_Temp2)\n", " fenetre.update()\n", " \n", " index_Temp=0\n", " compteur_index=0\n", " k=0\n", " Arete_Orientee=[]\n", " \n", " while compteur_index !=2 :\n", " if Sommets[k][0] in L_Temp :\n", " ### [k] est l'index du premier sommet cliqué\n", " compteur_index+=1\n", " Arete_Orientee.append(Sommets[k][0])\n", " ### mise en mémoire du sommet_père portant le plus petit numéro\n", " k+=1\n", " ### on passe à l'index suivant\n", " \n", " if not(Arete_Orientee in Aretes) :\n", " Aretes.append(Arete_Orientee)\n", "\n", " ### on met en mémoire l'arête orientée crééeet \n", " \n", " compteur_Temp,L_Temp=0,[]\n", " ### pour pouvoir recommencer les click\n", " \n", " if flag :\n", " ### la première fois que l'on rencontre cette ligne\n", " bouton_depart = Button(fenetre, text ='Mettre le sommet de départ', command =sommet_depart)\n", " bouton_depart.pack(side=RIGHT, padx =3, pady =3)\n", " flag=0\n", " ### on ne met ce bouton qu'une seule fois\n", "\n", " \n", "def sommet_depart() :\n", " global Sommets,Aretes,S_d \n", " canevas.bind(\"\",click_depart)\n", " canevas.bind(\"\",inutile)\n", " bouton_graphe.destroy()\n", " \n", " \n", "def inutile(event) :\n", " 1 \n", "\n", "def click_depart(event) :\n", " global Sommets,Aretes,S_d,S_a, bouton_depart,bouton_arrivee\n", " x,y=event.x,event.y\n", " \n", " s=Test_Debordement([M[0] for M in Sommets],[x,y])\n", " if s!=[] :\n", " ### on veut pointer un sommet du graphe\n", " k=0\n", " while Sommets[k][0] != s :\n", " k+=1\n", " M=Sommets[k][0]\n", " c=Sommets[k][1]\n", " Sommets[k]=[M,c,canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#2EFE2E'),canevas.create_text(s[0],s[1],text=str(c),font='bold',fill='black')]\n", " S_d=s\n", " fenetre.update() \n", " canevas.bind(\"\",inutile)\n", " ### on met temporairement hors service la souris\n", " bouton_depart.destroy()\n", " bouton_arrivee = Button(fenetre, text =\"Mettre le sommet d'arrivée\", command =sommet_arrivee)\n", " bouton_arrivee.pack(side=RIGHT, padx =3, pady =3)\n", " \n", " else :\n", " click_depart\n", "def sommet_arrivee() :\n", " global Sommets,Aretes,S_d,S_a,bouton_depart\n", " canevas.bind(\"\",click_arrivee) \n", " \n", " \n", "def click_arrivee(event) :\n", " global Sommets,Aretes,S_d,S_a,bouton_recherche,bouton_arrivee\n", " \n", " x,y=event.x,event.y\n", " \n", " s=Test_Debordement([M[0] for M in Sommets],[x,y])\n", " if s!=[] and s!=S_d :\n", " ### on veut pointer un sommet du graphe différent du départ\n", " k=0\n", " while Sommets[k][0] != s :\n", " k+=1\n", " M=Sommets[k][0]\n", " c=Sommets[k][1]\n", " Sommets[k]=[M,c,canevas.create_oval(s[0]-rayon,s[1]-rayon,s[0]+rayon,s[1]+rayon,fill='#FA5858'),canevas.create_text(s[0],s[1],text=str(c),font='bold',fill='black')]\n", " S_a=s\n", " fenetre.update() \n", " canevas.bind(\"\",inutile)\n", " ### on met définitivement hors service la souris\n", " bouton_arrivee.destroy() \n", " bouton_recherche = Button(fenetre, text ='Lancer la recherche en profondeur', command =recherche)\n", " bouton_recherche.pack(side=RIGHT, padx =3, pady =3)\n", " \n", " else :\n", " click_depart\n", "\n", "### Partie programmation de recherche en profondeur\n", "\n", "def recherche() :\n", " global Sommets,Aretes,S_d,S_a \n", " bouton_recherche.destroy()\n", " \n", " Pile=[[S_d]]\n", " # voici notre pile : le premier index est le sommet de départ\n", " L_Assiettes=[M for M in Sommets if M[0] != S_d]\n", " \n", " ###on met en mémoire les sommets et arêtes coloriées pour les effacer éventuellement\n", " while Pile[-1][0] != S_a :\n", " Test_Empilage=True\n", " while Test_Empilage :\n", " Test_Empilage=False\n", " for k in range(len(L_Assiettes)) :\n", " ## parcours par index pour avoir accès aux compteurs\n", " S=L_Assiettes[k]\n", " x,y=S[0][0],S[0][1]\n", " T=Pile[-1][0]\n", " ### dernier sommet marqué\n", " if [T,S[0]] in Aretes :\n", " L_Assiettes.remove(S)\n", " # on marque le sommet\n", " Aretes.remove([T,S[0]])\n", " # on marque l'arête\n", " Pile.append([S[0],canevas.create_oval(x-rayon,y-rayon,x+rayon,y+rayon,fill='white'),canevas.create_text(x,y,text=str(S[1]),font='bold',fill='black'),Trace_Arete(T,S[0],couleur='red')])\n", " ## on empile\n", " fenetre.after(1000)\n", " fenetre.update()\n", " ## Pile : [0] pour le point, [1] pour le disque blanc,[2] pour le compteur du sommet, [3] pour l'arête \n", " \n", " Test_Empilage=True\n", " ## om comptabilise l'empilage\n", " break\n", " # on a pu avancer d'un cran dans notre recherche\n", " # en sortie de while on n'a pas pu empiler\n", " if Pile[-1][0]==S_a :\n", " break\n", " ### chemin impossible et on sort de la boucle while\n", " if not(Test_Empilage) and len(Pile)>1 : \n", " ### on recule d'un sommet à condition de ne pas \n", " for j in range(1,4) :\n", " canevas.delete(Pile[-1][j])\n", " ### effacement du sommet marqué, du compteur marqué et de l'arête marquée\n", " Pile.pop()\n", " ## désempilage\n", " fenetre.after(1000)\n", " fenetre.update() \n", " elif not(Test_Empilage) and len(Pile)==1 :\n", " ### chemin impossible et on fait clignoter les sommets extrémaux\n", " for j in range(5) :\n", " dep=canevas.create_oval(S_d[0]-rayon,S_d[1]-rayon,S_d[0]+rayon,S_d[1]+rayon,fill='#FF8000')\n", " arr=canevas.create_oval(S_a[0]-rayon,S_a[1]-rayon,S_a[0]+rayon,S_a[1]+rayon,fill='#0101DF')\n", " fenetre.after(250)\n", " fenetre.update()\n", " canevas.delete(dep)\n", " canevas.delete(arr)\n", " dep=canevas.create_oval(S_d[0]-rayon,S_d[1]-rayon,S_d[0]+rayon,S_d[1]+rayon,fill='#0101DF')\n", " arr=canevas.create_oval(S_a[0]-rayon,S_a[1]-rayon,S_a[0]+rayon,S_a[1]+rayon,fill='#FF8000')\n", " fenetre.after(250)\n", " fenetre.update()\n", " break\n", " fenetre_fin=Tk()\n", " for k in range(3) :\n", " texte=Label(fenetre_fin,text=\"Algorithme terminé !!\",font='Arial 20',fg=\"red\")\n", " texte.pack()\n", " fenetre_fin.after(300)\n", " fenetre_fin.update()\n", " texte.destroy()\n", " fenetre_fin.after(200)\n", " fenetre_fin.update()\n", " \n", " texte=Label(fenetre_fin,text=\"Algorithme terminé !!\",font='Arial 20',fg=\"red\") \n", " texte.pack () \n", " b = Button(fenetre_fin, text ='Fermer', command =fenetre_fin.quit)\n", " b.pack(side =BOTTOM)\n", " fenetre_fin.mainloop()\n", " fenetre_fin.destroy() \n", " \n", "def Trace_Arete(M,N,couleur='blue') :\n", " \"\"\"couleur bleue par défaut, on changera la couleur lors du parcours dans le graphe \"\"\"\n", " norme=((M[0]-N[0])**2+(M[1]-N[1])**2)**(0.5)\n", " Ligne=[[M[0]+rayon*(N[0]-M[0])/norme, M[1]+rayon*(N[1]-M[1])/norme],\n", " [N[0]-rayon*(N[0]-M[0])/norme,N[1]-rayon*(N[1]-M[1])/norme]]\n", " return canevas.create_line(Ligne[0][0],Ligne[0][1],Ligne[1][0],Ligne[1][1],width=3,fill=couleur)\n", " \n", " \n", "### Interface\n", "\n", "Taille_largeur=800\n", "Taille_hauteur=450\n", "fenetre = Tk()\n", "titre=Label(fenetre,text=\"La recherche en profondeur dans un graphe\",fg=\"red\",font=\"Arial 16 italic\")\n", "titre.pack(side=TOP)\n", "canevas = Canvas(fenetre, width =Taille_largeur, height =Taille_hauteur, bg ='#A9F5F2')\n", "\n", " \n", "canevas.pack(side =TOP, padx =5, pady =5)\n", "\n", "bouton_quitter= Button(fenetre, text=\"Quitter\", command=fenetre.quit)\n", "bouton_quitter.pack(side=RIGHT)\n", "\n", "bouton_graphe= Button(fenetre, text=\"Construire le graphe\", command=Graphe)\n", "bouton_graphe.pack(side=RIGHT)\n", "\n", "\n", "fenetre.mainloop()\n", "fenetre.destroy()\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Autres modes de recherche dans un graphe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Distance sur les sommets" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On considère un graphe $G=(S,{\\cal A})$, où $S$ est l'ensemble des sommets et ${\\cal A}$ est l'ensemble des arêtes.\n", " \n", "Pour tout couple $(a,b)$ de sommets, on définit la distance $d(a,b)$ qui sépare $a$ et $b$ par :\n", "\n", "$\\bullet$ s'il existe un chemin d'arêtes $(s_0,\\cdots,s_k)$ reliant $a=s_0$ à $b=s_k$, on choisit parmi tous les chemins possibles, un chemin de longueur $k$ minimale. On pose alors $d(a,b)=k$\n", "\n", "$\\bullet$ s'il n'existe aucun chemin reliant $a$ à $b$, on pose $d(a,b)=+\\infty$.\n", "\n", "On vient alors de définir une **distance** sur l'ensemble $S$ car $d(\\cdot,\\cdot)$ prend des valeurs positives, lorsque le graphe est non orienté, $d(a,b)=d(b,a)$, $d(a,b)=0\\Longleftrightarrow a=b$ et pour tous sommets $a$, $b$ et $c$ :\n", "$$d(a,c)\\leq d(a,b)+d(b,c)$$\n", "\\n car un chemin minimal reliant $a$ à $b$, et un chemin minimal reliant $b$ à $c$, fournit par concaténation un chemin de $a$ vers $c$ (transitant via $b$) de longueur supérieure ou égale à $d(a,b)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sphères" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour tout sommet $s\\in S$, pour tout entier naturel $k$, on note ${\\cal S}(s,k)$ la **sphère** de centre $s$ et de rayon $k$ comme :\n", " $${\\cal S}(s,k)=\\Bigl\\{a\\in S ~|~d(s,a)=k\\Bigr\\}.$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Principe de la recherche en largeur " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le problème consiste, étant donné un graphe $G$ dont les sommets et les arêtes sont données, un sommet de départ $a$ et un sommet d'arrivée $b$ à répondre aux deux questions suivantes :\n", "\n", "$\\quad$ $\\longrightarrow$ existe-t-il un chemin d'arêtes reliant $a$ vers $b$ ?\n", "\n", "$\\quad$ $\\longrightarrow$ si oui, quels sont les chemins realisant le minimum de distance $d(a,b)$ ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'algorighme est le suivant :" ] }, { "cell_type": "raw", "metadata": {}, "source": [ "LS initialisée à [[a]] # sphère de rayon nul\n", "New_LS initialisée à [a]\n", "\n", "Test initialisé à VRAI\n", "\n", "TANT QUE (b hors de LS et Test=VRAI) :\n", "\n", " Test mis à FAUX\n", " \n", " RES mis à []\n", " \n", " POUR point parcourant NEW_LS :\n", " POUR sommet parcourant la sphère de centre point et de rayon 1 :\n", " SI sommet hors de LS :\n", " Test mis à VRAI # un nouveau point vient d'être trouvé\n", " mettre sommet dans RES\n", " fin SI\n", " fin POUR\n", " fin POUR\n", " \n", " New_LS remplacé par RES\n", " ajouter [RES] dans LS # LS contient une nouvelle sphère de centre a\n", " \n", "fin TANT QUE \n", "\n", "SI TEST=FAUX :\n", " 'pas de solution au problème'\n", "\n", "SINON :\n", " CHEMIN=[b]\n", " éliminer le dernier élément de LS\n", " parcourir les sommets du dernier élément de LS pour trouver un sommet s_{k-1} relié à b\n", " ajouter s_{k-1} à gauche de CHEMIN\n", " éliminer le dernier élément de LS\n", " parcourir les sommet du dernier élément de LS pour trouver un sommet s_{k-2} relié à s_{k-1}\n", " ajouter s_{k-2} à gauche de Chemin \n", " recommencer jusqu'à obtenir le point a et l'ajouter à gauche de CHEMIN\n", "fin SINON\n", "\n", "La liste CHEMIN fournit une solution au problème de chemin minimal reliant a à b.\n", " \n" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Interface implémentant les recherches en profondeur et en largeur dans un labyrinthe" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Longueur de la trajectoire en profondeur : 125\n", "Longueur de la trajectoire en largeur : 75\n" ] } ], "source": [ "from pylab import *\n", "from tkinter import *\n", "\n", "\n", "### calibrage de la taille du canevas\n", "c=20\n", "largeur=60\n", "hauteur=30\n", " \n", "\n", "Taille_largeur=c*largeur\n", "Taille_hauteur=c*hauteur\n", "\n", "### initialisation : aucun obstacle\n", "Liste_Cases=[[i,j] for i in range(largeur+1) for j in range(hauteur+1)]\n", "\n", "\n", "### initialisation : aucune case remplie dans la trajectoire\n", "Cases_Marquees=[]\n", "\n", "### initialisation : case en dehors du canevas\n", "Case_Dep=[-1,0]\n", "Case_Arr=[-1,0]\n", "\n", "def click_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c) # index de la case cliquée\n", " j=int(y/c) \n", " \n", " if [i,j] in Liste_Cases :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')\n", " Liste_Cases.remove([i,j])\n", " ### création de la case noire d'obstacle\n", " ### comptabilisation dans Liste_Cases\n", "\n", "\n", "def declick_case(event) :\n", " global Liste_Cases\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " \n", " if not([i,j] in Liste_Cases) :\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='white')\n", " Liste_Cases.append([i,j])\n", " ### effets contraires à l'autre commande\n", "\n", "Test_bouton_dep=True\n", "\n", "def obstacles() :\n", " global b2,b3,Test_bouton_dep\n", " canevas.bind(\"\", click_case)\n", " canevas.bind(\"\", declick_case)\n", " b2.destroy() # on détruit le widget 'Mettre les obstacles manuellement'\n", " if Test_bouton_dep :\n", " \n", " b3=Button(fenetre,text='Mettre la case de départ',command=depart)\n", " b3.pack(side =RIGHT, padx =3, pady =3)\n", " Test_bouton_dep=False\n", "\n", "def obstacles_alea():\n", " global b_alea,Liste_Cases,Test_bouton_dep,b3\n", " for i in range(largeur+1) :\n", " for j in range(hauteur+1) :\n", " if binomial(1,0.35) :\n", " Liste_Cases.remove([i,j])\n", " canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='black')\n", " b_alea.destroy()\n", " if Test_bouton_dep :\n", " b3=Button(fenetre,text='Mettre la case de départ',command=depart)\n", " b3.pack(side =RIGHT, padx =3, pady =3)\n", " Test_bouton_dep=False\n", " \n", "Nbre_choix=0\n", "\n", "def click_depart(event) :\n", " global Liste_Cases,Case_Dep,Case_Arr,Cases_Marquees,b3,Nbre_choix,b4\n", " \n", " canevas.bind(\"\", inutile) # on désactive le clic droit\n", " ### on aurait pu mettre le .bind en mémoire et détruire cette mémoire par .destroy()\n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " if [i,j] in Liste_Cases : # case cliquée blanche initialement\n", " Nbre_choix+=1 # comptabilisation du choix\n", " if Case_Dep != [-1,0] : # ce n'est pas le premier choix\n", " canevas.delete(Cases_Marquees[0][1]) # destruction de la case graphique\n", " Cases_Marquees.pop() # suppression de la case de départ de la Cases_Marquees\n", " Case_Dep=[i,j]# on met à jour la case de départ\n", " Cases_Marquees.append([[i,j],canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='green')]) \n", " # on met à jour la Cases_Marquees\n", " if Case_Dep!=[-1,0] and Nbre_choix == 1 : # une case déjà choisie\n", " ### on détruit le widget 'Mettre la case de départ à la première bonne case cliquée\n", " b3.destroy()\n", " \n", " b3=Button(fenetre,text=\"Mettre la case d'arrivée\",command=sortie)\n", " b3.pack(side =RIGHT, padx =3, pady =3) \n", " Nbre_choix=0 # on remet à jour \n", " ### on crée un nouveau widget mais une seule fois !!\n", " \n", "def depart() :\n", " global Case_Dep,Case_Arr,b2,b_alea\n", " try :\n", " b2.destroy()\n", " except :\n", " pass\n", " try :\n", " b_alea.destroy()\n", " except :\n", " pass\n", " \n", " canevas.bind(\"\", click_depart)\n", "\n", "def inutile(event) :\n", " pass \n", "\n", "\n", "def detruit() :\n", " global Liste_Cases,b3,b4\n", " try :\n", " b3.destroy()\n", " except:\n", " pass\n", " try :\n", " b4.destroy()\n", " except:\n", " pass\n", " try :\n", " for case in Liste_Cases :\n", " if not(case in [Case_Dep,Case_Arr]) :\n", " x,y=case\n", " canevas.create_rectangle(x*c, y*c, (x+1)*c, (y+1)*c, fill='white')\n", " except :\n", " pass\n", " \n", " \n", " \n", "\n", "def parcourir_profondeur() :\n", " \"\"\" implémente l'algorithme de parcours en profondeur \"\"\"\n", " global Liste_Cases,Case_Dep,Case_Arr,Cases_Marquees,b3,b4,Cases_Libres\n", " canevas.bind(\"\", inutile)\n", " detruit()\n", " \n", " Cases_Libres=Liste_Cases.copy()\n", " Cases_Libres.remove(Case_Dep)\n", " Pile=[Case_Dep]\n", " \n", " while Pile!=[] and Pile[-1]!=Case_Arr :\n", " i,j=Pile[-1]\n", " \n", " for k in [-1,1] :\n", " if ([i+k,j] in Cases_Libres ) : #nouvelle case libre\n", " Pile.append([i+k,j])\n", " break\n", " elif ([i,j+k] in Cases_Libres) : #nouvelle case libre\n", " Pile.append([i,j+k])\n", " break\n", " if Pile[-1]==[i,j] : #il n'y a pas eu d'empilement ; on doit désempiler\n", " r,s=Pile.pop()\n", " if [r,s]!=Case_Dep :\n", " canevas.create_rectangle(r*c, s*c, (r+1)*c, (s+1)*c, fill='orange')\n", " else :\n", " r,s=Pile[-1]\n", " if [r,s]!=Case_Arr: \n", " canevas.create_rectangle(r*c, s*c, (r+1)*c, (s+1)*c, fill='cyan')\n", " Cases_Libres.remove([r,s])\n", " \n", " fenetre.update()\n", " fenetre.after(10)\n", " ## on traite maintenant la pile pour l'optimiser :\n", " \n", " if Pile!=[] :\n", " Chemin=[Case_Dep]\n", " \n", " \n", " while Chemin[-1]!=Case_Arr:\n", " i,j=Chemin[-1]\n", " index_max=len(Pile)-1\n", " while abs(i-Pile[index_max][0])+abs(j-Pile[index_max][1])!=1 :\n", " index_max-=1\n", " Chemin.append(Pile[index_max])\n", " \n", " for point in Chemin[1:-1]:\n", " r,s=point\n", " canevas.create_rectangle(r*c, s*c, (r+1)*c, (s+1)*c, fill='magenta')\n", " fenetre.update()\n", " fenetre.after(100)\n", " print('Longueur de la trajectoire en profondeur :',len(Chemin))\n", " else :\n", " print('Pas de chemin possible par la recherche en profondeur.') \n", " \n", " \n", " b3=Button(fenetre,text=\"Lancer le parcours en largeur\",command=parcourir_largeur)\n", " b3.pack(side =RIGHT, padx =3, pady =3) \n", " b4=Button(fenetre,text=\"Lancer le parcours en profondeur\",command=parcourir_profondeur)\n", " b4.pack(side =RIGHT, padx =3, pady =3) \n", " \n", " \n", "def parcourir_largeur() :\n", " \"\"\" implémente l'algorithme de parcours en largeur \"\"\"\n", " global Liste_Cases,Case_Dep,Case_Arr,Cases_Marquees,b3,b4\n", " canevas.bind(\"\", inutile)\n", " detruit()\n", " \n", " Cases_Libres=Liste_Cases.copy()\n", " Cases_Libres.remove(Case_Dep)\n", " New_Cases=[Case_Dep]\n", " Cases_Marquees=[New_Cases] # mise en mémoire des sphères marquées\n", " \n", " Test_new=True # test de nouvelles bases\n", " Test_end=True # test de fin de parcours\n", " while Test_new and Test_end :\n", " Test_new=False\n", " \n", " New_Sphere=[]\n", " for case in New_Cases :\n", " I,J=case\n", " for point in [[I+k,J] for k in [-1,1] if [I+k,J] in Cases_Libres]+[[I,J+k] for k in [-1,1] if [I,J+k] in Cases_Libres] : \n", " Test_new=True\n", " x_p,y_p=point\n", " if point!=Case_Arr:\n", " canevas.create_rectangle(x_p*c, y_p*c, (x_p+1)*c, (y_p+1)*c, fill='cyan')\n", " else :\n", " Test_end=False\n", " New_Sphere.append(point)\n", " Cases_Libres.remove(point)\n", " New_Cases=New_Sphere.copy()\n", " Cases_Marquees.append(New_Sphere)\n", " fenetre.update()\n", " fenetre.after(100)\n", " \n", " if not(Test_end) :# sortie de boucle car on arrive à Case_Arr\n", " Chemin=[Case_Arr] # on remonte les sphères jusqu'au départ\n", " position=Chemin[0]\n", " while position!=Case_Dep :\n", " Cases_Marquees.pop() # on elève la dernière sphère\n", " for point in Cases_Marquees[-1] :\n", " if abs(point[0]-position[0])+abs(point[1]-position[1])==1 : # cases voisines \n", " Chemin=[point]+Chemin\n", " x_p,y_p=point\n", " if point!=Case_Dep :\n", " canevas.create_rectangle(x_p*c, y_p*c, (x_p+1)*c, (y_p+1)*c, fill='magenta')\n", " break # on arrête le parcours dans la sphère\n", " position=point.copy() # on met à jour\n", " fenetre.update()\n", " fenetre.after(100)\n", " print('Longueur de la trajectoire en largeur :',len(Chemin)) \n", " else : \n", " print('Pas de chemin possible par la recherche en largeur.')\n", " b3=Button(fenetre,text=\"Lancer le parcours en largeur\",command=parcourir_largeur)\n", " b3.pack(side =RIGHT, padx =3, pady =3) \n", " b4=Button(fenetre,text=\"Lancer le parcours en profondeur\",command=parcourir_profondeur)\n", " b4.pack(side =RIGHT, padx =3, pady =3) \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "def sortie() :\n", " \n", " global Case_Dep,Case_Arr,b2,b_alea,b3\n", " try :\n", " b2.destroy()\n", " except :\n", " pass\n", " try :\n", " b_alea.destroy()\n", " except :\n", " pass\n", " \n", " canevas.bind(\"\", click_sortie) \n", " \n", "def click_sortie(event):\n", " global Liste_Cases,Case_Dep,Case_Arr,Cases_Marquees,b4,b3,Nbre_choix\n", " \n", " x=event.x\n", " y=event.y\n", " i=int(x/c)\n", " j=int(y/c) \n", " if [i,j] in Liste_Cases and [i,j]!=Case_Dep : # case cliquée blanche initialement\n", " Nbre_choix+=1 # comptabilisation du choix\n", " \n", " if Case_Arr != [-1,0] : # ce n'est pas le premier choix\n", " canevas.delete(Cases_Marquees[-1][1]) # destruction de la case graphique\n", " Cases_Marquees.pop() # suppression de la case d'arrivée de Cases_Marquees\n", " Case_Arr=[i,j]# on met à jour la case d'arrivée\n", " Cases_Marquees.append([[i,j],canevas.create_rectangle(i*c, j*c, (i+1)*c, (j+1)*c, fill='red')]) \n", " # on met à jour Cases_Marquees\n", " if Case_Arr!=[-1,0] and Nbre_choix == 1 : # une case déjà choisie\n", " ### on détruit le widget 'Mettre la case de départ à la première bonne case cliquée\n", " b3.destroy()\n", " \n", " b3=Button(fenetre,text=\"Lancer le parcours en largeur\",command=parcourir_largeur)\n", " b3.pack(side =RIGHT, padx =3, pady =3) \n", " b4=Button(fenetre,text=\"Lancer le parcours en profondeur\",command=parcourir_profondeur)\n", " b4.pack(side =RIGHT, padx =3, pady =3) \n", " ### on crée un nouveau widget mais une seule fois !!\n", " \n", " \n", " \n", "def dessiner_grille(): \n", " \"\"\" dessine la grille \"\"\"\n", " for i in range(largeur+2) :\n", " canevas.create_line(i*c,0,i*c,Taille_hauteur+c,width=1,fill='black')\n", " for j in range(hauteur+2) :\n", " canevas.create_line(0,j*c,Taille_largeur+c,j*c,width=1,fill='black')\n", " \n", " fenetre.update()\n", "\n", "\n", " \n", " \n", " \n", "########## interface graphique ##########\n", "\n", "\n", "fenetre = Tk()\n", "canevas = Canvas(fenetre, width =Taille_largeur+c, height =Taille_hauteur+c, bg ='white')\n", "\n", " \n", "canevas.pack(side =TOP, padx =5, pady =5)\n", "dessiner_grille()\n", "\n", "\n", "b1 = Button(fenetre, text ='Quitter', command =fenetre.quit)\n", "b1.pack(side =RIGHT, padx =3, pady =3)\n", "\n", "b2=Button(fenetre,text='Mettre les obstacles manuellement',command=obstacles)\n", "b2.pack(side =RIGHT, padx =3, pady =3)\n", "b_alea=Button(fenetre,text='Mettre les obstacles aléatoirement',command=obstacles_alea)\n", "b_alea.pack(side =RIGHT, padx =3, pady =3)\n", "fenetre.mainloop()\n", "fenetre.destroy()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 1 }