Algorytm X do rozwiązania dokładnej osłony: Fat Matrices - algorytm, macierz, liniowa algebra, sudoku

Kiedy czytałem o Algorytmie X Knutha, aby rozwiązać problem dokładnego pokrycia, pomyślałem o przypadku, który chciałem wyjaśnić.

Oto moje założenia:

1. Biorąc pod uwagę macierz A, celem algorytmu X „s” jest wybranie podzbioru wierszy, tak aby cyfra 1 pojawiła się w każdej kolumnie dokładnie raz. "
2. Jeśli macierz jest pusta, algorytm kończy się pomyślnie, a rozwiązanie jest wtedy podzbiorem wierszy zarejestrowanych w częściowym rozwiązaniu do tego momentu.
3. Jeśli istnieje kolumna 0 ”, algorytm kończy się bezskutecznie.

Na przykład: http://en.wikipedia.org/wiki/Algorithm_X

Rozważmy macierz A: [[1 1 0] [0 1 1]]

Kroki, które podjąłem:

Biorąc pod uwagę 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}.

Nie jest to jednak oczywiste, ponieważ wiersz 1 składa się tylko z [1 1 0] i wyraźnie nie obejmuje trzeciej kolumny.

Zakładam, że algorytm powinien w pewnym momencie zredukować macierz do punktu, w którym jest tylko jedno 0 i zakończyć się bezskutecznie.

Czy ktoś mógłby to wyjaśnić?

Odpowiedzi:

1 dla odpowiedzi № 1

Myślę, że zamieszanie tutaj jest po prostu w użyciu tego terminu pusta matryca. Jeśli czytasz oryginalny dokument Knutha (połączony naartykuł cytowany w Wikipedii), widać, że traktował wiersze i kolumny jako listy podwójnie powiązane. Kiedy mówi, że macierz jest pusta, nie oznacza, że ​​nie ma żadnych wpisów, oznacza to, że wszystkie obiekty wierszy i kolumn zostały usunięte.

Aby to wyjaśnić, „Oznaczę wiersze małymi literami, a kolumny wielkimi literami w następujący sposób:

   | A | B | C
---------------
a | 1 | 1 | 0
---------------
b | 0 | 1 | 1

Algorytm stwierdza, że ​​wybierasz kolumnędeterministycznie (stosując dowolną regułę) i sugeruje wybranie kolumny z najmniejszą liczbą 1 ”s. Więc, będziemy postępować zgodnie z sugestią i wybrać kolumnę ZA. Jedyny rząd z kolumną 1 w ZA jest wiersz za, więc wybieramy wiersz za i dodaj to do możliwego rozwiązania { za }. Teraz, wiersz za ma 1s w kolumnach ZA i b, więc musimy usunąć te kolumny i wszystkie wiersze zawierające 1s w tych kolumnach, czyli wierszach za i b, tak jak ty. Powstała macierz ma pojedynczą kolumnę do i bez wierszy:

   | C
-------

To nie jest pusta matryca (ma kolumnę pozostałą). Jednak kolumna do nie ma w nim 1s, więc kończymy bezskutecznie, jak wskazuje algorytm.

Może się to wydawać dziwne, ale jest to bardzo ważny przypadek, jeśli zamierzamy użyć macierzy częstości dla Dokładny problem z okładką, ponieważ kolumny reprezentują elementy zbioru Xktóre chcemy pokryć, a wiersze reprezentują podzbiory X. Tak więc macierz z niektórymi kolumnami i bez wierszy reprezentuje dokładny problem obejmujący, gdzie zbiór podzbiorów do wyboru jest pusty (ale nadal są punkty do pokrycia).

Jeśli ten opis powoduje problemy dla twojegoimplementacja, istnieje proste obejście: po prostu dołącz pusty zestaw do każdego problemu. Pusty zestaw (nie zawierający punktów X) jest reprezentowany przez rząd wszystkich zer. Nigdy nie jest wybierany przez algorytm jako część rozwiązania, nigdy nie koliduje z innymi wybranymi wierszami, ale zawsze zapewnia, że ​​macierz jest niepusta (jest co najmniej jeden wiersz), dopóki wszystkie kolumny nie zostaną usunięte, co jest naprawdę wszystkim. dbaj o to, ponieważ musisz upewnić się, że każda kolumna jest pokryta jakimś rzędem.

---