Mentre stavo leggendo sull'Algoritmo X di Knuth per risolvere l'esatto problema di copertura, ho pensato a un caso limite su cui volevo qualche chiarimento.
Ecco le mie ipotesi:
- Data una matrice A, l'obiettivo "Algorithm X" è selezionare un sottoinsieme delle righe in modo che la cifra 1 appaia in ogni colonna esattamente una volta".
- Se la matrice è vuota, l'algoritmo termina correttamente e la soluzione è quindi il sottoinsieme di righe registrate nella soluzione parziale fino a quel punto.
- Se c'è una colonna di 0 "s, l'algoritmo termina senza successo.
Per riferimento: http://en.wikipedia.org/wiki/Algorithm_X
Considera la matrice A: [[1 1 0] [0 1 1]]
Passi che ho preso:
Data matrice A:
1. Choose a column, c, with the least number of 1"s. I choose: column 1
2. Choose a row, r, that contains to a 1 in column c. I choose: row 1
3. Add r to the partial solution.
4. For each column j such that A(r, j) = 1:
For each row i such that A(i, j) = 1:
delete row i
delete column j
5. Matrix A is empty. Algorithm terminates successfully and solution is allegedly: {row 1}.
Tuttavia, questo non è chiaramente il caso in quanto la riga 1 consiste solo di [1 1 0] e chiaramente non copre la 3a colonna.
Suppongo che l'algoritmo debba a un certo punto ridurre la matrice al punto in cui esiste un solo 0 e terminare senza successo.
Qualcuno potrebbe spiegare questo?
risposte:
1 per risposta № 1Penso che la confusione qui sia semplicemente nell'uso del termine matrice vuota. Se leggi la carta originale di Knuth (collegata sul'articolo di Wikipedia che hai citato), puoi vedere che stava trattando le righe e le colonne come liste a doppio collegamento. Quando dice che la matrice è vuota, non intende dire che non ha voci, vuol dire che tutti gli oggetti riga e colonna sono stati cancellati.
Per chiarire, I'll etichetta le righe con lettere minuscole e le colonne con lettere maiuscole, come segue:
| A | B | C
---------------
a | 1 | 1 | 0
---------------
b | 0 | 1 | 1
L'algoritmo indica che si sceglie una colonnadeterministicamente (usando qualsiasi regola tu desideri), e suggerisce di scegliere una colonna con il minor numero di 1 ". Quindi, procederemo mentre suggerisci e scegli la colonna UN. L'unica riga con una colonna 1 in UN è una riga un, quindi abbiamo scelto la riga un e aggiungilo alla possibile soluzione { un }. Ora, fila un ha 1s in colonne UN e B, quindi dobbiamo cancellare quelle colonne e tutte le righe contenenti 1s in quelle colonne, cioè le righe un e B, proprio come hai fatto tu. La matrice risultante ha una singola colonna C e nessuna riga:
| C
-------
Questa non è una matrice vuota (ha una colonna rimanente). Tuttavia, colonna C non ha 1 in esso, quindi terminiamo senza successo, come indica l'algoritmo.
Questo può sembrare strano, ma è un caso molto importante se intendiamo utilizzare una matrice di incidenza per il Esatto problema di copertura, perché le colonne rappresentano gli elementi dell'insieme Xche vogliamo coprire e le righe rappresentano sottoinsiemi di X. Quindi una matrice con alcune colonne e nessuna riga rappresenta il problema esatto di copertura in cui la raccolta di sottoinsiemi da cui scegliere è vuota (ma ci sono ancora punti da coprire).
Se questa descrizione causa problemi al tuoimplementazione, c'è una soluzione semplice: basta includere il set vuoto in ogni problema. Il set vuoto (che non contiene punti di X) è rappresentato da una riga di tutti gli zeri. Non è mai selezionato dal tuo algoritmo come parte di una soluzione, non collide mai con altre righe selezionate, ma garantisce sempre che la matrice non sia vuota (c'è almeno una riga) fino a quando tutte le colonne non sono state cancellate, il che è tutto preoccuparsi poiché è necessario assicurarsi che ogni colonna sia coperta da qualche riga.