Problema delle coppie
Mi è stato proposto da tempo un problema matematico per il quale credo di essere arrivato a una soluzione ma non ho ancora trovato il modo di dimostrarla... vediamo se mi potete dare una mano:
Ho k coppie di elementi (diciamo numeri).
Ogni coppia è formata da 2 numeri diversi.
In coppie diverse può ripetersi lo stesso numero.
Se si sceglie un numero, si eliminano tutte le coppie che lo contengono.
Come trovare il numero minimo di elementi da scegliere per eliminare tutte le coppie?
Intuitivamente ho pensato a un algoritmo, ma non saprei come dimostrarne l'efficacia:
Si ordinano le coppie: L'ordine è ininfluente.
Si prende la prima coppia, si conta in quante coppie compare il primo elemento e in quante il secondo.
Si sceglie l'elemento che compare in più coppie e si cancellano dalla lista tutte le coppie che lo contengono (compresa la coppia stessa da dove è scelto). Se il numero è uguale se ne prende uno qualsiasi.
Si passa alla seconda coppia e si ripete il procedimento.
Alla fine il numero di scelte che si sono fatte dovrebbe essere il numero minimo di scelte possibili.
che ne dite?
Esempio:
Ho le coppie
1-2, 2-3, 3-1, 4-2, 5-3, 4-1, 2-5, 1-5, 5-6
Prendo la prima, l'1 è contenuto in 4 coppie e il 2 è contenuto in 4 coppie quindi ne scelgo uno qualsiasi, diciamo l'1.
Cancello tutte le coppie che contengono l'1 e mi rimane:
2-3, 4-2, 5-3, 2-5, 5-6
Ora prendo la coppia 2-3. Il 2 è contenuto in 3 coppie e il 3 in 2 coppie, quindi scelgo il 2.
Cancello tutte le coppie che contengono il 2 e mi rimane:
5-3, 5-6
Adesso Scelgo il 5 e ho fatto.
Il numero minimo di scelte è 3.
Ho k coppie di elementi (diciamo numeri).
Ogni coppia è formata da 2 numeri diversi.
In coppie diverse può ripetersi lo stesso numero.
Se si sceglie un numero, si eliminano tutte le coppie che lo contengono.
Come trovare il numero minimo di elementi da scegliere per eliminare tutte le coppie?
Intuitivamente ho pensato a un algoritmo, ma non saprei come dimostrarne l'efficacia:
Si ordinano le coppie: L'ordine è ininfluente.
Si prende la prima coppia, si conta in quante coppie compare il primo elemento e in quante il secondo.
Si sceglie l'elemento che compare in più coppie e si cancellano dalla lista tutte le coppie che lo contengono (compresa la coppia stessa da dove è scelto). Se il numero è uguale se ne prende uno qualsiasi.
Si passa alla seconda coppia e si ripete il procedimento.
Alla fine il numero di scelte che si sono fatte dovrebbe essere il numero minimo di scelte possibili.
che ne dite?
Esempio:
Ho le coppie
1-2, 2-3, 3-1, 4-2, 5-3, 4-1, 2-5, 1-5, 5-6
Prendo la prima, l'1 è contenuto in 4 coppie e il 2 è contenuto in 4 coppie quindi ne scelgo uno qualsiasi, diciamo l'1.
Cancello tutte le coppie che contengono l'1 e mi rimane:
2-3, 4-2, 5-3, 2-5, 5-6
Ora prendo la coppia 2-3. Il 2 è contenuto in 3 coppie e il 3 in 2 coppie, quindi scelgo il 2.
Cancello tutte le coppie che contengono il 2 e mi rimane:
5-3, 5-6
Adesso Scelgo il 5 e ho fatto.
Il numero minimo di scelte è 3.
Risposte
Ahimè ho trovato che l'algoritmo non vale anche se dopo un sacco di prove sembrava di sì.
esempio prendiamo le coppie:
(a,A) (a,B) (a,C) (b,A) (b,D) (c,A) (c,E)
se applichiamo l'algoritmo scegliendo come prima scelta (a) invece di (A) -visto che sono presenti in ugual numero- la risposta è 3, se scegliamo (A) la risposta è 4.
esempio prendiamo le coppie:
(a,A) (a,B) (a,C) (b,A) (b,D) (c,A) (c,E)
se applichiamo l'algoritmo scegliendo come prima scelta (a) invece di (A) -visto che sono presenti in ugual numero- la risposta è 3, se scegliamo (A) la risposta è 4.
Il tuo problema può essere interpretato come un problema di minimum hitting set; puoi fare una ricerca bibliografica sugli algoritmi utilizzabili (tipicamente si tratta di Integer Linear Programming).
C'è una pagina su wikipedia:
https://en.wikipedia.org/wiki/Set_cover_problem
C'è una pagina su wikipedia:
https://en.wikipedia.org/wiki/Set_cover_problem
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo