deutsch     english    français     Imprimer

 

10.4 PLUS COURT CHEMIN, PROBLÈME DES 3 RÉCIPIENTS

 

 

INTRODUCTION

 

De nombreuses solutions algorithmiques ont été développées à partir de l’expérience quotidienne, y compris le retour sur trace. Comme vous l’avez compris, l’ordinateur choisit un coup parmi tous les coups permis et poursuit ainsi de manière parfaitement mécanique et cohérente. Si l’ordinateur se retrouve bloqué dans une impasse, il annule les coups précédents. Cette stratégie s’apparente au tâtonnement dans le contexte de la vie quotidienne et il est bien connu qu’elle n’est souvent pas optimale du tout. Il serait bien préférable de choisir le prochain coup le plus intelligent possible pour se rapprocher du but recherché [plus... En informatique, on appelle cela une recherche heuristique].

CONCEPTS DE PROGRAMMATION: Tâtonnement, graphe comportant des cycles, retour sur trace

 

 

GRAPHES COMPORTANT DES CYCLES

 

Lors du parcours d’un graphe, il peut arriver que l’on se retrouve en un nœud qui a déjà été visité quelques étapes plus tôt. Prenons l’exemple du réseau de métro souterrain d’une grande métropole dont les gares comportent de nombreuses liaisons différentes. Ce réseau permet d’atteindre une gare A à partir d’une gare B de différentes manières et l’on pourrait rapidement se retrouver à tourner en rond sans jamais atteindre la gare souhaitée. Prenons l’exemple du graphe suivant comportant 5 nœuds tous reliés deux à deux par une arête.

Les nœuds sont identifiés par les nombres 0 à 4. Comme vous l’aurez compris, il est fort probable que le simple algorithme de retour sur trace ne parvienne pas à trouver le chemin reliant A à B s’il reste bloqué dans un cycle. Il suffit cependant d’un remède facile à implémenter : il suffit de vérifier que le prochain voisin que l’algorithme s’apprête à visiter ne figure pas encore dans la liste visited avant d’effectuer l’appel récursif à search(). S’il est présent, il faut simplement ignorer ce nœud et continuer l’algorithme avec le nœud suivant. Avec cette correction, tous les 16 chemins possibles entre A et B sont imprimés dans la console.

 


def getNeighbours(node):
    return range(0, node) + range(node + 1, 5)

def search(node):
    global nbSolution
    visited.append(node)  # node marked as visited

    # Check for solution
    if node == targetNode:
        nbSolution += 1
        print nbSolution, ". Route:", visited
        # don't stop to get all solutions
        
    for neighbour in getNeighbours(node):
        if neighbour not in visited: # Check if already visited
            search(neighbour) # recursive call
    visited.pop() 

startNode = 0
targetNode = 4
nbSolution = 0
visited = []
search(startNode)
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

En vérifiant au préalable si un nœud a déjà été visité, il est possible d’utiliser le retour sur trace dans un graphe comportant des cycles. Si l’on oublie d’effectuer cette vérification, le programme va se planter et lever une erreur d’exécution due à un débordement de la pile d’appels récursifs (appels récursifs infinis).

 

 

PLUS COURT CHEMIN, SYSTÈME DE NAVIGATION

 

Chercher son chemin pour passer d’un point A à un point de destination B est un problème récurrent dans la vie quotidienne. Comme il y a de nombreux chemins qui mènent de A à B (et non seulement à Rome), il est également important de déterminer un certain critère (longueur du chemin, durée du voyage, qualité de la route, paysages, coûts etc…) dans le but de trouver le chemin optimal [plus... Trouver le plus court chemin d’après un certain critère d’optimalité constitue un algorithme
classique. Le célèbre informaticien E. W. Dijkstra a trouvé une solution élégante déjà en 1959
].

Dans le programme développé ci-après, on se concentre sur les bases. Il traite le cas d’un réseau de métro ne comportant que 6 arrêts dans une ville fictive. Les nœuds du graphe sont identifiés par le nom des stations qui commencent par les lettres A, B, C, D, E et F. On aurait donc également pu identifier les stations par les lettres A, B, C, D, E, F ou par un numéro de station. Pour stocker les relations de voisinage entre stations, on utilise un dictionnaire dont chaque élément est constitué d’une station en guise de clé et de la liste de toutes les stations qui lui sont adjacentes dans le réseau en guise de valeur. Au lieu d’utiliser une fonction getNeighbours(), ont fait directement usage d’un dictionnaire neighbours.

