Immagino che questa sia una domanda per la soluzione dei problemi, ma sono fuori di idee, non so davvero dove posso trovare aiuto, e ho bisogno di risolvere questo problema.
Essenzialmente abbiamo una serie di consumatori e un insieme di risorse e l'obiettivo è assegnare una risorsa a ciascun consumatore. Non tutte le risorse sono idonee per ogni consumatore: ci sono molti diversi tipi di regole che limitano le scelte.
Dati questi consumatori e risorse:
consumers = [C1, C2, C3, C4, C5]
resources = [R1, R2, R3, R4, R5, R6, R7, R8]
Possiamo rappresentare le risorse idonee con una tabella (si noti che in questo esempio il raggruppamento in sezioni di risorse può suggerire una soluzione, in pratica le risorse idonee sarebbero più disperse e il raggruppamento sarebbe difficile o impossibile):
C1 C2 C3 C4 C5
R1 x x x x
R2 x x x x
R3 x x
R4 x x
R5 x x
R6 x x
R7 x x
R8 x x
Proviamo ad assegnare una risorsa a ogni consumatore:
while unsatisfied_consumers:
unassigned_resources = list(resources)
unsatisfied_consumers = list(consumers)
for c in unsatisfied_consumers:
for r in eligible_resources[c]:
if c.assign(r):
unsatisfied_consumers.remove(c)
unassigned_resources.remove(r)
break
Se non tutti i consumatori potrebbero essere soddisfatti, per ognuno di essi proviamo a trovare risorse già assegnate idonee e al destinatario assegnato viene invece assegnata una risorsa non assegnata (se idonea). Essenzialmente una riassegnazione. Questo sarebbe giusto dopo il ciclo for :
for c in unsatisfied_consumers:
assigned_resources = [r for r in resources if r not in unassigned_resources]
c_eligible_resources = [r for r in eligible_resources[c] if r in assigned_resources]
for r in c_eligible_resources:
satisfied_consumer = r.assigned_consumer()
# try to find an alternative resrouce for the already satisfied consumer
# so that c can be assigned its resource instead
for unassigned_r in unassigned_resources:
if satisfied_consumer.assign(unassigned_r):
unassigned_resrouces.remove(unassigned_r)
unsatisfied_consumers.remove(c)
c.resource = r
Come puoi vedere, siamo noiosi a forzare il nostro modo di trovare la soluzione.
Il problema è quando non tutti i consumatori possono essere soddisfatti, semplicemente a causa dell'idoneità delle risorse. Indipendentemente dal numero di tentativi di riassegnazione delle risorse, ad alcuni utenti non verranno mai assegnate risorse perché non ci sono abbastanza risorse.
E c'è dove sto cercando di ottenere. Sto cercando di escogitare un modo per essere in grado di dire quali sono i consumatori esposti all'esaurimento delle risorse prima ancora di iniziare ad assegnare risorse, in modo che quando si manifestano problemi di insoddisfazione, possiamo tranquillamente assumere il loro stato e andare avanti con i consumatori che possono effettivamente essere risorse assegnate.
Usando il mio esempio di tabella, a prima vista possiamo dire che i consumatori C1 , C2 e C3 rivaleggiano per le risorse R1 e R2 , quindi uno di questi consumatori sarà semplicemente insoddisfatto. Quello che sto cercando di fare è progettare un meccanismo per riconoscere che [C1, C2, C3] è soggetto all'esaurimento delle risorse quindi se si verifica un assegnamento fallito, non dovremmo provare di nuovo per questi particolari consumatori.
Sappiamo quali risorse sono elliglbe per ogni consumatore, e inversamente sappiamo quali sono i consumatori "adatti" a ciascuna risorsa. Forse questa informazione potrebbe essere utilizzata nella soluzione?