by Paolo Russo, 06/12/2024
In this article I will describe a software technique (a class of algorithms) that I simply call "state space search" and that was known in the past with the strange name of dynamic programming. Frankly, I knew nothing of dynamic programming when I used the technique for the first time. I am still not completely sure what dynamic programming is all about; it looks strange to me that such an ambitious name was given to such a simple thing, so I still suspect that dynamic programming is something more than just state space search, but I did not dig any deeper in the subject.
In simple words, state space search is an optimization technique that is useful for solving problems where reaching a goal requires a number of steps and you must optimize the sequence of steps (the optimization criteria may vary). The most obvious algorithm to optimize the sequence consists in an extensive search in the step space: consider all possible variations for the first step; for each possible first step, consider all possible second steps; for each second step, consider all possible third steps and so on. This straightforward approach quickly leads to an exponential growth of computation and is thus unfeasible unless the number of steps is very low. The step space is too big to explore. But there is another approach: exploring the space of states, not steps. The state space is often much smaller. The reason is that many completely different sequences of steps may lead to the same intermediate result, i.e. to the same state; therefore, the search from that state onward can disregard the actual path of steps that was followed to reach that point. That is a simplification.
As a first example I will use the famous travelling salesman problem: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?". First I'll let you play with this problem with a Javascript software and the computer power of your own PC. Click with the mouse in the following rectangle. Every click places a city in that point of the rectangle. At every click the software tries to solve the problem the hard way, computing all possible paths: the computation required is O(N!). You won't have to click so many times before hitting the limit imposed by the computational power. Soon the progress bar will fill too slowly to be reasonably waited for. Just try:
Is it possible to optimize the search? Yes. Let's study the state space. Every line between two cities is a step. After each step, the state of the traveller consists in the city he is in and the subset of cities that he already visited. Encoding this state requires a number from 0 to N-1 for the current city and N bits for the subset, so the computation required to explore this space is O(N2*2N); the additional N factor is for generating all possible steps from any state. It is considerably less than O(N!). State search requires allocating and using a large array. Every array element should contain a single value that encodes the optimality value that you are trying to maximize or minimize. The search usually works backwards: first consider all states where the salesman has visited all cities but one, then all cities but two and so on. For every state you consider all possible steps from the state; since you already explored all states that you might reach from there, you already know how good each possible choice is. You choose the step that leads to the best value and store in the current state the combined value given by the step to be taken and the value of the destination state. In the travelling salesman problem, you store the overall distance to be travelled to complete the journey from that state. Just try this new version: you'll have to place more points to reach the computation power limit.
However, the travelling salesman problem is such an intractable problem anyway that it is not a very good example, despite its simplicity. The best usage cases for state space search are those situations where state space search solves the problem quickly and optimally. The first time I used this search was decades ago. I owned an Amiga 500 and I wanted to write a lossless image compression routine. Amiga images had typically a palette of up to 32 colors. Images were hand-drawn and often used a sort of two-color dithering to simulate a much higher number of color shades. Therefore, a simple run-length algorithm was not very useful. I wanted to divide the image in large squares of 64 by 64 pixels and then follow a quadtree approach: for every square, the compression routine had to decide two things: whether to reduce the palette or not, whether to split the square in four smaller squares or not. For example, if only 13 colors were used in a whole square, locally reducing the palette from 32 to 13 colors would have allowed to encode each pixel with only 3 or 4 bits instead of 5. However, in order to reduce the palette it is necessary to encode the new palette: 32 bits (13 ones and 19 zeroes). Is the palette remapping worth its cost? For a single square the answer is simple, but then the routine must decide whether to split the square and go on recursively or not. If the square is splitted, then at every subsquare the same decisions must be made and it is difficult to evaluate the net result of a palette remapping at the top level of the hierarchy of squares. Trying all possible combinations of decisions for all subsquares would take too much computation. State space search solved the problem. After every remap and/or split, the state consists only in the colors of the current palette, but only the number of colors actually matters for the search, so for every square the routine had to evaluate how many bits were required to encode that square for every possible set of decisions and for up to 32 different palette sizes.
However, this example is historical. I suppose you are not very interested in compressing 32-color images. I used state space search many more times in my life, but usage cases were a bit complex, small parts of much bigger projects. Therefore, just to give you a simple and convincing example of the power of state space search, I will apply it to a game that I played at school with my schoolmates back in the '80s. It had no name, but I'll call it School Pen Race. The game was played on the page of a squared notebook. One of the player drew a closed track with a pen. The track consisted in two lines, distant only a few squares from each other. Every player used a pen with an ink of a different color. The player that drew the track also drew a start/finish line. Every player drew a point on the start line at the intersection of the squary lines. That point represented the player's racing car. Then every player, at his/her turn, drew a segment to move his/her car. Segments had to be either horizontal, vertical or at 45°; their length had to be between 1 and 5 squares. However, inertia imposed two rules: the direction of the segment could vary only by 45° with respect to the previous segment; its length could vary only by 1. "Cars" frequently banged against the walls when turning at excessive speeds. Winning a race is a global optimization problem. Cutting the finish line with the smallest number of moves is a tough global optimization problem; if you try to solve it evaluating all possible sequences of moves, it is absolutely intractable, because complex tracks can require several tens of moves to complete. However, state space search easily solves the problem. The state space is not very large. The state of a car consists in its position (one per square in the track), its speed (1 to 5) and its direction (8 values). An array of a few tens of thousands elements is enough even for a very large squared notebook page. A well written Javascript software running in a good browser can explore this space in no time.
As you might have guessed, I'll let you play the School Pen Race against State Space Search right in this web page. Of course you cannot beat it, so I'll give you a significant advantage: your opponent will start a few turns after you: 3 for the simple track, 5 for the medium track and 8 for the complex track. Yes, there are three predefined tracks, but you can draw one yourself (same handicap as the complex track). You can save your custom track to a local file and load it afterwards if you want, but the program will save the current track anyway within the browser, just to prevent an accidental loss of your favourite and carefully drawn track (oh well, it took only a few lines to implement). In order to make graphics a bit clearer, I changed one aspect of the game: cars are in the middle of squares instead of at the edges. I'll also give you the possibility to backtrack, undoing a move (how generous I feel today!). Moves that crash the car are simply not accepted, so if the program feels unresponsive double check that you are not actually trying to crash the car. To use the program: choose a track or select "Draw one yourself" and draw one with the mouse (left button draws, right button cancels). When you are ready, click Race. You can move your car clicking on the control panel with the white arrows. It becomes visible when the mouse pointer is in the lower half of the page. It appears either in the bottom-left ot the bottom-right corner, depending on the mouse pointer position: this lets you easily move the panel away from the portion of the track where your car is passing. If your keyboard has a numeric pad, you can use it too instead of clicking the arrows, but you will have to use the Num Lock key, otherwise the browser might think that you are trying to navigate in the page with the arrow keys. Just have some fun and appreciate the devilish ability of your opponent driven by State Space Search. After playing, you might click the Solve button. It shows the current solution (in red) and ALL other solutions (in yellow), i.e. all other sequences of moves that solve the problem in the same minimum number of moves. You'll probably find that there is a huge number of them. In order to demonstrate the power of state space search, the program shows you ALL solutions, no matter their number (even if they are trillions). The code that does this thing it not exactly straightforward, since it cannot draw solutions one by one, but the mere fact that this thing can be done at all is quite an impressive demonstration of the power of the technique. The program also assigns a number to every solution, so you can choose which solution to show in red. Yes, you can type absurd numbers such as 173546253464726 (for a complex track) and it will work. Enjoy!
Backdi Paolo Russo, 06/12/2024
In quest'articolo descrivo una tecnica software (una classe di algoritmi) che chiamo semplicemente "ricerca nello spazio degli stati" e che è stata nota in passato con lo strano nome di programmazione dinamica. Francamente, non l'avevo neanche mai sentita nominare quando ho usato la tecnica per la prima volta. Non sono ancora del tutto sicuro che la programmazione dinamica consista proprio e solo in quello; mi pare strano che abbiano dato un nome così roboante a una cosa così semplice, quindi ho ancora il sospetto che la programmazione dinamica sia qualcosa di più di una semplice ricerca nello spazio degli stati, ma non ho indagato oltre.
In poche parole, la ricerca nello spazio degli stati è una tecnica di ottimizzazione utile per risolvere problemi dove per raggiungere un certo obiettivo bisogna compiere più passi distinti e il problema è ottimizzare la sequenza di passi (in base a qualche criterio di ottimizzazione; i criteri possono variare). L'algoritmo più ovvio per ottimizzare la sequenza consiste in una ricerca esaustiva nello spazio dei passi: si considerano tutte le possibili variazioni per il primo passo, poi, per ogni possibile primo passo, si considerano tutti i possibili secondi passi, poi per ognuno di questi si considerano tutti i possibili terzi passi e così via. Quest'approccio semplicissimo porta rapidamente a una crescita esponenziale del tempo di calcolo ed è quindi inutilizzabile a meno che il numero di passi sia molto basso. Lo spazio dei passi è troppo vasto da esplorare. Ma si può usare un altro approccio: esplorare lo spazio degli stati, non quello dei passi. Spesso quello degli stati è molto più piccolo, perché molte sequenze di passi totalmente diverse possono portare allo stesso risultato intermedio, cioè allo stesso stato; quindi, la ricerca da quel punto in poi può procedere ignorando la sequenza dei passi che hanno portato a quello stato. È una semplificazione.
Come primo esempio ricorrerò al famoso problema del commesso viaggiatore: "dato un insieme di città, e note le distanze tra ciascuna coppia di esse, trovare il tragitto di minima percorrenza che un commesso viaggiatore deve seguire per visitare tutte le città una ed una sola volta e ritornare alla città di partenza". Per prima cosa vi lascio giocare con questo problema con un programmino in Javascript e la potenza di calcolo del vostro PC. Cliccate con il mouse nel seguente rettangolo. Ogni click piazza una città in quel punto del rettangolo. Dopo ogni click il software cerca di risolvere il problema con la forza bruta, calcolando tutti i possibili percorsi: la complessità algoritmica è O(N!). Non dovrete cliccare poi tanto prima di andare a sbattere contro il limite imposto dal carico computazionale. Presto la barra di completamento inizierà a riempirsi troppo lentamente perché si possa ragionevolmente sopportare il ritardo. Provate pure:
Si può ottimizzare la ricerca? Sì. Esaminiamo lo spazio degli stati. Ogni linea tra due città è un passo. Dopo ogni passo, lo stato del viaggiatore consiste nella città in cui si trova e nel sottoinsieme di città che ha già visitato. Per codificare questo stato serve un numero da 0 a N-1 per la città corrente e N bit per il sottoinsieme, quindi la complessità computazionale per l'esplorazione di questo spazio è O(N2*2N); il fattore N aggiuntivo è per la generazione di tutti i passi possibili da quello stato. È parecchio meno di O(N!). La ricerca negli stati richiede l'allocazione e l'utilizzo di un grosso array. Ogni elemento deve contenere un singolo valore che codifica il valore del parametro da ottimizzare (massimizzare o minimizzare). Generalmente la ricerca procede all'indietro: prima si considerano tutti gli stati in cui il viaggiatore ha già visitato tutte le città tranne una, poi tutte le città tranne due e così via. Per ogni stato bisogna considerare tutti i passi possibili da quello stato; dato che tutti gli stati raggiungibili da lì sono stati già esplorati, si può facilmente determinare quanto sia valida ogni possibile scelta. Basta scegliere il passo che porta al valore migliore e memorizzare nello stato corrente il valore combinato dato dal passo scelto e il valore dello stato di destinazione. Nel problema del commesso viaggiatore si memorizza la distanza complessiva che bisogna ancora percorrere per completare il viaggio da quello stato. Provate pure questa nuova versione: dovrete piazzare più punti per raggiungere il limite computazionale.
Ad ogni modo, il problema del commesso viaggiatore rimane comunque un problema intrattabile e quindi non è un esempio molto istruttivo, nonostante la sua semplicità. Le situazioni in cui la ricerca nello spazio degli stati è più utile sono quelle in cui risolve il problema rapidamente ed esattamente. La prima volta che usai questa ricerca fu decenni fa. Avevo un Amiga 500 e volevo scrivere una routine di compressione di immagini senza perdita. Le immagini Amiga avevano tipicamente una paletta di 32 colori al massimo, erano disegnate a mano e impiegavano spesso una specie di retinatura a due colori per simulare un numero di sfumature di colore molto maggiore. Di conseguenza, un semplice algoritmo di run-length non sarebbe servito a molto. Volevo suddividere l'immagine in quadratoni di 64 per 64 pixel e poi adottare un approccio a quadtree: per ogni quadrato, la routine doveva decidere due cose: se ridurre la paletta o no, se suddividere ulteriormente il quadrato in quattro quadrati più piccoli o no. Per esempio, se in un intero quadrato erano usati solo 13 colori, ridurre localmente la paletta da 32 a 13 colori avrebbe consentito di codificare ogni pixel con solo 3 o 4 bit invece di 5. Tuttavia, per ridurre la paletta bisognava codificare la nuova: 32 bit (13 uni e 19 zeri). Ne vale la pena? Per un singolo quadrato la risposta è semplice da trovare, ma poi la routine deve decidere se suddividere il quadrato e procedere ricorsivamente o no. Se il quadrato viene suddiviso, bisogna poi prendere le stesse decisioni per ogni quadrato componente ed è difficile valutare le conseguenze di un rimappaggio della paletta al livello più alto di una gerarchia di quadrati. Valiutare tutte le possibili combinazioni di decisioni per tutti i quadrati della gerarchia richiederebbe troppi calcoli. La ricerca nello spazio degli stati risolse il problema. Dopo ogni rimappatura e/o suddivisione, lo stato consiste solo nei colori della paletta corrente, ma solo il numero dei colori conta ai fini della ricerca, quindi per ogni quadrato la routine doveva valutare quanti bit erano richiesti per codificare quel quadrato per ogni possibile insieme di decisioni e per 32 possibili dimensioni della paletta.
Ad ogni buon conto, quest'esempio è solo una curiosità storica. Non credo che vi interessi molto comprimere immagini a 32 colori. Ho usato la ricerca nello spazio degli stati molte altre volte nella vita, ma le situazioni di utilizzo erano un po' complicate: piccole parti di progetti molto più grossi. Di conseguenza, giusto per darvi un esempio semplice e convincente della potenza della ricerca nello spazio degli stati, la applicherò a un gioco a cui giocavo a scuola con i miei compagni nei lontani anni '80. Non aveva un nome, ma lo chiamerò Corsa delle penne. Il gioco si giocava sulla pagina di un quaderno a quadretti. Uno dei giocatori disegnava a penna una pista chiusa, consistente in due linee, distanti solo pochi quadretti l'una dall'altra. Ogni giocatore usava una penna con inchiostro di colore diverso. Il giocatore che disegnava la pista tracciava anche la linea di partenza e di arrivo. Ogni giocatore tracciava un punto sulla linea di partenza, all'intersezione delle linee dei quadretti, che rappresentava la sua vettura da corsa; poi ogni giocatore, a turno, tracciava un segmento per muovere la sua vettura. I segmenti dovevano essere orizzontali, verticali o a 45° e dovevano essere lunghi da 1 a 5 quadretti. Tuttavia, l'inerzia imponeva due regole: la direzione di un segmento poteva variare solo di 45°, e la sua lunghezza solo di 1, rispetto al segmento precedente. Le "auto" sbattevano sovente contro i bordi della pista quando i giocatori prendevano le curve a velocità eccessive. Vincere una gara è un problema di ottimizzazione globale. Tagliare la linea del traguardo con il minimo numero di mosse è un problema tosto di ottimizzazione globale; se si tenta di risolverlo calcolando tutte le possibili sequenze di mosse, è assolutamente intrattabile, perché le piste più complesse possono richiedere parecchie decine di mosse per percorrerle. D'altro canto, la ricerca nello spazio degli stati risolve il problema facilmente. Lo spazio degli stati non è molto vasto. Lo stato di una vettura consiste nella sua posizione (una possibile per ogni quadretto nella pista), la sua velocità (da 1 a 5) e la sua direzione (8 valori possibili). Un array di poche decine di migliaia di elementi è abbastanza anche per un foglio a quadretti molto grande. Un software in Javascript ben scritto che gira in un buon browser può esplorare questo spazio in una frazione di secondo.
Come potreste aver immaginato, potete giocare alla corsa delle penne contro la ricerca nello spazio degli stati in questa stessa pagina web. Ovviamente non potreste mai batterla, quindi vi darò un bel vantaggio: il vostro avversario partirà alcuni turni dopo di voi: 3 per la pista semplice, 5 per la media e 8 per quella complessa. Sì, ci sono tre piste predefinite tra cui scegliere, ma potete anche disegnarvene una voi (con lo stesso handicap della pista complessa). Potete salvare su file locale (sul vostro PC) la vostra pista e ricaricarla in seguito, se volete, ma il programma salva comunque la pista corrente all'interno del browser, giusto per evitarvi di perdere accidentalmente la vostra pista preferita e faticosamente disegnata (oh, be', implementare anche questo salvataggio automatico mi costava solo poche righe). Ho cambiato un aspetto del gioco per rendere la grafica un po' più chiara: le vetture sono puntini nel bel mezzo dei quadretti invece che ai loro angoli. Avete anche la possibilità di tornare indietro, annullando l'ultima mossa (eh, oggi mi sento generoso!). Le mosse che mandano l'auto a sbattere non vengono accettate, quindi se il programma sembra non rispondere ai comandi controllate bene di non stare cercando di demolire la vettura. Per usare il programma: scegliere una pista o selezionare l'opzione "Disegnane una" e disegnarne una con il mouse (il pulsante di sinistra traccia, quello di destra cancella). Una volta finito, cliccare su Gara. Potete muovere la vostra vettura cliccando sul pannello di controllo con le frecce bianche. Diventa visibile quando il puntatore del mouse si trova nella metà inferiore della pagina; appare nell'angolo in basso a sinistra o in quello in basso a destra, in base a dove si trova il puntatore del mouse: in questo modo potete facilmente spostare il pannello dove non dà fastidio. Se la vostra tastiera ha un tastierino numerico, potete usare quello invece di cliccare sulle frecce, ma dovrete usare il tasto Bloc Num, altrimenti il browser potrebbe pensare che state cercando di navigare nella pagina con i tasti cursore. Divertitevi e apprezzate l'abilità infernale del vostro avversario guidato dalla ricerca nello spazio degli stati. Dopo la corsa, o invece di giocare, si può cliccare sul bottone Risolvi, che mostra la soluzione corrente (in rosso) e anche TUTTE le altre soluzioni (in giallo), cioè tutte le altre sequenze di mosse che risolvono il problema nello stesso numero minimo di mosse. Probabilmente vedrete che ce n'è un gran numero. Allo scopo di dimostrare la potenza della ricerca nello spazio degli stati, il programma mostra TUTTE le soluzioni equivalenti, non importa quante siano (anche miliardi di miliardi). Il codice che lo fa non è proprio banalissimo, dato che non può certo permettersi di disegnare le soluzioni una a una, ma già il semplice fatto che sia possibile farlo costituisce una dimostrazione abbastanza impressionante della potenza della tecnica. Il programma assegna anche un numero a ogni soluzione, quindi potete scegliere quale soluzione mostrare in rosso. Potete anche inserire numeracci assurdi come 173546253464726 (per una pista complessa) e funzionerà. Divertitevi!
Indietro