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]. |
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.
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)
|
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.
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()
|
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:
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. 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!"
|
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 |
|
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()
|
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. |