Algoritmo di pianificazione lavoro in Java

Question

Ho bisogno di progettare un algoritmo efficiente per un problema di schedulazione e davvero non ne ho idea.

C'è una macchina che produce pillole in una certa velocità. Ad esempio, la macchina potrebbe essere in grado di produrre 1 pillola se è consentito lavorare ininterrottamente per un giorno, 4 compresse, se è consentito lavorare per 3 giorni, 16 compresse se funziona per 5 giorni e così via. Se fermo la macchina e prendo tutte le pillole, la macchina inizierà di nuovo dal primo giorno. Tutte le pillole che ho estratto dalla macchina devono essere utilizzate lo stesso giorno.

C'è una certa quantità di pazienti che vengono e prendono pillole ogni giorno. I pazienti devono essere trattati lo stesso giorno, i pazienti non trattati vengono ignorati. L'obiettivo è decidere in quali giorni fermare la macchina e trattare il maggior numero possibile di pazienti in n giorni.

Supponiamo che il numero di giorni n = 5, dato esempio ingresso

int[] machineRate = {1,2,4,8,16}; 
int[] patients = {1,2,3,0,2}; 

In questo caso, se mi fermo macchina il giorno 3, avrò 4 pillole. Posso trattare 3 pazienti e gettare via 1 pillola. Poi interrompo di nuovo la macchina il giorno 5, poiché è stata interrotta il terzo giorno, ha funzionato per 2 giorni, quindi ho 2 pillole per curare 2 pazienti. Alla fine 3 + 2 = 5, l'output = 5 pazienti.

Se arresto la macchina al giorno 2, giorno 3, giorno 5. Quindi l'output sarà (2 pillole per 2 pazienti al giorno 2) + (1 pillola per 3 pazienti al giorno 3) + (2 pillole per 2 pazienti al giorno 5). Ciò equivale a 5 pazienti pure.

I numeri machineRate[] e patients[] variano in base all'input.

Qual è l'algoritmo che trova il numero massimo di pazienti trattati?

Answer 1

Questo è un bel problema di programmazione dinamica.

Il modo di pensare di programmazione dinamica è quella di porsi due domande:

1. Esiste una versione banale di questo problema se riduco uno (o più) delle variabili da zero (o simili)?
2. Esiste un modo semplice per calcolare la risposta a un problema di dimensione n+1 se conosco le risposte a tutti i problemi della dimensione n? (Qui, "dimensione" è specifica del problema, e devi trovare la nozione giusta di dimensioni che aiuti con il problema in mano.)

Per questo problema, quale sarebbe una versione banale? Bene, supponiamo che il numero di giorni sia stato 1. Quindi sarebbe stato facile: ho fermato la macchina e ho trattato il maggior numero di pazienti possibile. Non ha senso fare altro.

Ora, se consideriamo il numero di giorni rimasti come nozione di dimensione, otteniamo anche una risposta alla seconda domanda. Supponiamo di sapere tutte le risposte a tutti i problemi in cui ci sono n giorni rimanenti. Scriviamo maxTreat(days, running) per il numero massimo che potremmo trattare se ci fossero days giorni rimanenti e se la macchina fosse stata inizialmente in esecuzione per running giorni.

Ora ci sono n+1 giorni rimanenti; e la macchina ha funzionato finora per i giorni k. Abbiamo due opzioni: (1) fermare la macchina; (2) non fermarlo.Se interrompiamo la macchina, possiamo trattare alcuni pazienti oggi (possiamo calcolare il numero basato su k), e successivamente possiamo trattare i pazienti maxTreat(n, 1), perché ci sono ancora n giorni, e domani la macchina sarà di nuovo in esecuzione per un solo giorno. Se non fermiamo la macchina, non possiamo trattare chiunque oggi, ma da allora in poi saremo in grado di trattare i pazienti maxTreat(n,k+1), perché domani la macchina sarà in corso da k+1 giorni.

Vi lascio a elaborare i dettagli precisi, ma per risolverlo in modo efficiente, creiamo una matrice multidimensionale, basata sul numero di giorni rimasti e il numero di giorni per i quali la macchina ha funzionato finora. Quindi, iteriamo attraverso l'array, risolvendo tutti i possibili problemi, a partire dal banale (un giorno lasciato) e lavorando all'indietro (due giorni, poi tre giorni e così via). In ogni fase, il problema che stiamo risolvendo è o banale (quindi possiamo semplicemente scrivere la risposta in), o qualcosa che possiamo calcolare dalle voci che abbiamo scritto nell'array nel passaggio precedente.