De manière similaire, les distances séparant les stations sont stockées dans un autre dictionnaire distances analogue au dictionnaire neighbours.

Il faut également recourir à un dictionnaire locations pour stocker les coordonnées x et y des emplacements des stations.

L’essentiel du programme est une copie exacte de l’algorithme de retour sur trace utilisé précédemment.  De plus, il faut également quelques fonctions auxiliaires pour permettre la représentation graphique.

On peut utiliser une boîte de dialogue pour récupérer la saisie utilisateur et écrire la sortie dans la barre d’état. De plus, le programme dessine le chemin optimal dans le graph reliant les stations. 

 

 

 

from gamegrid import *

neighbours = {
    'Althaus':['Bellevue', 'Dom', 'Enge', 'Friedhof'], 
    'Bellevue':['Althaus', 'City', 'Dom'], 
    'City':['Bellevue', 'Dom', 'Friedhof'], 
    'Dom':['Althaus', 'Bellevue', 'City', 'Enge', 'Friedhof'], 
    'Enge':['Althaus', 'Dom'], 
    'Friedhof':['Althaus', 'City', 'Dom']}

distances = {
   ('Althaus', 'Bellevue'):5, ('Althaus', 'Dom'):9, 
   ('Althaus', 'Enge'):6, ('Althaus', 'Friedhof'):15,
   ('Bellevue', 'City'):3, ('Bellevue', 'Dom'):13, 
   ('City', 'Dom'):4, ('City', 'Friedhof'):3, 
   ('Dom', 'Enge'):2, ('Dom', 'Friedhof'):12}

locations = {
    'Althaus':Location(2, 0), 
    'Bellevue':Location(0, 1), 
    'City':Location(1, 3), 
    'Dom':Location(4, 2), 
    'Enge':Location(5, 0), 
    'Friedhof':Location(3, 4)}

def getNeighbourDistance(station1, station2):
    if station1 < station2:
        return distances[(station1, station2)]
    return distances[(station2, station1)]

def totalDistance(li):
    count = 0
    for i in range(len(li) - 1):
        count += getNeighbourDistance(li[i], li[i + 1])
    return count

def drawGraph():
    getBg().clear()
    getBg().setPaintColor(Color.blue)
    for station in locations:
        location = locations[station]
        getBg().fillCircle(toPoint(location), 10) 
        startPoint = toPoint(location)
        getBg().drawText(station, startPoint)
        for s in neighbours[station]:
            drawConnection(station, s)
            if s < station:
                distance = distances[(s, station)]
            else:
                distance = distances[(station, s)]
            endPoint = toPoint(locations[s]) 
            getBg().drawText(str(distance), 
                   getDividingPoint(startPoint, endPoint, 0.5))
    refresh()
         
def drawConnection(startStation, endStation):
    startPoint = toPoint(locations[startStation])
    endPoint = toPoint(locations[endStation])
    getBg().drawLine(startPoint, endPoint)

def search(station):
    global trackToTarget, trackLength    
    visited.append(station)  # station marked as visited

    # Check for solution
    if station == targetStation:
        currentDistance = totalDistance(visited)
        if currentDistance < trackLength:
            trackLength = currentDistance
            trackToTarget = visited[:]
        
    for s in neighbours[station]:
        if s not in visited:  # if all are visited, recursion returns
            search(s) # recursive call
    visited.pop() # station may be visited by another path 

def init():
    global visited, trackToTarget, trackLength
    visited = []
    trackToTarget = [] 
    trackLength = 1000
    drawGraph()
    
makeGameGrid(7, 5, 100, None, "sprites/city.png", False)
setTitle("City Guide")
addStatusBar(30)
show()
init()
startStation = ""
while not startStation in locations:
    startStation = inputString("Start station")
targetStation = ""
while not targetStation in locations:
    targetStation = inputString("Target station")
search(startStation)
setStatusText("Shortest way from " + startStation + " to " + targetStation 
    + ": " + str(trackToTarget) + " Length = " + str(trackLength))
for i in range(len(trackToTarget) - 1):
    s1 = trackToTarget[i]
    s2 = trackToTarget[i + 1]
    getBg().setPaintColor(Color.black)
    getBg().setLineWidth(3)
    drawConnection(s1, s2)
refresh()   
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La recherche du plus court chemin au sein d’un graph constitue l’une des tâches élémentaires de la science de l’information. La solution que nous avons étudiée pour déterminer le plus court chemin atteint son but par retour sur trace mais présente le désavantage d’être extrêmement gourmande en ressources CPU. Il existe de bien meilleurs algorithmes pour trouver le plus court chemin qui évitent d’explorer systématiquement tous les chemins possibles. Le plus fameux d’entre eux est appelée "algorithme de Dijkstra".

 

 

