Minimizzare numero di rettangoli sugli assi cartesiani
Ciao a tutti,
vorrei sottoporvi un problema,
immaginando che mi trovi in una situazione simile a quella in figura sopra ho bisogno di trovare il minimo numero
di rettangoli che siano equivalenti a quelli di partenza rispettando i colori, ovvero dove un aerea è verde deve rimanere verde..
nella soluzione finale posso prevedere delle sovrapposizioni, ovvero due rettangoli uno sopra l'altro,
infine si deve tenere conto che lo sfondo ha un colore o rosso o verde.
quindi la figura inizale potrebbe essere semplificata in uno di questi due modi:
Ero in dubbio se mettere il prob qua o nella sezione di ric operativa..
quello che abbiamo pensato di fare è di numerare gli intervalli che troviamo sugli assi con dei nuemri binari e
provare a minizzare l'espressione così ottenuta, ma nn siamo molto convinti (anche perchè dobbiamo
implementarlo su pc e il prob sembra essere NP completo o quasi, simile al prob dello zaino se qualcuno lo conosce..)
cmq i prob di impl nn ci interessano immediatamente, vorremo sapere se sesitono delle soluzioni migliori, magari
già utilizzate per prob simili...
Ciao a tutti
Grazie
Alberto
vorrei sottoporvi un problema,
immaginando che mi trovi in una situazione simile a quella in figura sopra ho bisogno di trovare il minimo numero
di rettangoli che siano equivalenti a quelli di partenza rispettando i colori, ovvero dove un aerea è verde deve rimanere verde..
nella soluzione finale posso prevedere delle sovrapposizioni, ovvero due rettangoli uno sopra l'altro,
infine si deve tenere conto che lo sfondo ha un colore o rosso o verde.
quindi la figura inizale potrebbe essere semplificata in uno di questi due modi:
Ero in dubbio se mettere il prob qua o nella sezione di ric operativa..
quello che abbiamo pensato di fare è di numerare gli intervalli che troviamo sugli assi con dei nuemri binari e
provare a minizzare l'espressione così ottenuta, ma nn siamo molto convinti (anche perchè dobbiamo
implementarlo su pc e il prob sembra essere NP completo o quasi, simile al prob dello zaino se qualcuno lo conosce..)
cmq i prob di impl nn ci interessano immediatamente, vorremo sapere se sesitono delle soluzioni migliori, magari
già utilizzate per prob simili...
Ciao a tutti
Grazie
Alberto
Risposte
Spiegami se ho capito: devi trovare il minimo numero di rettangoli verdi la cui somma delle aree uguagli la somma delle aree dei rettangoli verdi della prima figura, e idem per quelli rossi?
non è un problema strettamente legato alle aree (almeno per come lo intendo io..) quello che mi interessa è esclusivamente minimizzare il numero di
rettangoli, se poi l'area totale dei rettangoli è maggiore nn importa, la cosa che interessa è che le zone verdi rimangano verdi e quelle rosse riamangano
rosse. Quelle non colorate hanno un colere di deafault (diciamo che è semrpe rosso)
Ad esempio questa sol va bene
come andrebbe bene anche una sol in cui i due rett sopra vengono "fusi" insieme
rettangoli, se poi l'area totale dei rettangoli è maggiore nn importa, la cosa che interessa è che le zone verdi rimangano verdi e quelle rosse riamangano
rosse. Quelle non colorate hanno un colere di deafault (diciamo che è semrpe rosso)
Ad esempio questa sol va bene
come andrebbe bene anche una sol in cui i due rett sopra vengono "fusi" insieme
"kappaalby":
non è un problema strettamente legato alle aree (almeno per come lo intendo io..) quello che mi interessa è esclusivamente minimizzare il numero di
rettangoli, se poi l'area totale dei rettangoli è maggiore nn importa, la cosa che interessa è che le zone verdi rimangano verdi e quelle rosse riamangano
rosse. Quelle non colorate hanno un colere di deafault (diciamo che è semrpe rosso)
Ad esempio questa sol va bene
come andrebbe bene anche una sol in cui i due rett sopra vengono "fusi" insieme
Beh, però se le zone verdi devono rimanere verdi allora stai chiedendo che le aree siano uguali: vuoi "tappezzare" con il minimo numero di rettangoli verdi possibile la zona già colorata di verde.
Il problema però è che nel secondo grafico quelli verdi non sono rettangoli.
----
Beh, però se le zone verdi devono rimanere verdi allora stai chiedendo che le aree siano uguali: vuoi "tappezzare" con il minimo numero di rettangoli verdi possibile la zona già colorata di verde.
----
in parte è così
----
Il problema però è che nel secondo grafico quelli verdi non sono rettangoli.
----
per me sono due rettangoli sovrapposti, uno più importante dell'altro, considera questo esempio:
sono due rettangoli e sono già il numero minimo, se cercassi il numero minimo di rettangoli verdi per
coprire l'area verde ne otterrei 4, giusto?
In realtà nel mio prob i rettangoli sono le regole di un firewall, che hanno una priorità e che possono sovrapporsi
il alcune zone, nelle zone di sovrappossizione "vince" la regola che ha priorità maggiore, quindi deve essere considerata
solo quella regola
Beh, però se le zone verdi devono rimanere verdi allora stai chiedendo che le aree siano uguali: vuoi "tappezzare" con il minimo numero di rettangoli verdi possibile la zona già colorata di verde.
----
in parte è così
----
Il problema però è che nel secondo grafico quelli verdi non sono rettangoli.
----
per me sono due rettangoli sovrapposti, uno più importante dell'altro, considera questo esempio:
sono due rettangoli e sono già il numero minimo, se cercassi il numero minimo di rettangoli verdi per
coprire l'area verde ne otterrei 4, giusto?
In realtà nel mio prob i rettangoli sono le regole di un firewall, che hanno una priorità e che possono sovrapporsi
il alcune zone, nelle zone di sovrappossizione "vince" la regola che ha priorità maggiore, quindi deve essere considerata
solo quella regola
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo