punti ponderati Dato su un aereo, trovare luoghi per U piazze tale che il peso totale racchiusa sarebbe massimizzato

che sto di fronte alla seguente problema:punti ponderati Dato su un aereo, trovare luoghi per U piazze tale che il peso totale racchiusa sarebbe massimizzato

Dato

Un insieme di punti su un piano euclideo, ogni punto P (x, y, w) ha coordinate e un peso positivo associato.
Un insieme di U piazze, aventi tutti la stessa lunghezza taglia L.

Calcio:

Assign (trovare spazi per) i quadrati tali che il peso totale dei punti racchiuso all'interno tutti i quadrati sarebbero massimizzati.

Note:

I quadrati dovrebbero essere parallela all'asse
I quadrati possono sovrapporsi, ma i pesi allegati non saranno contati più di una volta.

Sto cercando un incarico ottimale .

Le mie domande:

Si tratta di un problema noto (Fa ha un nome È già stato esplorato prima?).
Qualche idea su come affrontarlo?

(I possono essere tenuti a parlare di quello che ho provato. Dal momento che sto cercando un ottimale incarico , le mie idee euristiche non sono davvero rilevanti. A questo punto non ho idea di come trovare l'ottimale assegnazione).

fonte

2013-08-27 Lior Kogan

Si prega di chiarire la definizione di un quadrato U. E racchiuso in tutti i quadrati, non intendi che i punti debbano essere nel piano del quadrato, ma contenuti all'interno di alcuni set di riquadri, dove ciascun lato è composto da questi quadrati paralleli ad assi, o si intersecano con altri tali scatole? –

@ RobertJørgensgaardEngdahl: U è il numero dei quadrati di uguali dimensioni in cui voglio trovare posizioni ottimali. I quadrati sono sullo stesso piano dei punti (questo è un problema 2D). –

Puoi aggiungere un'immagine di ciò che il programma dovrebbe fare in 2D? – jambono

È un caso geometrico speciale della ponderata maximum coverage problem. L'MCP generale è NP-hard, e sospetto che anche questo caso speciale sia, a differenza del caso generale, probabilmente ha un efficiente schema di approssimazione del tempo polinomiale. Tuttavia, si desidera una soluzione ottimale, quindi la prima cosa che consiglierei è di inserire la formulazione di programmazione lineare intera nell'articolo Wikipedia collegato a un risolutore di LP.

maximize sum_j (w_j * y_j) 
subject to 
for all i, sum_i x_i <= U 
for all j, sum_{i : j in S_i} x_i - y_j >= 0 
for all i, x_i in {0, 1} 
for all j, 0 <= y_j <= 1

Il peso w_j di ogni punto j è dato, e gli insiemi S_i sono tutte le possibilità di coprire punti con una larghezza L quadrato. Il significato di x_i è se è selezionato il set S_i. Il significato di y_j è se il punto j è coperto. L'algoritmo cubico più semplice per costruire il S_i s è enumerare tutti i quadrati il cui vertice in basso a sinistra ha una coordinata x uguale a quella di un punto e una coordinata y uguale a quella di qualche punto (eventualmente altro), poiché ogni altro quadrato può essere fatto scorrere e/a destra senza sacrificare la copertura.

fonte

2013-08-27 13:31:16

Grazie David. Hai per caso un riferimento a una descrizione più estesa di un metodo per la costruzione di S_i? (Quali strutture dati usare, ecc.) –

@LiorKogan Non ho un riferimento a portata di mano, dato che l'ho appena pensato.In modo leggermente più dettagliato, l'algoritmo è quello di raccogliere e ordinare le coordinate x dei punti, raccogliere e ordina le coordinate y dei punti, per x nelle coordinate x, per y nelle coordinate y, scansiona gli altri punti per vedere quale appartiene al quadrato di larghezza L il cui lato sinistro ha x-coordinate x e il cui lato inferiore ha la coordinata y. Sospetto che sarebbe controproducente utilizzare le strutture dati qui, dato che risolvere il programma intero richiederà un po 'di tempo. –

punti ponderati Dato su un aereo, trovare luoghi per U piazze tale che il peso totale racchiusa sarebbe massimizzato

risposta

Problemi correlati