LE PROBLÈME DES TROIS JERRICANS

 

Les casse-têtes consistant à diviser une quantité donnée en une fraction d’elle-même par mesure (en pesant, versant, etc …) fourmillent depuis des lustres dans les livres pour enfants et dans les magazines. Le célèbre problème des trois récipients est attribué au mathématicien français du 17e siècle Bachet de Méziriac et s’énonce comme suit:

Deux amis décident de partager de manière équitable huit litres de vin contenus dans un récipient de huit litres par vidage et transferts. Ils disposent également d’un récipient de cinq litres et d’un autre de trois litres tous dépourvus de graduation. Comment doivent-ils procéder et combien de transferts faut-il au minimum?

 

D’après la formulation du problème, il ne s’agit pas seulement de trouver la solution, ce qui est tout à fait faisable en réfléchissant la moindre, mais de déterminer toutes les solutions possibles et de trouver la plus courte. Sans ordinateur, cette tâche serait très fastidieuse. Rechercher toutes les solutions possibles comme dans le cas présent constitue une recherche exhaustive.

Pour commencer, on procède par retour sur trace, ce qui nécessite l’élaboration d’une structure de données appropriées pour stocker les états du jeu. Pour ce faire, on utilisera une liste de trois nombres décrivant le niveau de remplissage de chacun des récipients. L’état [1, 4, 3] signifie donc que le récipient de 8 litres contient 1 litre de vin, le récipient de 5 litres en contient 4 et le récipient de 3 litres en contient 3.

Une fois n’est pas coutume, on modélise les états du jeu par des nœuds dans un graphe et l’on considère le transfert des récipients vers un autre commune une transition d’un nœud du graphe vers un nœud qui lui est adjacent. Dans cette situation, comme dans tant d’autres, il est insensé de vouloir construire dès le début tout l’arbre de décision. Il est en effet préférable de ne déterminer les nœuds voisins du nœud actuel node par la fonction getNeighbours(node) que lorsque cela est nécessaire. Il faut partir de la considération suivante:

Peu importe la quantité de vin présente dans un récipient, il y a essentiellement 6 options différentes de transfert d’un récipient à l’autre. Pour chaque récipient, on peut soit vider totalement son contenu dans un autre récipient ou ne transférer que la quantité de vin correspondant au volume encore disponible dans le récipient de destination. On rassemble donc les nœuds correspondant à ces 6 possibilités de transfert dans la liste neighbours au sein de la fonction getNeighbours(). Pour déterminer les nœuds voisins de l’état courant, la fonction transfer(state, source, target) retourne l’état résultant d’un transfert du récipient source vers target. On considère pour ce faire autant la contenance maximale des récipients que le volume de vin qu’ils contiennent déjà.

Encore une fois, la fonction récursive search() utilise l’algorithme de retour sur trace.

def transfer(state, source, target):
    # Assumption: source, target 0..2, source != target
    s = state[:] # clone
    if s[source] == 0 or s[target] == capacity[target]:
        return s  # source empty or target full
    free = capacity[target] - s[target]
    if s[source] <= free: # source has enough space in target
        s[target] += s[source]
        s[source] = 0
    else:  # target is filled-up
        s[target] = capacity[target]
        s[source] -= free
    return s

def getNeighbours(node):
# returns list of neighbours
    neighbours = []
    t = transfer(node, 0, 1) # from 0 to 1
    if t not in neighbours:
       neighbours.append(t)
    t = transfer(node, 0, 2) # from 0 to 2
    if t not in neighbours:
        neighbours.append(t)
    t = transfer(node, 1, 0) # from 1 to 0
    if  t not in neighbours:
        neighbours.append(t)
    t = transfer(node, 1, 2) # from 1 to 2
    if t not in neighbours:
        neighbours.append(t)
    t = transfer(node, 2, 0) # from 2 to 0
    if t not in neighbours:
        neighbours.append(t)
    t = transfer(node, 2, 1) # from 2 to 1
    if t not in neighbours:
        neighbours.append(t)
    return neighbours

def search(node):
    global nbSolution    
    visited.append(node)

    # Check for solution
    if node == targetNode:
        nbSolution += 1
        print nbSolution, ". Route:", visited, ". Length:", len(visited)
        
    for s in getNeighbours(node):
        if s not in visited: 
            search(s)
    visited.pop() 
 
