Massimizzare nu di abitanti di una città con certi vincoli
Ciao a tutti, ho un problemo nato da una situazione reale (un giochino online 
) per cui non riesco a scrivere un programma sufficientemente efficiente, quindi avrei bisogno d'aiuto.
Trattasi di riempire una "mappa", ovvero una matrice $n*n$ con delle abitazioni di $h$ tipi (una per "casella", dove per casella intendo una coppia $(i,j)$, che mi identifica una entrata della matrice), indicati con $0,1,2,3,..h-1$: case dello stesso tipo hanno la stessa capienza (intesa come numero di abitanti che può ospitare) $c$, e vale $c
Per esempio, se i tipi sono "baracca", "casa" "condominio" "grattacielo", una casa può essere costruita in $(i,j)$ se e solo se esiste una casella adiacente a $(i,j)$ con una baracca, un condominio può essere costruito in una certa casella se e solo se esistono (almeno) una casella adiacente che contiene una baracca e una casella adiacente che contiene una casa, e cosiì via per il grattacielo.
Il problema consiste nel trovare la mappa che massimizza il numero di abitanti totali della città.
Considerazioni:
1)non ho postato in ricerca operativa perchè nn mi sembra un problema di programmazione lineare, o almeno io non sono riuscito a scriverlo in quella forma.
2)ho quindi optato per una soluzione informatica per il problema con 4 tipi, scrivendomi un programmino in C molto rozzo che semplicemente genera tutte le mappe ammissibili e sceglie poi la migliore.
Tale algoritmo ha un costo computazione spropositato. Ovviamente non genera tutte le $4^(n^2)$ mappe possibili, per un totale di circa $3*4^(n^2)$ chiamate della mia funzione ricorsiva (quel $3$ deriva da dati sperimentali su pochissimi casi, quindi non credo sia molto attendibile), ma solo quelle che sono papabili di ammissibilità.
Il mio algoritmo, quando deve decidere se inserire o no un elemento nella casella in questione, fa due check, uno per vedere se la casella precedente resta ammissibile anche con la nuova abitazione nella casella in considerazione (ovvero se la casa presente nellla casella precedente, ossia subito a sinistra, ha ancora diritto di essere costruita là), e uno che controlla se la casa nella casella immediatamente superiore (se non sono nella prima riga) ha ancora diritto di esistere dopo che si ritrova una nuova casa sotto di lei.
In tal modo le mappe effettivamente costruite sono molte meno (nel caso $n=5$ e $h=4$ sono circa $50*10^9$ invece che $4^25$), ma l'algoritmo esegue comunque un numero di passi spropositato (per risolvere questo caso ci ha impiegato 46 minuti).
Chiedo quindi lumi su come progettare algoritmi un filino più intelligenti del mio, per poter progettare città un pò più grosse di un campo da calcio (supposto quadrato).
Grazie per l'attenzione
) per cui non riesco a scrivere un programma sufficientemente efficiente, quindi avrei bisogno d'aiuto.Trattasi di riempire una "mappa", ovvero una matrice $n*n$ con delle abitazioni di $h$ tipi (una per "casella", dove per casella intendo una coppia $(i,j)$, che mi identifica una entrata della matrice), indicati con $0,1,2,3,..h-1$: case dello stesso tipo hanno la stessa capienza (intesa come numero di abitanti che può ospitare) $c$, e vale $c
Per esempio, se i tipi sono "baracca", "casa" "condominio" "grattacielo", una casa può essere costruita in $(i,j)$ se e solo se esiste una casella adiacente a $(i,j)$ con una baracca, un condominio può essere costruito in una certa casella se e solo se esistono (almeno) una casella adiacente che contiene una baracca e una casella adiacente che contiene una casa, e cosiì via per il grattacielo.
Il problema consiste nel trovare la mappa che massimizza il numero di abitanti totali della città.
Considerazioni:
1)non ho postato in ricerca operativa perchè nn mi sembra un problema di programmazione lineare, o almeno io non sono riuscito a scriverlo in quella forma.
2)ho quindi optato per una soluzione informatica per il problema con 4 tipi, scrivendomi un programmino in C molto rozzo che semplicemente genera tutte le mappe ammissibili e sceglie poi la migliore.
Tale algoritmo ha un costo computazione spropositato. Ovviamente non genera tutte le $4^(n^2)$ mappe possibili, per un totale di circa $3*4^(n^2)$ chiamate della mia funzione ricorsiva (quel $3$ deriva da dati sperimentali su pochissimi casi, quindi non credo sia molto attendibile), ma solo quelle che sono papabili di ammissibilità.
Il mio algoritmo, quando deve decidere se inserire o no un elemento nella casella in questione, fa due check, uno per vedere se la casella precedente resta ammissibile anche con la nuova abitazione nella casella in considerazione (ovvero se la casa presente nellla casella precedente, ossia subito a sinistra, ha ancora diritto di essere costruita là), e uno che controlla se la casa nella casella immediatamente superiore (se non sono nella prima riga) ha ancora diritto di esistere dopo che si ritrova una nuova casa sotto di lei.
In tal modo le mappe effettivamente costruite sono molte meno (nel caso $n=5$ e $h=4$ sono circa $50*10^9$ invece che $4^25$), ma l'algoritmo esegue comunque un numero di passi spropositato (per risolvere questo caso ci ha impiegato 46 minuti).
Chiedo quindi lumi su come progettare algoritmi un filino più intelligenti del mio, per poter progettare città un pò più grosse di un campo da calcio (supposto quadrato).
Grazie per l'attenzione
Risposte
Ovviamente considerando che ci sono solo 4 lati il massimo livello di grattacieli non può superare il 4 (5 tipi). Personalmente direi che si dovrebbe iniziare dalla disposizione dei 4. [...]
Tieni conto inoltre che si scrive un programma più generale si dovrebbe considerare che ogni soluzione è equivalente ad altre 8, non necessariamente distinte (l'orbita di ogni elemento può anche essere formata da 2 o 1 elemento), attraverso l'"azione" del gruppo delle simmetrie del quadrato...
Ma non sono sicuro come questa cosa possa essere usata per rendere il tutto più efficiente.
EDIT: ho levato le 2 disposizioni di 4 che non portavano a nulla...
Tieni conto inoltre che si scrive un programma più generale si dovrebbe considerare che ogni soluzione è equivalente ad altre 8, non necessariamente distinte (l'orbita di ogni elemento può anche essere formata da 2 o 1 elemento), attraverso l'"azione" del gruppo delle simmetrie del quadrato...
Ma non sono sicuro come questa cosa possa essere usata per rendere il tutto più efficiente.
EDIT: ho levato le 2 disposizioni di 4 che non portavano a nulla...
No, dopo un breve calcolo a mente mi sono reso conto che nessuno dei due sia possibile... peccato... tutto sommato è necessario distanziare maggiormente i 4...
Tra l'altro... Vuoi che trovi una soluzione o che le trovi tutte?
No, a me interesserebbe una soluzione sola(forse ha un interesse in se anche il trovarle tutte), e soprattutto le idee e la matematica che hai usato, o che ti sono venute in mente:
dalle tecniche della ricerca operativa all'algebra (ho letto la parola "azione", in effetti avevo pensato anch'io a sfruttare in qualche modo la simmetria del problema), fino ad algoritmi computazionalmente efficienti. Qualunque cosa, lo scopo è risolvere questo problema.
dalle tecniche della ricerca operativa all'algebra (ho letto la parola "azione", in effetti avevo pensato anch'io a sfruttare in qualche modo la simmetria del problema), fino ad algoritmi computazionalmente efficienti. Qualunque cosa, lo scopo è risolvere questo problema.
Cmq io ho risolto con il computer il caso con 4 tipi di case (non 5), nei casi $n=2,3,4,5$, e con $c=i+1$ per ogni $i=0,..,3$. Magari i risultati che ho trovato possono esserti utile per verificare se la strada che stai provando è corretta.
Comunque non può esistere una mappa ottima generale, ovviamente essa varia in funzione del vettore $c$, quindi non credo si pèossa evitare di passare dalla ricerca operativa o dall'informatica. Però qualunque idea è ben gradita.
Comunque non può esistere una mappa ottima generale, ovviamente essa varia in funzione del vettore $c$, quindi non credo si pèossa evitare di passare dalla ricerca operativa o dall'informatica. Però qualunque idea è ben gradita.
Con alcune prove sono arrivato alla soluzione che probabilmente nessuna soluzione nelle caselle 5x5 possiede più di un 4 (centrale?). D'altra parte è possibile che la soluzione ottimale (se esiste) non abbia palazzi così alti (stavo pensando a soluzioni con quattro 3). Ma per arrivare ad una soluzione devo fare ancora qualche prova.
[edit] Alcune soluzioni per il caso 5x5 con case con meno di 4 piani. Trovate a mano...
01100
03231
12021
13230
00110
totale 28 (puoi controllare se posso migliorarlo cambiando qualche casa)
01302
01201
32023
10210
20310
totale 30
Alcune con 4 piani
02031
11420
20312
31203
02101
totale 35 (per ora il più alto che ho trovato)
01120
12031
11420
00312
21201
totale 31
[edit] Alcune soluzioni per il caso 5x5 con case con meno di 4 piani. Trovate a mano...
01100
03231
12021
13230
00110
totale 28 (puoi controllare se posso migliorarlo cambiando qualche casa)
01302
01201
32023
10210
20310
totale 30
Alcune con 4 piani
02031
11420
20312
31203
02101
totale 35 (per ora il più alto che ho trovato)
01120
12031
11420
00312
21201
totale 31
Per soluzione intendevo una soluzione ottima, non una qualunque mappa ammissibile.
Nelle due soluzioni che hai scritto hai considerato $c=i$, io avevo fatto $c=i+1$ (una casa con 0 abitanti sarebbe un pò inutile...), e in questo modo gli abitanti per le tue mappe sono $53$ e $55$. La mappa ottima contiene invece $61$ abitanti, ed è la seguente
0 1 2 3 0
2 3 0 1 2
1 3 2 3 0
0 0 1 2 3
1 2 3 0 1
Ma a parte questo, hai avuto qualche idea per un algoritmo efficiente o un metodo di risoluzione matematico (anche solo nel caso con al massimo 4 piani)?
P.S. magari è meglio spostare in ricerca operativa, anche se il problema può riguardare entrambi gli argomenti...chissà magari stavolta i moderatori faranno un'eccezione al multi-posting..chiedo un loro parere.
Nelle due soluzioni che hai scritto hai considerato $c=i$, io avevo fatto $c=i+1$ (una casa con 0 abitanti sarebbe un pò inutile...), e in questo modo gli abitanti per le tue mappe sono $53$ e $55$. La mappa ottima contiene invece $61$ abitanti, ed è la seguente
0 1 2 3 0
2 3 0 1 2
1 3 2 3 0
0 0 1 2 3
1 2 3 0 1
Ma a parte questo, hai avuto qualche idea per un algoritmo efficiente o un metodo di risoluzione matematico (anche solo nel caso con al massimo 4 piani)?
P.S. magari è meglio spostare in ricerca operativa, anche se il problema può riguardare entrambi gli argomenti...chissà magari stavolta i moderatori faranno un'eccezione al multi-posting..chiedo un loro parere.
Bella la soluzione da 61... Personalmente ho paura che l'algoritmo sia NP-completo... In quel caso potrebbe essere interessante trovare un algoritmo polinomiale con una approssimazione accettabile. D'altra parte ho trovato una soluzione da 60 a mano e un po' a caso... Devo provare con matrici di dimensioni differenti per capire se riesco a produrre un algoritmo che imiti il mio ragionamento (che ho paura sia in gran parte casuale)...
Senza darmi il risultato quanto è il massimo con matrici 4x4... per ora (dopo 2-3 tentativi) il massimo che ho trovato è 49...
Senza darmi il risultato quanto è il massimo con matrici 4x4... per ora (dopo 2-3 tentativi) il massimo che ho trovato è 49...
Strano, il mio programma ha sputato che il massimo per la 4*4 è $37$...
"alvinlee88":
Strano, il mio programma ha sputato che il massimo per la 4*4 è $37$...
Avevo sbagliato il calcolo... :p Mi era venuto 39... 23+16 (continuo a calcolare come prima, tanto sono solo risultati traslati.
Eccola...
2101
0423
2310
1021
----------------
5855 = 23 + 16 = 39
Ma probabilmente senza usare i 4 il risultato massimo è minore... Senza usare il 4 ero arrivato appena a 35...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo