deutsch     english    français     Print

 

10.4 SHORTEST PATH, 3 JUGS PROBLEM

 

 

INTRODUCTION

 

Many important algorithmic solution methods were developed from the practice of daily life, including backtracking. As you have already learned, the computer chooses a game move from all the possibilities of allowed moves and consequently pursues it. If the computer runs into a dead end, it undoes previous moves. This solution strategy is called trial and error in the context of daily life, and it is known that it is not always optimal. It would be better to choose the next move as favorably as possible depending on the goal [more... In computer science, this is called a heuristic search].

PROGRAMMING CONCEPTS: Trial and error, graph with cycles, backtracking

 

 

GRAPH WITH CYCLES

 

When traversing a graph, it may happen that you arrive back at the same state after making a few steps. Think, for example, of the subway network of a big city where the stations have an interwoven structure. If you want to ride from point A to point B in that city, there are many different options and you could easily end up riding around in cycles. In preparation for such a navigation task, you look at a graph with 5 nodes where each node is connected to every other node.

The nodes are identified by a node number 0..4. As you have already seen, it is possible that the simple backtracking algorithm cannot find the path from a given node to another because it gets stuck in a cycle. However, you only need a small supplement to avoid this: Before you make the recursive call to search(), check in the list visited to see if the concerned neighboring nodes were already visited. If so, you can skip these neighbors. Now all 16 possible routes between nodes are written out in the program.

 


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)
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

By checking if a neighbor has already been visited, you can also make use of backtracking on graphs with cycles. If you forget to check this, your program will "hang", resulting in a bad run-time error due to overflowing of the function call memory.

 

 

SHORTEST PATH, NAVIGATION SYSTEMS

 

Trying to find a path from starting point A to a destination B is omnipresent in daily life. Since there are often many routes leading from A to B (not only to Rome), it is usually also important to determine a certain criterion (route length, traveling time, road quality, landmarks, cost, etc.) in order to find the optimal path [more... Finding the shortest path with a distance evaluation is one of the classical algorithms. An elegant solution was given in 1959 by the famous computer scientist EW Dijkstra.].

In your program, we will simply focus on the basics. Therefore, you choose a local network with only 6 places that you can regard as subway stations in a fictional city. The nodes of the graph are identified by the names of the stations. (The first letters of these names are A, B, C, D, E, F, so the stations could also be identified with these letters or with node numbers.) The indication of the neighboring stations is an allocation of a station name to a list of of names, which is why a dictionary with the station name as a key and the list of the neighboring stations as a value is perfectly suited for this. Instead of using a function getNeighbours(), you directly use a dictionary neighbours.

The distance between the stations are also stored analogously in a dictionary distances that has the two connected stations as a key and the distance as a value.

In order to enter these stations into a GameGrid, you still need a dictionary locations with the locations (x, y coordinates) of the stations.

The central part of your program is an exact replication of the backtracking algorithm used above. In addition, you need some auxiliary functions to represent it graphically.

You use an entry dialog for the user input and write the outputs to a status bar. Furthermore, you draw the optimal path in the graph of 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()   
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

The search for the shortest path in a graph is one of the basic tasks in computer science. The solution shown here achieves its goal with backtracking, but it is very CPU-intensive (meaning it takes a lot of processing power). There are much better algorithms for finding the shortest path where you do not have to systematically search for every route. The most famous is called "Dijkstra's algorithm".

 

 

THE THREE JUGS PROBLEM

 

Brain teasers in which a given quantity has to be divided into certain partial quantities by measuring (pouring, weighting, etc.) have already been found in children's books and magazines for centuries. The well-known three jugs problem is attributed to the French mathematician Bachet de Méziriac in the 17th century and goes as follows:

Two friends have decided to evenly divide up 8 liters of wine that is in an 8 liter jug by pouring it. In addition to the 8 liter jug, you have a 5 liter and a 3 liter jug. The jugs have no markings on them for measuring the contents. How should you proceed and how many pours are necessary, at minimum?

 

According to the problem description, it is not only a matter of finding the solution, which you might be able to do by thinking a bit, but finding all possible solutions, and therefore determining the shortest of them all. Without a computer, this would be very tiring. Searching for all solutions, such as in this example, is called an exhaustive search.

To begin with, you again proceed according to the previously tried solution strategy with backtracking. First invent a suitable data structure for the game states. For this, you use a list with three numbers that describes the current fill level of the three jugs. [1, 4, 3] should thus mean that the 8 liter jug currently contains 1 liter of wine, the 5 liter jug contains 4 liters, and the 3 liter jug contains 3 liters.

You can again model the game states as nodes in a graph and consider the pouring as a transition from one node to its neighboring node. Here, as in many other examples, it does not make sense to construct the entire game tree at the beginning. Instead, you can determine the neighboring nodes of a node node in the function getNeighbours(node) only when you actually need them during the game. You can begin with the following consideration:

Regardless of how much wine is in the jugs, there are basically 6 options of how you can pour: You take one of the jugs and either pour all of their contents or as much as there is space available in the second jug. You therefore collect the neighboring nodes of these 6 cases in the list neighbours in getNeighbours(). The function transfer(state, source, target) helps you to figure out the neighboring states of a particular state state and given jug numbers source and target after pouring from source to target. The jug sizes (maximum capacity) and the already contained quantity will be considered.
Again your recursive function search() uses the backtracking algorithm as you know it.

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!"
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

The solutions are written out to the output window. They are not published here so that you are able to approach the problem with an open mind and possibly first try to find the solution with pencil and paper. After they are revealed, you will see that there are 16 solutions, and 16 pours are necessary for the longest.

 

 

EXERCISES

 

1.


Simplify the navigation program so that the nodes are identified by the numbers 0, 1, 2, 3, 4, 5 and neighbours is a list with sublists.

2.

You should scoop exactly 4 liters of water from a lake with a 3 liter and 5 liter jug. Describe how you would proceed and find the shortest amount of pours it would take. Keep in mind that you can pour the water back into the lake again

3.

Invent a solvable pouring problem and give it to other people in your community as a brain teaser.

 

   

ADDITIONAL MATERIAL


 

CITY NAVIGATION WITH MOUSE SUPPORT

 

The graphical user interface plays a central role in any professional program. While designing it, the programmer has to be guided less by programmatic considerations but rather by putting themselves into the shoes of an unbiased user who uses the program with as little effort as possible and natural human logic. Today such an interface usually includes a graphical surface with mouse or touch controls. The task of developing the user interface can often take up a considerable amount of the total effort spent on a project in computer science.

Touch screens are becoming popular for navigation systems. However, their logic differs only slightly from programming for mouse control. Due to this, you will now alter your city navigation program to support mouse control, so that the user can select the starting and destination point with a mouse click. Output information will be written both to the title bar and to the status bar.

The mouse click triggers an event that is processed in the callback pressEvent(). You register these in makeGameGrid() using the named parameter mousePressed. You should remember that the program can be in two different states depending on whether the user will click on the starting station as the next action, or whether they have already done so and have to choose the target station next. A Boolean variable (a flag) isStart will suffice for this state change, which will be True when the starting station has to be chosen next.

The program should be structured so that the user can perform the route search multiple times without having to restart the program. Therefore, the program has to internally reset to a well-defined initial state. This is referred to as initialization and is best carried out with the function init(). Since certain initializations are performed automatically at the start up, it is by no means trivial to repeatedly reset a currently running program to a well-defined initial state using its own function. Initialization errors are therefore programming errors which are widespread, dangerous, and difficult to locate since the program often behaves correctly during testing and only later behaves incorrectly when put into operation.

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()
Highlight program code (Ctrl+C copy, Ctrl+V paste)

 

 

MEMO

 

The algorithmic part with the backtracking remains pretty much unchanged. The user interface with mouse control is quite complex, despite good support from callbacks.

Using global easily leads to initialization errors in Python, as global variables can be created in functions and you might later forget to reset their value.