Split k imposta su 2 gruppi di set

0

Dato k set, ognuno contiene diversi elementi.

Voglio dividerli in due gruppi,

il primo gruppo contiene m set, il secondo gruppo contiene n set, m + n = k.

Sia w1 la somma dei pesi di tutti gli elementi nell'unione del primo gruppo di insiemi.

e w2 sono la somma dei pesi di tutti gli elementi nell'unione del secondo gruppo di insiemi.

Disegna un algoritmo per suddividere i k set in due gruppi in modo che w1 * m + w2 * n abbia il valore minimo.

Algoritmo 1:

Imposta il primo gruppo vuoto, quindi continua a fare queste operazioni: muoversi in un set dal gruppo due al gruppo uno; spostando un set dal gruppo 1 al gruppo 2; o passare due serie nei due gruppi; ogni passaggio non deve aumentare il valore w1 * m + w2 * n finché non è possibile eseguire altre operazioni. Non funziona, posso facilmente trovare dei controesempi quando questo algoritmo si arresta, il valore non è minimo.

Algoritmo 2:

Per prima cosa dividiamo i k set in k gruppi, ognuno contiene un set. Quindi, dividi i gruppi k in gruppi k-1 in modo che il valore Σw m sia minimo, ora i due gruppi nello stesso gruppo, consideriamo che sono sempre nello stesso gruppo, quindi dividi i gruppi k-1 in gruppi k-2 in modo che il valore Σw m sia minimo ... finché non abbiamo solo due gruppi. Non funziona, posso facilmente trovare controesempi.

    
posta iouvxz 19.07.2016 - 10:36
fonte

1 risposta

1

Supponendo che Brute Force non sia un approccio accettabile, il tuo problema è NP Hard, il che significa che non è possibile risolverlo efficacemente per la complessità operativa del caso peggiore. Tuttavia, questa soluzione può essere ottimizzata.

Questo è fondamentalmente un problema di ottimizzazione . È necessario trovare la migliore soluzione per un insieme discreto di variabili. Ammesso che il numero di combinazioni possibili sarebbe enorme potenzialmente ma è certamente discreto.

In particolare si tratta di un problema di ottimizzazione combinatoria.

Dato che ci sono k set ciascuno con una misura di peso. Questi k set possono essere divisi solo in un numero discreto di modi (per esempio k = 4 allora ci sono 7 possibili combinazioni distinte di m e n). Sono troppo pigro per fare i calcoli per una formula che trova tutte le combinazioni distinte per ogni k ma non è importante a meno che tu non debba conoscere anche il peggiore numero di operazioni.

C'è un corrispondente Problema decisionale in un'ottica combinatoria. Questo è per ogni f (m, n, o), c'è QUALUNQUE soluzione per f (m, n, o) dove o < = 10?

Se true allora se una soluzione era = 10 quindi controlla le soluzioni rimanenti dove f (m, n, o) dove o < = 9?

Se è vero e incontri, dici 7 dove si trova < di 9 poi sulla tua prossima iterazione inizia a controllare tutte le combinazioni rimanenti per < = 6.

Se incontri false dopo aver esaurito le combinazioni rimanenti per 6, ricorda che i valori per me vanno 7 come il migliore possibile per quel k.

Questo può ottimizzare l'algoritmo ed essere migliore della forza bruta scartando immediatamente le combinazioni se m w1 o n w2 sono più di o.

    
risposta data 19.07.2016 - 15:02
fonte

Leggi altre domande sui tag