Algoritmo per uno strumento di pianificazione

Question

Sto scrivendo una piccola applicazione software che deve servire come un semplice strumento di pianificazione per una scuola locale. Il 'problema' di cui ha bisogno per risolvere è piuttosto semplice. Vale a dire, gli insegnanti hanno bisogno di parlare con i genitori di tutti i bambini. Tuttavia, alcuni bambini hanno, ovviamente, fratelli e sorelle in diversi gruppi, in modo questi colloqui devono essere in programma accanto a vicenda, al fine di evitare le situazioni erano genitori avere un colloquio alle 6 del pomeriggio e un altro alle 10 di sera. Così, in breve, dato un insieme di n i bambini, dove alcuni bambini hanno 1 o più fratelli o sorelle, generare un programma in cui tutti i colloqui di questi bambini sono previsti uno accanto all'altro.

Ora, forse il problema può essere risolto estremamente facile, ma dall'altra ho la sensazione che questo può essere un problema piuttosto complicato, che ha bisogno e può essere risolto con una sorta di algoritmo. Elegantemente. Ma ho ragione? È lì? Ho guardato il ungherese alorithm ma non abbastanza si applica a questo particolare problema.

Modifica:. Ho dimenticato di dire, che tutti i colloqui prendere la stessa quantità di tempo

Grazie!

Answer 1

Credo che sia abbastanza facile.

In primo gruppo i bambini che appartengono insieme perché condividono i genitori. Pianificare i bambini all'interno di un gruppo consecutivamente, pianificare il resto come casuale.

Un altro modo per astrarre e rendere il problema più semplice è quello di guardare dal punto di vista genitore, vedere fratelli e sorella come "bambino" e dare loro più tempo. Poi si può solo programmare i genitori a caso, ma un po 'bisogno di più tempo (perché hanno più childeren).

Answer 2

Un approccio woul DBE per definire il problema in un linguaggio dichiarativo vincolo e poi lasciarlo a risolvere il problema per voi. L'ultima volta che ho fatto questo, ho usato Eclipse , che è un po 'la lingua abile in cui si definisce il problema di spazio da vincoli , e poi lasciarlo trovare valori ammissibili che soddisfano tali vincoli.

Per esempio, credo che si hanno due classi di vincoli:

1. Un insegnante può avere un solo conferenza in un momento
2. Tutti gli studenti nella stessa mosto famiglia hanno slot consecutivi

Dopo aver definito questi in Eclipse, sarà calcolare i valori per ogni studente che soddisfano i requisiti. Se andate in questo modo, si può anche facilmente aggiungere vincoli come è necessario. Ad esempio, è facile dire che un insegnano non è disponibile per lo slot Y o insegnanti devono, a turno, facendo un lavoro amministrativo, ecc.

Answer 3

Questa specie si sente come un tipo di "algoritmo zaino" del problema. È necessario raggruppare i membri della famiglia insieme poi riempire gli slot in modo appropriato.

Se google "algoritmo zaino", vedrete abbastanza write-up per far girare la testa e anche alcune buone soluzioni in codice.

Answer 4

Credo che se ogni discorso potrebbe essere ridotto a "attività" in cui ogni attività ha un tempo di inizio e di fine è possibile utilizzare l'algoritmo di attività di selezione studiata in informatica. Esso si basa su un approccio greedy e potrebbe essere risolto in O (n) (dove n è il numero di attività). Si potrebbe trovare ulteriori informazioni qui . Sono sicuro che sarà necessario avere a che fare un pre-processing qui per essere in grado di ridurre l'emissione fratello / sorella come attività dello stesso tipo.