Als ich über Knuths Algorithmus X las, um das genaue Cover-Problem zu lösen, dachte ich an einen Edge-Case, an dem ich eine Klarstellung machen wollte.
Hier sind meine Annahmen:
- Bei gegebener Matrix A ist das Ziel des Algorithmus X "s", eine Teilmenge der Zeilen so auszuwählen, dass die Ziffer 1 in jeder Spalte erscheint genau einmal. "
- Wenn die Matrix leer ist, wird der Algorithmus erfolgreich beendet und die Lösung ist dann die Teilmenge der Zeilen, die bis zu diesem Punkt in der Teillösung protokolliert wurden.
- Wenn es eine Spalte von 0 "s gibt, wird der Algorithmus erfolglos beendet.
Als Referenz: http://en.wikipedia.org/wiki/Algorithm_X
Betrachten Sie die Matrix A: [[1 1 0] [0 1 1]]
Schritte, die ich gemacht habe:
Gegebene Matrix 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}.
Dies ist jedoch eindeutig nicht der Fall, da Zeile 1 nur aus [1 1 0] besteht und die 3. Spalte eindeutig nicht abdeckt.
Ich würde annehmen, dass der Algorithmus irgendwann die Matrix bis zu dem Punkt reduzieren sollte, wo es nur eine einzige 0 gibt und erfolglos endet.
Könnte jemand bitte das erklären?
Antworten:
1 für die Antwort № 1Ich denke, die Verwirrung hier ist einfach in der Verwendung des Begriffs leere Matrix. Wenn Sie Knuths Originalarbeit lesen (verlinkt aufden Wikipedia-Artikel, den Sie zitiert haben), Sie können sehen, dass er die Zeilen und Spalten als doppelt verknüpfte Listen behandelt hat. Wenn er sagt, dass die Matrix leer ist, bedeutet das nicht, dass es keine Einträge hat, das bedeutet, dass alle Zeilen- und Spaltenobjekte gelöscht wurden.
Zur Klarstellung bezeichne ich die Zeilen mit Kleinbuchstaben und die Spalten mit Großbuchstaben wie folgt:
| A | B | C
---------------
a | 1 | 1 | 0
---------------
b | 0 | 1 | 1
Der Algorithmus gibt an, dass Sie eine Spalte auswählendeterministisch (mit einer beliebigen Regel, die Sie wünschen), und er schlägt vor, eine Spalte mit der geringsten Anzahl von 1 "s zu wählen. Also, wir werden fortfahren, wie Sie vorschlagen und Spalte wählen EIN. Die einzige Zeile mit einer 1 in Spalte EIN ist Reihe einAlso wählen wir eine Reihe ein und füge es der möglichen Lösung hinzu { ein }. Jetzt, rudern ein hat 1s in Spalten EIN und BDaher müssen wir diese Spalten und alle Zeilen löschen, die 1s in diesen Spalten enthalten, also Zeilen ein und bSo wie du es getan hast. Die resultierende Matrix hat eine einzelne Spalte C und keine Zeilen:
| C
-------
Dies ist keine leere Matrix (es ist noch eine Spalte vorhanden). Jedoch Spalte C hat keine 1s drin, also beenden wir erfolglos, wie der Algorithmus anzeigt.
Dies mag seltsam erscheinen, aber es ist ein sehr wichtiger Fall, wenn wir beabsichtigen, eine Inzidenzmatrix für die Genaues Cover-Problem, weil Spalten Elemente der Menge X darstellendas, was wir abdecken wollen, und Zeilen repräsentieren Teilmengen von X. Eine Matrix mit einigen Spalten und ohne Zeilen repräsentiert also das Problem, dass die Auswahl der zu wählenden Teilmengen leer ist (aber es gibt noch Punkte, die abgedeckt werden müssen).
Wenn diese Beschreibung Probleme für Sie verursachtImplementation gibt es eine einfache Problemumgehung: Fügen Sie einfach die leere Menge in jedes Problem ein. Die leere Menge (die keine Punkte von X enthält) wird durch eine Reihe von Nullen dargestellt. Es wird niemals von Ihrem Algorithmus als Teil einer Lösung ausgewählt, kollidiert niemals mit anderen ausgewählten Zeilen, sondern stellt immer sicher, dass die Matrix nicht leer ist (es gibt mindestens eine Zeile), bis alle Spalten gelöscht wurden, was wirklich alles ist Vorsicht, da Sie sicherstellen müssen, dass jede Spalte von einer Reihe abgedeckt ist.