Visualizza il feed RSS

Titolo provvisorio...

TAXIIIIII! (WAS: Algoritmo first-fit per bin-packing)

Valuta questo inserimento
di pubblicato il 06-04-2012 alle 17:51 (6751 Visite)
Su gentile (ma pressante) richiesta privata di alcuni lettori, dedico la presente blog entry a questo recente thread, che si rifà a questo problema.

Accontento volentieri i miei lettori, non certo per una malintesa captatio benevolentiae o per sciocca autoincensazione, ma perché questo genere di soluzione è assolutamente, solidamente paradigmatico del modo di pensare del Buon Programmatore, sano cultore della matematica discreta e computazionale.

Si tratta di un problema fortemente vincolato, che per natura va affrontato con una strategia tipo pigeonhole. Tale principio della piccionaia (noto anche come principio di Dirichlet o delle caselle postali, e detto "dei cassetti" o "del cassetto" in alcune traduzioni alquanto improprie) è un pilastro fondamentale della matematica discreta e degli insiemi finiti. In soldoni il principio afferma che, data una piccionaia con più piccioni che buche, esiste almeno una buca nella quale vi sono almeno due piccioni. Sembra fin troppo banale: ma se sicuramente l'enunciato è tale, non lo sono certo le conseguenze. Numerosi sono i casi nei quali l'applicazione di tale principio non è immediata.

Restando comunque ai casi ordinari e applicando pedissequamente tale principio si risolvono già moltissimi problemi di minimo, elementari e non. Tipico in letteratura, ad esempio, il problema dei calzini spaiati (straordinariamente carico di richiami autobiografici, ché i matematici, si sa, son sempre tipi strambi, goffi e bizzarramente vestiti nell'immaginario collettivo): se un cassetto contiene solamente calzini blu e neri di identica foggia, qual è il numero minimo di calzini che - operando al buio - dovrò prelevare per avere la certezza assoluta di uscire dalla stanza con una coppia di calzini del medesimo colore? La risposta è, ovviamente, tre. La dimostrazione è lasciata come banale esercizio per il lettore. Hint: in questo caso, i "piccioni" sono i calzini e le "buche" sono i due immaginari contenitori corrispondenti al colore. E - considerando gli stereotipi che circolano - garantiamo che i calzini, prima di esser riposti nel cassetto, sono stati lavati.

Allo stesso modo, il problemino in oggetto si risolve senza ricorrere a metodi overkill (es. ottimizzazione per discesa ricorsiva) e senza sprecare memoria con array di dimensioni esorbitanti: è possibile una soluzione in tempo costante O(1) (la sola lettura dei dati a monte è proporzionale alla dimensione dell'input), con una occupazione costante (= indipendente dall'input) di memoria, pari esattamente a quattro interi non segnati, e senza alcun loop.

Infatti, esistono solamente quattro possibili valori per l'ampiezza del gruppo di studenti, dunque la lettura si può effettuare come nello shellsort o nel conteggio delle occorrenze di caratteri ASCII da un testo arbitrario, ossia indirizzando direttamente l'array delle occorrenze col dato appena letto, dopo un ovvio quanto minimale controllo di congruenza formale.

Una volta ottenuti questi quattro numeretti, che rappresentano completamente l'input in forma "compressa", non resta che ricombinarli. Ciò che dobbiamo ottenere è, in realtà, una soluzione ad un problemino di composizione (l'opposto della partizione di un intero...). Dobbiamo cioè sostanzialmente conteggiare quante composizioni, di valore pari a 4, possiamo ottenere con le quantità a nostra disposizione - con qualche piccola variante, ovviamente, e tralasciando l'ordinamento.
Le partizioni possibili, in questo caso, sono:

Formula LaTeX: \begin{align*}\\4 &= 4\\&= 3+1\\&= 2+2\\&= 2+1+1\\&= 1+1+1+1\end{align*}

Il che ci dà, in modo pressoché immediato, una formuletta lineare da applicare. Se infatti conveniamo di ignorare la composizione 2+1+1 (tranne in un caso specifico, che vedremo) in favore di quelle combinatorialmente equivalenti, abbiamo che il totale si compone di:

• Tutti i gruppi di quattro studenti, conteggiati una sola volta (students[3] nell'esempio);

• Tutti i gruppi di tre studenti, conteggiati una sola volta (per la regola "all members of each group should ride in the same taxi"). Spiego meglio, perché qui si hanno tre sottocasi apparenti, secondo la relazione tra il numero di gruppi di tre studenti (diciamo S3) e quello dei singoli S1:
a) S3 > S1: formeremo S1 taxi con 3+1 studenti e S3 - S1 taxi con 3 studenti, dovendo conteggiare quindi S1 + S3 - S1 = S3 taxi;
b) S3 = S1: Occorrono S3 taxi che porteranno 3+1 studenti.
c) S3 < S1: Potremo formare solo S3 taxi del tipo 3+1.
Appare palese come, in tutti e tre i casi, il contributo dei gruppi di 3 è tale che ad ogni gruppo corrisponde un taxi, esattamente come nel caso precedente.

• Per i gruppi di due, conteggiamo la metà del numero disponibile, approssimata all'intero successivo se tale numero risulta dispari. Consideriamo infatti di formare taxi con gruppi da 2+2, con eventuale avanzo di un gruppo (che può dare adito ad un singolo caso particolare, gestito a parte).

• Infine, per i singoli studenti, dobbiamo tenere presente l'eventuale accoppiamento già effettuato con i gruppi da 3, con una sottrazione condizionata (è infatti palese che nel caso a) nulla di buono verrebbe dal sottrarre ad un numero naturale un distinto naturale maggiore di esso...). Gli eventuali singoli rimanenti verranno "stipati" a quattro a quattro negli ultimi taxi, con eventuale resto.

