Approccio all'algoritmo per l'assegnazione delle risorse

Question

Approccio all'algoritmo per l'assegnazione delle risorse

#1 da (3 voti)
#2 da (2 voti)
#3 da (0 voti)

4

Abbiamo l'obbligo di essere in grado di abbinare le persone con le posizioni in base alla disponibilità e a determinate condizioni.

Diciamo che ho un gruppo di persone ognuna con 3 tipi di cose che potrebbero aver bisogno di parcheggiare. Una macchina, un camion e una barca. Ogni persona indica anche la posizione di parcheggio preferita (scelte 1, 2 e 3).

Ho anche una lista di parcheggi che possono gestire un certo numero di ciascuna di queste cose. L'obiettivo è quello di abbinare tutti in modo che il massimo utilizzo. Il requisito principale è che ogni singola persona debba essere in grado di parcheggiare tutto nella stessa posizione OPPURE di non parcheggiare affatto.

Esempio:
A partire dalle posizioni di parcheggio che ho:

Lot    Cars    Trucks    Boats
A       2       0         2
B       2       1         3
C       0       5         0

Per le persone che ho:

Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Tom        2       1         0         A         B         C
Betty      1       0         1         B         C         A
Sam        0       2         0         C         A         B
Pat        3       2         1         A         C         B

Il mio pensiero iniziale è quello di ordinare semplicemente le persone in base al numero di elementi che hanno (dal più grande al più piccolo). Quindi provare a posizionare ciascuno in base alla scelta. IE: proverei a posizionare Pat prima (la maggior parte degli oggetti), ma non potrei perché non c'è molto che soddisfi i requisiti. Poi proverei Tom, che andrebbe in Lot B. Etc.

Conosci qualche problema con questo approccio?

Punti bonus: esiste un nome per questo tipo di problema?

algorithms

posta NotMe 22.11.2013 - 20:35

fonte

3 risposte

Leggi altre domande sui tag algorithms

L'uso di mongodb migliora l'estensione / modifica delle applicazioni basate su database? GWT vs JSF vs ZK vs Restful + JS [chiuso]

score 3 · Answer 1

Non è proprio così semplice. Dovresti fare il backtracking nei casi in cui una persona corrisponde a più lotti. Supponiamo che tu abbia gli stessi lotti, ma le seguenti persone:

Person    Cars    Trucks    Boats    Choice 1  Choice 2  Choice 3
Adam       2       0         1         B         A         C
Eve        1       1         0         B         C         A

Adam potrebbe rientrare in B o A , quindi gli permetti di avere la sua prima scelta: B . Ora Eve non può andare bene ovunque, anche se Adam fosse in A , potrebbe rientrare in B . Quindi hai bisogno di un mezzo per tornare indietro per fare una scelta diversa per Adam. È anche possibile che la soluzione ideale non permetta a qualcuno con la richiesta più grande, anche se si adatta, quindi è necessario tenerne conto.

Non so se c'è un nome noto per questo problema esatto. Il nome più comune che vedo per il problema generale è "allocazione delle risorse".

score 2 · Answer 2

Questa sembra una variante del problema dello zaino tuttavia invece di avere una borsa singola ne hai diversi e ogni oggetto ha una preferenza su quale borsa appartiene. Consulta il tuo dipartimento di informatica locale per conferma.

Se si tratta di una variante del problema dello zaino, ti troverai in NP-Complete in termini di complessità. Il che significa che stai cercando pragmaticamente un problema di ottimizzazione, quindi trova la soluzione il più vicino possibile ottimale.

score 0 · Answer 3

Che ne dici di qualcosa di simile:

Create a list of Lots lots.  
Sort this list by the number of resources (cars + trucks + boats)

While lots is not empty:  
    Lot next_lot = The lot that has the least amount of resources.  
    Find the Person person who fits in this lot and takes up most of its resources.  
    Place person into next_lot.  
    Remove next_lot from lots.

Immagino che questo minimizzerebbe la frammentazione.