La cosa veramente interessante della programmazione dinamica è che stiamo creando una cache di tutti i risultati. Quindi, per problemi in cui un approccio ricorsivo finirà per dover calcolare più volte la risposta a un sotto-problema, con la programmazione dinamica non risolviamo mai un sotto-problema più di una volta.

Ulteriori commenti ora che ho visto l'implementazione:

Per uno, io non sono troppo sorpreso che inizia a rallentare quando si colpisce 10.000 o giù di lì. L'algoritmo è O(n^2), perché a ogni iterazione è necessario riempire l'array con un massimo di n voci prima di passare al livello successivo. Sono abbastanza certo che O(n^2) è la migliore complessità asintotica che otterrai per questo puzzle, però.

Se si desidera accelerare ulteriormente, è possibile osservare un approccio dall'alto verso il basso. Attualmente stai facendo una programmazione dinamica bottom-up: risolvendo i casi di dimensione 0, quindi di dimensione 1 e così via. Ma puoi anche farlo al contrario. Essenzialmente questo è lo stesso algoritmo come se si stesse scrivendo una soluzione ricorsiva orribilmente inefficiente che calcola le soluzioni ai sotto-problemi al volo, eccetto che si memorizza un risultato in cache ogni volta che lo si calcola. Quindi assomiglia a questo:

