Assegnazione di molti studenti a molte scuole basate sulla capacità

Question

Dì che ho un insieme di coordinate delle scuole. Ho anche un set di coordinate del Centroide di quartieri (N).

So quanti figli sono in ogni quartiere, e sono classificati come scuola primaria, media o superiore. Quindi, in altre parole,

N = [(locationN1, primary:3, middle:10, high:4), (locationN2, primary:10, middle:17, high:7), ...]

.

So quanti spot sono disponibili in ogni scuola, il formato è:

S = [(locationS1, primary:20, middle:5, high:2), (locationS2, primary:12, middle:7, high:8), ...]

.

Il mio obiettivo è abbinare il maggior numero possibile di studenti a una scuola all'interno di un certo raggio. È possibile (estremamente probabile) che nei miei calcoli, alcuni studenti saranno inferiori a scuola.

Quello che voglio: identificare quale quartiere ha bambini meno scuola e quanti anni.

Il mio piano corrente:

.
• Elenca tutti gli abbinamenti e le distanze corrispondenti tra scuole e quartiere, all'interno di un determinato raggio
• ordina per distanza dal più basso al più alto
• Dare la priorità basata sulla distanza
• Loop sul quartiere in ordine di apparizione (ogni quartiere può apparire più volte collegato a una determinata scuola all'interno del raggio definito)
• Riempi la scuola corrispondente con i bambini dal quartiere
• Rimuovi punti presi dalla capacità della scuola
• Passa al prossimo accoppiamento della scuola di quartiere, ...

Come esempio:

.

• Dì che ottieni il seguente ordine:

  ordine= [(vicinato_2, scuola_7, distanza1), (vicinato_5, scuola_2, distanza2), (quartiere_2, scuola_2, distanza3), (vicinato_2, scuola_3, distanza4) ...]

Allora, School_7 riceve i bambini dal quartiere_2. Non tutti i bambini dal vicinato_2 possono essere presi a scuola_7.

Allora, School_2 riceve studenti dal vicinato_5. Ora, supponi che School_2 sia piena per la capacità della scuola media.

Allora, il quartiere_2 ha ancora studenti di spedire, e quindi cerca di inviarli a scuola_2. Primarie e superiori, nessun problema, ora sono tutti spediti. Ma la scuola media è piena.

Poi passiamo al prossimo accoppiamento, e School_3 ottiene i restanti studenti della scuola media dal quartiere_2. Si noti che se la distanza4 era stata superiore al raggio limite, questi studenti della scuola media sarebbero stati classificati come meno a scuola da quando non sono disponibili altri accoppiamenti.

Inoltre, se il vicinato_4 è OIT del raggio limite per qualsiasi scuola, tutti i suoi figli sono considerati a scuola meno.

1) Il mio algoritmo è corretto?

2) Qual è il nome di questo problema esatto? Ho incontrato molti a molti problemi di abbinamento del punto, problemi di assegnazione capacita, o la parte "convalidazione" del problema della posizione della struttura, ma non questa particolare variante per qualche motivo (probabilmente scarse condizioni di ricerca)

3) Come posso renderlo efficiente, o è abbastanza ragionevole in questo modo? (L'efficienza non è la mia preoccupazione principale, ma le correzioni facili sono i benvenuti)

4) Ho altre opzioni oltre a ordinamento della distanza? Tecnicamente, nel mio caso, la distanza non ha importanza di dare priorità, è più di un casuale (o dovrei dire la giusta relativa assegnazione basata per esempio il tempo di applicazione ricevuta (dati sconosciuti). Quindi il mio metodo mostrerà probabilmente allocation al 100% per un quartiere molto vicino a una scuola AMD un gruppo di bambini meno scolastici nei quartieri di Farrer, ma che potrebbe non essere (non è) vero nella vita reale.

Answer 1

Questo può essere espresso come il problema di trovare un corrispondenza massima in un grafico bipartite :Ogni bambino è un sinistro-vertice, ogni slot in una scuola è un vero vertice, e c'è un vantaggio tra due vertici se possono essere abbinati.

Nel tuo caso, puoi risolverlo in modo più efficiente usando flusso max .Lascerò allenarmi i dettagli.