Prototipo di un constraint solver – Struttura

Nel precedente post avevo parlato di cosa è un constraint satisfaction problem, in questo invece descriverò come funziona un solver per tali problemi. Lo pseudocodice di una generica procedura che consente di risolvere un CSP è la seguente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void Solve(CSP problem)
{
    bool continue = true;
    while (continue && !IsDone(problem))
    {
        Preprocess(problem);
        Propagate(problem);
        if (!IsDone(problem))
        {
            if (IsAtomic(problem))
            {
                continue = false;
            }
            else
            {
                CSP[] problems = Split(problem);
                ProceedWithSubproblems(problems);
            }
        }
    }
}

• IsDone è un procedura capace di indicare se il CSP è stato risolto oppure, al contrario, se non esistono soluzioni al problema (es. X, Y e Z con dominio {1, 2}, X < Y < Z). Questo comporta, a seconda dei casi:
  • Che una soluzione al problema è stata trovata;
  • Che tutte le soluzioni al problema sono state trovate;
  • C’è un’incoerenza nel problema (es. X appartiene a {1,2}, Y appartiene a {3,4}, X + Y = 9);
  • Tutti i domini hanno una dimensione inferiore ad un valore prefissato (nel caso di domini reali)
  • È stato trovato l’ottimo rispetto a qualche funzione obiettivo
• Preprocess consente di trasformare il problema nella forma desiderata prima di partire con la fase di propagazione. È particolarmente utile per alcune tipologie di solver, ad esempio quando ci sono solo vincoli di tipo logico (and, not, or, …) su domini booleani
• Propagate è il cuore del processo di risoluzione di un problema vincolato. Lo scopo della procedura è iterare delle regole di riduzione dei domini fino a quando nessuna ulteriore riduzione è possibile. Si prenda ad esempio il seguente problema: X in [50 ... 200], Y in [0 ... 100] e Z in [0 ... 100], con vincoli X < Y e Y < Z. Usiamo la regola di riduzione per X < Y porta alla seguente riduzione: X.High = Min(X.High, Y.High - 1) e Y.Low = Max(Y.Low, X.Low + 1), dove Low ed High rappresentano il minimo ed il massimo del dominio associato alle variabili. Allora al primo passaggio, usando la regola di riduzione su X < Y, otteniamo X in [50 ... 99], Y in [51 ... 100], Z in [0 ... 100]. Al secondo, usando il vincolo Y < Z, otteniamo X in [50 ... 99], Y in [51 ... 99] e Z in [52 ... 100]. Il terzo passaggio, di nuovo concentrandosi su X < Y, porta a X in [50 ... 98], Y in [51 ... 99], Z in [52 ... 100]. Nessuna altra riduzione è possibile.
• IsAtomic è una procedura che testa se è possibile suddividere ulteriormente il problema oppure no. In genere, un problema non è ulteriormente suddivisibile se tutti i domini sono dei singoletti.
• Split e ProceedWithSubproblems, assieme a Propagate, rappresentano la parte più importante del solver. Queste due procedure si occupano di suddividere il problema in sottoproblemi, di selezionare il successivo sottoproblema su cui avviare la procedura di Solve, ed eventualmente di terminare se si è raggiunta una soluzione.

Fatta questa introduzione, il constraint solver in C# sarà composto dalle seguenti parti:

• Una classe Variable, che si occupa di gestire le operazioni elementari sul suo dominio. La classe esporrà l’evento DomainChanged per avvisare dell’avvenuto cambiamento del dominio.
• Un interfaccia IConstraint, implementata dalle varie classi che si occupano di applicare le regole di riduzione dei domini.
• Un ConstraintStore, che gestirà la fase di propagazione.
• Un VariableStore, che avrà il ruolo di gestire le fasi di splitting e backtracking.
• Per finire un Solver, che agirà usando il ConstraintStore e il VariableStore per risolvere il CSP.