Assegnazione di Risorse a delle basi
Salve, vi illustro brevemente il mio problema.
Io sto creando un gioco e cercavo il metodo più efficiente di fare quanto scritto sotto.
Ho principalmente 2 tipi di "oggetti", localizzati in uno spazio 2D (con coordinate x e y):
Io sto creando un gioco e cercavo il metodo più efficiente di fare quanto scritto sotto.
Ho principalmente 2 tipi di "oggetti", localizzati in uno spazio 2D (con coordinate x e y):
- [*:kwm60j83]N basi di lavoratori, che contengono un numero variabile di lavoratori.[/*:m:kwm60j83]
[*:kwm60j83]M miniere, che hanno al loro interno un tot variabile di risorse.[/*:m:kwm60j83][/list:u:kwm60j83]
Ogni lavoratore può portare la stessa quantità di risorse e ha la stessa velocità di movimento.
Il mio scopo è trovare il modo più "efficiente" di portare le risorse nelle basi considerando:
- Che, per l'appunto le Basi hanno un numero diverso di lavoratori all'interno
che le miniere hanno quantità diverse di risorse
Che una miniera è assegnata a solo una base
Che le miniere hanno posizioni diverse rispetto alle basi, e quindi risulta diverso il tempo di percorrenza del lavoratore di una base rispetto a quello di un'altra[/list:u:kwm60j83]
Questo conto è da fare raramente, quindi può essere anche computazionalmente pesante.
Approssimazioni fattibili:
- [*:kwm60j83]Le basi hanno un numero grande di lavoratori, che portano relativamente poco. Quindi (Numero Lavoratori) * (quantità trasportabile) può essere una variabile anche continua[/*:m:kwm60j83][/list:u:kwm60j83]
Spero che ci sia un pro k mi da una mano xk le idee che ho avuto sin'ora non tengono conto di tutte le cose che ho detto...
Grazie mille!
Risposte
Non mi è molto chiaro cosa vuoi.
Mi sembra di capire che:
1) ad ogni base sono associate una o più miniere (e ogni miniera è associata ad una sola base).
2) ogni lavoratore è associato a una sola base; il suo compito è quello di effettuare il percorso base -> una delle miniere associate alla base -> ritorno alla base di partenza.
Cosa vuoi ottimizzare?
Senza ulteriori vincoli, e supponendo che le premesse siano corrette, è chiaro che da ogni base conviene mandare prima tutti i lavoratori alla miniera (associata alla base) più vicina; quando questa è esaurita, si mandano alla più vicina di quelle rimanenti, etc.
Mi sembra di capire che:
1) ad ogni base sono associate una o più miniere (e ogni miniera è associata ad una sola base).
2) ogni lavoratore è associato a una sola base; il suo compito è quello di effettuare il percorso base -> una delle miniere associate alla base -> ritorno alla base di partenza.
Cosa vuoi ottimizzare?
Senza ulteriori vincoli, e supponendo che le premesse siano corrette, è chiaro che da ogni base conviene mandare prima tutti i lavoratori alla miniera (associata alla base) più vicina; quando questa è esaurita, si mandano alla più vicina di quelle rimanenti, etc.
Mi sono spiegato male:
Associo i le miniere alla base.
I lavoratori riescono in poco tempo a svuotare la miniera.
La miniera si riempie dopo 1 po' k è stata svuotata.
In pratica le basi (non comando i lavoratori, ma quelli partono in automatico) "tengono svuotate le miniere".
Analizziamo questo scenario:[M] è miniera, è base (faccio conto k tutte le basi abbiano = lavoratori e le miniere = risorse)
[M1].[M2]...[B1][M3].....[B2][M4]
è intuitivo k, sarebbe meglio k B1 usasse M1 ed M2, mentre B2 le restanti.
Se invece ogniuno fa la più vicina prima B1 prende M3 e B2 prende M4,
Associo i le miniere alla base.
I lavoratori riescono in poco tempo a svuotare la miniera.
La miniera si riempie dopo 1 po' k è stata svuotata.
In pratica le basi (non comando i lavoratori, ma quelli partono in automatico) "tengono svuotate le miniere".
Analizziamo questo scenario:[M] è miniera, è base (faccio conto k tutte le basi abbiano = lavoratori e le miniere = risorse)
[M1].[M2]...[B1][M3].....[B2][M4]
è intuitivo k, sarebbe meglio k B1 usasse M1 ed M2, mentre B2 le restanti.
Se invece ogniuno fa la più vicina prima B1 prende M3 e B2 prende M4,
Devo dire che non ho capito l'esempio, ma mi pare di capire che i lavoratori di una base possono andare dove gli pare (se fosse così, le miniere non sarebbero associate alle basi).
No, una volta assegnata la miniera alla base, i lavoratori della base partono in automatico e tentano di svuotare la miniera assegnata. La miniera si svuota dopo 1 viaggio. Dopo 1 po' però la miniera si riempie.
Lo scopo assegnare le miniere alle basi in modo k i lavoratori delle basi riescano a tenerle vuote.
L'esempio:
[M1].[M2]...[B1][M3].....[B2][M4]
Il metodo che permette ai lavoratori di fare + giri in meno tempo è quello di assegnare M1 e M2 a B1, ed M3 e M4 a B2.
Se ogni base prendesse inizialmente la miniera + vicina a se libera, B1 prenderebbe M3; poi B2 prenderebbe M4, poi B1 prenderebbe M2 e B2 prenderebbe M1, cosa sbagliata xk si compie più strada.
PS: il senso dei laboratori sta solo nel "quante" miniere può supportare 1 città.
PPS: Il senso della grandezza della miniera sta solo nel "quanta base occupa, quando viene assegnata"
Lo scopo assegnare le miniere alle basi in modo k i lavoratori delle basi riescano a tenerle vuote.
L'esempio:
[M1].[M2]...[B1][M3].....[B2][M4]
Il metodo che permette ai lavoratori di fare + giri in meno tempo è quello di assegnare M1 e M2 a B1, ed M3 e M4 a B2.
Se ogni base prendesse inizialmente la miniera + vicina a se libera, B1 prenderebbe M3; poi B2 prenderebbe M4, poi B1 prenderebbe M2 e B2 prenderebbe M1, cosa sbagliata xk si compie più strada.
PS: il senso dei laboratori sta solo nel "quante" miniere può supportare 1 città.
PPS: Il senso della grandezza della miniera sta solo nel "quanta base occupa, quando viene assegnata"
Ok, allora ogni miniera viene temporaneamente assegnata ad una base, fin quando non viene svuotata. Una volta che è di nuovo piena può essere assegnata ad un'altra base; è così?
no, in pratica lo script serve per assegnare le miniere alle basi in modo circa equilibrato.
Una volta fatto le assegnazioni restano così e il gioco le utilizza per una settimana, poi riparte con lo script per la riassegnazione rifacendo tutto da capo.
Nel gioco le miniere continuano ad essere svuotate come stabilito dallo script
Una volta fatto le assegnazioni restano così e il gioco le utilizza per una settimana, poi riparte con lo script per la riassegnazione rifacendo tutto da capo.
Nel gioco le miniere continuano ad essere svuotate come stabilito dallo script
Io procederei così:
1) costruisci un array con elementi del tipo $(d, i, j)$ così calcolati: per ogni base $i$ e miniera $j$ calcoli la distanza $d = d_{ij}$;
2) ordini l'array in modo crescente rispetto al primo elemento;
3) cicli sugli elementi dell'array; se $e = (d, i, j)$ è l'elemento in questione, se la base $i$ ha ancora lavoratori liberi gli assegni la miniera $j$, altrimenti scarti l'elemento e passi al successivo.
1) costruisci un array con elementi del tipo $(d, i, j)$ così calcolati: per ogni base $i$ e miniera $j$ calcoli la distanza $d = d_{ij}$;
2) ordini l'array in modo crescente rispetto al primo elemento;
3) cicli sugli elementi dell'array; se $e = (d, i, j)$ è l'elemento in questione, se la base $i$ ha ancora lavoratori liberi gli assegni la miniera $j$, altrimenti scarti l'elemento e passi al successivo.
E' sicuramente un metodo efficace ma cmq non risolve il problema dell'esempio che ho riportato.
Per poter superare quel problema bisognerebbe trovare 1 metodo k permetta alle assegnazioni di "interagire" per tentare di minimizzare la distanza totale, non singolarmenete quelle parziali..
Per poter superare quel problema bisognerebbe trovare 1 metodo k permetta alle assegnazioni di "interagire" per tentare di minimizzare la distanza totale, non singolarmenete quelle parziali..
Adesso ho capito.
Da un punto di vista matematico il problema non è banale (si può inquadrare nella classe dei problemi di trasporto ottimo, anche se è semplificato dalla presenza di grandezze intere).
Da un punto di vista algoritmico non ne so molto.
Da un punto di vista matematico il problema non è banale (si può inquadrare nella classe dei problemi di trasporto ottimo, anche se è semplificato dalla presenza di grandezze intere).
Da un punto di vista algoritmico non ne so molto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo