Seite 119 [119]
OCR
118 11 MULTIDIMENSIONAL EXPANSION OF THE ALGORYTHMICS... Linear search algorithms check, successively, every element of a list for the one that eguals the value we are looking for (target key). Binary searches repeatedly target the middle element of an ordered list reducing the search space by half after each step. We have chosen to illustrate the linear and binary searching strategies by flamenco dance choreographies (see figures 11.2-3). The list to be searched could be represented by a flamenco dancer sequence (women) and the target key by an extra dancer (man; the protagonist of the performance). Since each dancer wears the corresponding value on his/her back, these are not visible in the case of list elements but are visible on the back of the target key. In the case of linear searching, the result of the comparison operation between the target key and the current element of the searched list is yes (equal) or no (not equal). These yes/no comparisons could be illustrated by pieces of choreographies where the two dancers are dancing identically/differently (see Figure 11.2). In the case of binary searching, comparison operations result in one of the following three possibilities: less/greater/equal. To illustrate these variants, the corresponding dance couple could follow the same piece of choreography but in a slower/faster/in-synchrony rhythm (see Figure 11.3). Backtracking can be seen as an advanced searching strategy. It is a programming strategy for finding all (or some) solutions to a given computational problem that incrementally builds solutions and immediately abandons all those partial solutions that evidently cannot be completed to a valid final solution. The classic backtracking example is the so-called “eight queens puzzle”, which asks for all valid arrangements of eight chess queens on a chessboard (no queen attacks any other). We chose to illustrate the recursive version of the four-queen variant of this classic backtracking algorithm by classic ballet choreography (see Figure 11.4). The following pieces of choreographies are attached to each ballerina: — The queen comes to life on cell 0 of her row (new recursive call). — The queen dies on cell 5 of her row (the current recursive call ends). — The queen goes into “hibernation mode” (the current call is suspended; a new one begins at the next row). — The queen comes back from the “hibernation mode” (the suspended call from the previous row continues). — The current queen moves to the next cell of her row. — The current queen successively considers those queens that hibernate on previous rows. e These ones temporally wake up for a “pair of mutually attacking”/“pair of mutually non-attacking” dance. Additionally, four-queen “victory dances” illustrate the two valid solutions.