capacity = [8, 5, 3]
startNode = [8, 0, 0]
targetNode = [4, 4, 0]
nbSolution = 0
visited = []
search(startNode)
print "Done. Find the best  solution!"
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

Les solutions sont écrites dans la console et ne figurent pas dans ce texte pour vous permettre d’appréhender le problème sans a priori et de tenter de trouver les solutions par vous-mêmes avec un papier et un crayon. Après les avoir découvertes, vous constaterez qu’il y a 16 solutions dont la plus longue nécessite 16 transferts.

 

 

EXERCISES

 

1.


Simplifier le programme de navigation de telle sorte que les nœuds soient identifiés par les nombres 0, 1, 2, 3, 4, 5 et que neighbours soit une liste contenant des sous-listes de nœuds.

2.

Décrire le processus permettant de puiser d’un lac exactement 4 litres d’eau à l’aide d’un récipient de 3 litres et d’un récipient de 5 litres. Trouver la solution demandant le moins de transferts possibles. N’oubliez pas qu’il est possible de vider un récipient dans le lac

3.

Inventer un casse-tête de transfert dans le style de l’exercice précédent en vous assurant qu’il possède une solution. Demandez à vos amis de le résoudre.

 

   

MATÉRIAL SUPPLÉMENTAIRE


 

SYSTÈME DE NAVIGATION URBAIN À L’AIDE DE LA SOURIS

 

L’expérience utilisateur (UX = User eXperience) joue un rôle primordial dans n’importe quelle application professionnelle. Lors de la phase de conception, le développeur ou le concepteur ne doit pas tant se laisser guider par des considérations d’ordre techniques du domaine de la programmation mais bien plutôt en se mettant dans la peau d’un utilisateur lambda qui veut pouvoir utiliser l’application de la manière la plus intuitive possible et en ne recourant qu’à son bon sens. De nos jours, cela implique des interfaces intégrant une surface contrôlable à l’aide de la souris ou de gestes tactiles. Le développement de l’interface utilisateur nécessite souvent une partie non négligeable de l’effort global investi dans un projet de développement informatique.

Les systèmes de navigation adoptent de plus en plus les interfaces tactiles. Celles-ci adoptent cependant une logique relativement similaire au pilotage par la souris. De ce fait, nous allons modifier notre système de navigation urbain pour ajouter le support de la souris, de telle sorte que l’utilisateur puisse sélectionner le point de départ et celui d’arrivée à l’aide d’un clic de souris. Les résultats seront écrits aussi bien dans la barre de titre de la fenêtre que dans sa barre d’état. 


Le clic de la souris engendre un événement qui est géré dans la fonction de rappel pressEvent() que l’on enregistre avec la fonction makeGameGrid() grâce au paramètre nommé mousePressed. Il faut garder à l’esprit que le programme peut se trouver dans deux états différents suivant que l’utilisateur a déjà effectué un premier clic pour sélectionner le point de départ ou non. S’il a déjà effectué ce premier clic, le prochain clic servira à déterminer le point de destination souhaité. Il suffira de recourir un fanion booléen isStart pour distinguer ces deux états possibles. Ce dernier sera mis à True si le prochain clic est censé permettre la sélection du point de départ du trajet.

L’interface utilisateur devrait être conçue de telle manière qu’il soit possible de sélectionner plusieurs trajets d’affilée sans avoir à redémarrer le programme. De ce fait, il est nécessaire que le programme soit en mesure de retourner à un état initial bien défini. Ce processus qui est mené à bien par la fonction init() est appelé réinitialisation. Du fait que certains éléments sont initialisés automatiquement au démarrage du système, il n’est en aucun cas trivial d’implémenter à l’aide de fonctions définies par le programme lui-même un système de réinitialisation personnalisé permettant de retourner de manière répétée à un état initial propre. Les erreurs d’initialisation sont de ce fait très courantes en programmation en plus d’être généralement fâcheuses et difficiles à identifier puisque le programme se comporte souvent correctement durant les phases de test et ne commence à montrer des signes de dysfonctionnement que plus tard, lorsqu’il est mis en production.

from gamegrid import *

neighbours = {
    'Althaus':['Bellevue', 'Dom', 'Enge', 'Friedhof'], 
    'Bellevue':['Althaus', 'City', 'Dom'], 
    'City':['Bellevue', 'Dom', 'Friedhof'], 
    'Dom':['Althaus', 'Bellevue', 'City', 'Enge', 'Friedhof'], 
    'Enge':['Althaus', 'Dom'], 
    'Friedhof':['Althaus', 'City', 'Dom']}