Per concludere, attenzione all'unico eventuale caso particolare: se tale "resto" appena menzionato è non nullo ma diverso da tre E il numero di gruppi di due è dispari, i singoli rimanenti si possono intruppare col duetto superstite in un taxi 2+1 o 2+1+1 e con ciò occorre diminuire di uno il totale fin qui ottenuto, per evitare un erroneo doppio conteggio.

Tutto qui. Con un paio di operazioni algebriche, una if() e qualche operatore ternario abbiamo risolto elegantissimamente il problema, in tempo costante - a parte le noiose, ma necessarie, operazioni di input, ovviamente. Si noti anche la comoda idiv(), per l'occasione in versione più compatta rispetto all'esempio già pubblicato nel thread sopra referenziato (qualche compilatore potrebbe farne direttamente una funzione inline).

codice:
#include <stdlib.h>
#include <stdio.h>
#include <mem.h>

#define MAX_VAL 4

unsigned int idiv(unsigned int a, unsigned int b)
{
    return(a / b + (a % b != 0 ? 1 : 0));
}    

int TaxiCount(unsigned int st[])
{
    int i;
    int ret, t;
    
    for (i = 0; i < MAX_VAL; ++i)
    {
        printf("st[%d] = %d\n", i, st[i]);
    }
    
    /* 
    ** Le operazioni sono qui frazionate per ovvie motivazioni 
    ** didattiche e di comodita' di lettura/debug. 
    */
    ret = st[3] + st[2];
    ret += idiv(st[1], 2);
    st[0] -= min(st[2], st[0]);
    ret += idiv(st[0], 4);
    if ((st[1] & 1) && (st[0] % MAX_VAL > 0) && (st[0] % MAX_VAL < 3))
    {
        --ret;
    }
    return(ret);
}

int main(void)
{
    int i, n, m;
    unsigned int students[MAX_VAL];
    
    memset(students, 0, MAX_VAL * sizeof(int));
    scanf("%d", &n);
    
    for (i = 0; i < n; ++i)
    {
        scanf("%d", &m);
        if ((m > 0) && (m < MAX_VAL +1))
        {
            students[m -1] += 1;
        }
    }
    
    printf("Taxi necessari: %d\n\n", TaxiCount(students));
    
    return (0);
}
Si noti, in chiusura, che con un minimo di riflessione è molto facile impostare una singola, banale formuletta per gestire il caso particolare eliminando la if(), ovviamente per mero esercizio.

codice:
    ret -= (st[1] & 1) & (1 & (st[0] ^ (st[0] >> 1)));
La formula è ampiamente semplificata dal fatto che tutti i possibili valori del resto che ci interessano (1 e 2) sono caratterizzati dall'avere esattamente un solo bit alto. Grazie a shift e xor, possiamo quindi isolare nella medesima posizione (LSB) un bit per rappresentare l'informazione che ci interessa sul resto (per ulteriori cenni sul conteggio implicito di bit tramite XOR, si veda anche questo thread), e l'altro bit che naturalmente rappresenta la parità del numero di "gruppi di due studenti".
In ultima analisi, tale formuletta restituisce zero in tutti i casi, eccetto nel caso notevole, che dà invece adito alla restituzione di un valore unitario, da sottrarre poi debitamente al totale. Nulla vieta, infine, di pensare ad una LUT applicabile al caso in esame, indicizzata con tre bit giustapposti (i due bit del resto e quello della parità), il che potrebbe consentire un ulteriore risparmio di qualche ciclo macchina, sebbene in principio di minor rilevanza quantitativa rispetto all'eliminazione di un salto condizionato.

Notando infine che il modulo viene effettuato su una potenza intera del due, ricordo ad usum delphini che è sempre possibile sostituire esplicitamente tale operazione con una banale maschera AND. Sia infatti 2n il valore per il modulo, con n opportuno esponente naturale: allora, occorre e basta calcolare (val AND 2n - 1), come in (st[0] & 3), ossia creando una maschera AND che abbia gli n bit meno significativi alti, dal bit zero fino all'n-esimo escluso.
Allo stesso modo, le divisioni per le potenze del due possono essere implementate come d'abitudine tramite shift a destra.
Ciò avrà esattamente il medesimo effetto, ma con diverso grado di efficienza secondo la CPU target e il compilatore. Una volta accertato che l'optimizer non introduca già tali forme, è possibile farne uso per ottimizzare ulteriormente il codice, sempre a scopo ludico-didattico.

Commenti

  1. L'avatar di Windows M
    Davvero molto interessante, come già avevo commentato nel thread che hai linkato.
    Pare, però, che le partizioni di interi ti perseguitino
    aggiornamento da 10-04-2012 a 18:49 di Windows M (mistype)
  2. L'avatar di M.A.W. 1968
    In effetti, le partizioni (e le composizioni) sono un po' ovunque e spuntano fuori là dove meno ce le attendiamo: econometria, fisica, meccanica, chimica, teoria dei sistemi... oltre, ovviamente, alla "specialità della casa", ossia la matematica discreta.

    Basti pensare al loro ruolo fondamentale nei gruppi di permutazioni, a loro volta essenziali in molte teorie fisiche avanzate. Non a caso, uno dei pochissimi commenti a caldo in lingua italiana (al di là delle solite traduzioni di articoli sulle edizioni italiane di riviste straniere, pressoché dovute) all'annuncio dei risultati del gruppo di Ken Ono proveniva da un paio di fisici, che si occupano prevalentemente di teoria delle stringhe!

    Anche per questo le formule di cui abbiamo più volte discusso (e i relativi algoritmi) ricoprono un ruolo fondamentale...