1. Imposta il tuo array bidimensionale per contenere soluzioni a problemi secondari. Pre-riempirlo con -1 per ogni caso. Un valore di -1 indicherà che non hai ancora risolto il problema secondario.
2. Scrivere una routine che risolva maxTreat(days, running) in termini di risposte a problemi secondari al livello successivo. Quando vuoi le risposte ai sotto-problemi, guarda nell'array. Se c'è un -1 lì, non lo hai ancora risolto, quindi lo risolvi in ​​modo ricorsivo e poi metti la risposta nell'array. Se c'è qualcosa di diverso da -1, puoi semplicemente usare il valore che trovi lì, perché lo hai già calcolato. (È inoltre possibile utilizzare un anziché l'array multidimensionale.)

Questo è meglio in un modo e peggio in un altro. È peggio perché hai overheads associati alla ricorsione e perché alla fine finirai con lo stack con le chiamate ricorsive. Potrebbe essere necessario aumentare la dimensione dello stack con un parametro della riga di comando sulla JVM.

Ma è meglio in un aspetto fondamentale: non si calcolano le risposte a tutti i sotto-problemi, ma solo quelli a cui è necessario conoscere le risposte. Per alcuni problemi, questa è una grande differenza e per alcuni non lo è. È difficile avere l'intuizione giusta, ma penso che potrebbe fare una grande differenza qui. Dopotutto, ogni risposta dipende solo da due sotto-problemi della riga precedente.

La soluzione definitiva (non provarlo fino a quando non si ottiene prima quello ricorsivo dall'alto verso il basso!) È farlo dall'alto verso il basso ma senza ricorsione. Ciò eviterà il problema dello spazio di stack. Per fare questo, crei una serie di problemi secondari (usa uno ArrayDeque) che devono essere risolti e continui a portarli fuori dalla coda finché non ne rimane nessuno. La prima cosa è spingere in pila il grosso problema per il quale è necessaria una soluzione. Ora, si espellono in modo iterativo i problemi dallo stack fino a quando non è vuoto. Pop one off, e chiamalo P. Poi:

1. guardare nel tuo array o HashMap per vedere se P è stato risolto. In tal caso, restituire la risposta.
2. In caso contrario, verificare se i problemi secondari per P sono già stati risolti. In tal caso, è possibile risolvere P e memorizzare la risposta nella cache. Se lo stack è vuoto, hai risolto il problema finale e hai generato la risposta per P.
3. Se i problemi secondari non sono stati tutti risolti, premere nuovamente P nello stack. Quindi spingere uno dei problemi secondari di P che non sono ancora stati risolti nello stack.

Quello che succederà mentre si procede è che lo stack crescerà inizialmente quando si spinge il problema principale, i suoi sotto-problemi e quindi i suoi sotto-problemi, nello stack. Quindi inizierai a risolvere le istanze più piccole e a mettere i risultati nella cache, finché alla fine avrai tutto ciò che ti serve per risolvere il problema principale.

Non utilizza molto meno memoria rispetto all'approccio top-down ricorsivo, ma utilizza lo spazio heap anziché lo spazio JVM dello stack e ciò significa che si adatta meglio perché lo stack JVM è molto più piccolo dell'heap.

Questo è abbastanza difficile, però. Per lo meno, mantieni la soluzione di lavoro prima di iniziare a codificare la versione più difficile!

Answer 2

Un altro approccio sarebbe quello di prevedere il giorno o i giorni successivi. Diciamo che abbiamo visto 1,2 pazienti negli ultimi giorni, potremmo prendere le due pillole oggi e curare due pazienti o predire tre o più per il giorno successivo e far funzionare la macchina. Se non abbiamo un aumento come 1,1, prevediamo un paziente per domani e prendiamo l'unica pillola oggi. Se il giorno successivo risulta diffrente come 1, 4, 0, limitiamo semplicemente la previsione per il giorno successivo a 1/2, cioè 2. Il lato superiore di questa soluzione è che puoi lavorare con incertezza, cioè non sai cosa porta il domani. questo ci consente di trasmettere i dati. Il lato negativo è che il primo paziente morirà sempre.

Answer 3

Ho implementato il progetto chiastic-security, ma le prestazioni non sono grandi quando n diventa più grande di 10000 o giù di lì. Se qualcuno ha altre idee per favore fammelo sapere perché ho pensato che questo fosse un problema piuttosto interessante. L'ho provato con la ricorsione all'inizio, ma ho continuato a rimanere senza memoria, quindi ho dovuto farlo in un ciclo invece. Stavo conservando un grande array 2d con tutti i risultati fino ad ora, ma poi ho capito che ho sempre bisogno di accedere alla "riga" precedente dei risultati, quindi sto usando solo 2 array: "corrente" e "precedente":

MODIFICA: ho ora implementato un secondo approccio, ma ho ancora problemi con n> = 10000 circa: Exception in thread "main" java.lang.OutOfMemoryError: Java heap space. Ecco il mio codice se qualcuno è interessato a perseguire ulteriormente:

static final int[][] results = new int[n][n]; 
static final SortedSet<Target> queue = new TreeSet<>(new Comparator<Target>() { 
    @Override 
    public int compare(Target o1, Target o2) { 
     if (o1.daysRemaining < o2.daysRemaining) 
      return -1; 
     else if (o1.daysRemaining > o2.daysRemaining) 
      return 1; 
     else if (o1.daysMachineRunning < o2.daysMachineRunning) 
      return 1; 
     else if (o1.daysMachineRunning > o2.daysMachineRunning) 
      return -1; 
     else return 0; 
    } 
}); 

public static void main(String[] args) { 
    for (int i=0; i<n; i++) { 
     Arrays.fill(results[i], -1); 
    } 

    if (n <= 10) { 
     System.out.println(Arrays.toString(machineRate)); 
     System.out.println(Arrays.toString(patients)); 
    } else 
     System.out.println(n); 

    System.out.println(calculateMax()); 
} 

static class Target { 
    int daysRemaining, daysMachineRunning; 
    Target(int daysRemaining, int daysMachineRunning) { 
     this.daysRemaining = daysRemaining; 
     this.daysMachineRunning = daysMachineRunning; 
    } 
} 

static int calculateMax() { 
    addTarget(n-1, 0); 
    while (results[n-1][0]==-1) { 
     Target t = queue.first(); 
     queue.remove(t); 
     calculateMax(t); 
    } 
    return results[n-1][0]; 
} 

static void calculateMax(Target t) { 
    int daysRemaining = t.daysRemaining; 
    int daysMachineRunning = t.daysMachineRunning; 
    int treatedPatients = Math.min(patients[n-1-daysRemaining], machineRate[daysMachineRunning]); 
    if (daysRemaining==0) 
     results[0][daysMachineRunning] = treatedPatients; 
    else { 
     int resultA = results[daysRemaining-1][0]; 
     int resultB = results[daysRemaining-1][daysMachineRunning+1]; 
     if (resultA>=0 && resultB>=0) { 
      results[daysRemaining][daysMachineRunning] = Math.max(treatedPatients + resultA, resultB); 
     } 
     else { 
      if (resultA==-1) 
       addTarget(daysRemaining-1, 0); 
      if (resultB==-1) 
       addTarget(daysRemaining-1, daysMachineRunning+1); 
      addTarget(daysRemaining, daysMachineRunning); 
     } 
    } 
} 

static void addTarget(int a, int b) { 
    queue.add(new Target(a,b)); 
}