distances = {
   ('Althaus', 'Bellevue'):5, ('Althaus', 'Dom'):9, 
   ('Althaus', 'Enge'):6, ('Althaus', 'Friedhof'):15,
   ('Bellevue', 'City'):3, ('Bellevue', 'Dom'):13, 
   ('City', 'Dom'):4, ('City', 'Friedhof'):3, 
   ('Dom', 'Enge'):2, ('Dom', 'Friedhof'):12}

locations = {
    'Althaus':Location(2, 0), 
    'Bellevue':Location(0, 1), 
    'City':Location(1, 3), 
    'Dom':Location(4, 2), 
    'Enge':Location(5, 0), 
    'Friedhof':Location(3, 4)}

def getNeighbourDistance(station1, station2):
    if station1 < station2:
        return distances[(station1, station2)]
    return distances[(station2, station1)]

def totalDistance(li):
    count = 0
    for i in range(len(li) - 1):
        count += getNeighbourDistance(li[i], li[i + 1])
    return count

def drawGraph():
    getBg().clear()
    getBg().setPaintColor(Color.blue)
    for station in locations:
        location = locations[station]
        getBg().fillCircle(toPoint(location), 10) 
        startPoint = toPoint(location)
        getBg().drawText(station, startPoint)
        for s in neighbours[station]:
            drawConnection(station, s)
            if s < station:
                distance = distances[(s, station)]
            else:
                distance = distances[(station, s)]
            endPoint = toPoint(locations[s]) 
            getBg().drawText(str(distance), 
                 getDividingPoint(startPoint, endPoint, 0.5))
    refresh()
         
def drawConnection(startStation, endStation):
    startPoint = toPoint(locations[startStation])
    endPoint = toPoint(locations[endStation])
    getBg().drawLine(startPoint, endPoint)

def search(station):
    global trackToTarget, trackLength    
    visited.append(station)  # station marked as visited

    # Check for solution
    if station == targetStation:
        currentDistance = totalDistance(visited)
        if currentDistance < trackLength:
            trackLength = currentDistance
            trackToTarget = visited[:]
        
    for s in neighbours[station]:
        if s not in visited:  # if all are visited, recursion returns
            search(s) # recursive call
    visited.pop() # station may be visited by another path 

def getStation(location):
    for station in locations:
        if locations[station] == location:
            return station
    return None # station not found

def init():
    global visited, trackToTarget, trackLength
    visited = []
    trackToTarget = [] 
    trackLength = 1000
    drawGraph()
    
def pressEvent(e):
    global isStart, startStation, targetStation
    mouseLoc = toLocationInGrid(e.getX(), e.getY())
    mouseStation = getStation(mouseLoc)
    if mouseStation == None:
        return
    if isStart:
        isStart = False
        init()
        setTitle("Click on destination  station")
        startStation = mouseStation
        getBg().setPaintColor(Color.red)
        getBg().fillCircle(toPoint(mouseLoc), 10) 
    else:
        isStart = True
        setTitle("Once again? Click on  starting station.")
        targetStation = mouseStation
        getBg().setPaintColor(Color.green)
        getBg().fillCircle(toPoint(mouseLoc), 10) 
        search(startStation)
        setStatusText("Shortest route from " + startStation + " to " 
            + targetStation + ": " + str(trackToTarget) + " Length = " 
            + str(trackLength))
        for i in range(len(trackToTarget) - 1):
            s1 = trackToTarget[i]
            s2 = trackToTarget[i + 1]
            getBg().setPaintColor(Color.black)
            getBg().setLineWidth(3)
            drawConnection(s1, s2)
            getBg().setLineWidth(1)
    refresh()
    
isStart = True
makeGameGrid(7, 5, 100, None, "sprites/city.png", False, 
             mousePressed = pressEvent)
setTitle("City Guide. Click on starting  station.")
addStatusBar(30)
show()
init()
Sélectionner le code (Ctrl+C pour copier, Ctrl+V pour coller)

 

 

MEMENTO

 

La partie algorithmique impliquant le retour sur trace demeure pratiquement inchangée. L’interface utilisateur impliquant le contrôle avec la souris est par contre relativement complexe malgré les facilités mises à disposition par les fonctions de rappel.

L’usage du mot-clé global peut facilement conduire à des erreurs d’initialisation du fait que les variables globales peuvent être créées depuis certaines fonctions et que l’on pourrait facilement oublier de les réinitialiser.