Questa presentazione descrive diversi algoritmi per la risoluzione di un CSP per la pianificazione.
Dire che ho alcuni processi con alcuni vincoli:
a before c
c before b
b after d
c 50% more important than e
give d at least 20% of the total running time
f before and after d
g after f only if b is still running
run h if there is at least 20% free memory available.
interrupt h with i for a minute if h runs longer than 5 minutes.
etc.
Mi chiedo come faccio a scrivere questo in termini di vincoli, se possono essere scritti come vincoli binari (non sono sicuro che tutti siano binari), e l'idea approssimativa di come "risolvere" il sistema. Cioè, capire un ordine e la durata dei processi che soddisfa tutti i vincoli. Ho cercato di includere vari tipi di variabili per renderlo più realistico:
- Ora.
- Risorse. (memoria disponibile).
- priorità. (50% più importante).
Se dovessi scrivere i vincoli, farei:
a.start < c.start
c.start < b.start
b.start > d.start
e.priority = 0.5 * c.priority
d.duration = 0.2 * system.duration
f.start < d.start && f.end > d.end
g.start > f.start if b.running
if system.memory < system.memory.total * 0.2 then start h (this one is trickier)
if h.duration > 5 min then interrupt h && start i && stop i when i.duration == 1 min
Non sono sicuro di come scrivere start i e stop i come vincoli e le istruzioni if-then.
Direi che le variabili sono:
a.start
b.start
c.start
d.start
f.start
g.start
d.end
f.end
c.priority
e.priority
d.duration
h.duration
i.duration
system.duration
system.memory
system.memory.total
Quindi il dominio delle variabili di cui non sono sicuro. I tempi possono essere qualsiasi timestamp intero, quindi forse è all'interno di qualche milione di interi con risoluzione ms. Quindi la priorità è una percentuale. E c.priority sembra essere di sola lettura, quindi non è sicuro se abbiamo bisogno di inizializzare alcune delle variabili precedenti.
Quindi abbiamo le 3 componenti di un CSP = (V, D, C), variabili, domini e vincoli. Non sono sicuro di averle fatte correttamente.
Dopo averli definiti correttamente, sto cercando di capire come funziona l' algoritmo di controllo in avanti . Non vedo ancora approssimativamente come si naviga il "grafico dei vincoli" per assegnare valori alle variabili. Sto solo cercando una spiegazione di base usando i pezzi dell'esempio sopra riportato.
Per riassumere, le mie domande sono:
- Se modifico i componenti CSP = (V, D, C) correttamente. O cosa ho sbagliato.
- Una rapida spiegazione di come funziona uno qualsiasi degli algoritmi usando come esempio il V / D / C dall'alto. Mi piacerebbe vedere da qualcosa di pratico come andare effettivamente a "risolvere" il sistema dei vincoli ad alto livello, così posso quindi avere gli strumenti per capire come risolvere questo specifico problema.