L'algorithme X pour résoudre la couverture exacte: matrices grasses - algorithme, matrice, algèbre linéaire, sudoku

Alors que je lisais sur l'algorithme X de Knuth pour résoudre le problème de couverture exact, j'ai pensé à un cas de bord sur lequel je voulais des éclaircissements.

Voici mes hypothèses:

1. Étant donné une matrice A, le but de l'algorithme X est de sélectionner un sous-ensemble des lignes de sorte que le chiffre 1 apparaisse dans chaque colonne exactement une fois. "
2. Si la matrice est vide, l'algorithme se termine avec succès et la solution est alors le sous-ensemble de lignes enregistrées dans la solution partielle jusqu'à ce point.
3. S'il y a une colonne de 0 ", l'algorithme se termine sans succès.

Pour référence: http://en.wikipedia.org/wiki/Algorithm_X

Considérez la matrice A: [[1 1 0] [0 1 1]]

Les étapes que j'ai prises:

Étant donné la 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}.

Cependant, ce n'est clairement pas le cas car la ligne 1 ne comprend que [1 1 0] et ne couvre clairement pas la 3e colonne.

Je suppose que l'algorithme devrait à un moment donné réduire la matrice au point où il n'y a qu'un seul 0 et se terminer sans succès.

Quelqu'un pourrait-il expliquer cela?

Réponses:

1 pour la réponse № 1

Je pense que la confusion ici est simplement dans l'utilisation du terme matrice vide. Si vous lisez le document original de Knuth (lié surl'article de Wikipédia que vous avez cité), vous pouvez voir qu'il traitait les lignes et les colonnes comme des listes à double liaison. Quand il dit que la matrice est vide, cela ne signifie pas qu'elle n'a pas d'entrées, cela signifie que tous les objets de ligne et de colonne ont été supprimés.

Pour clarifier, je vais étiqueter les lignes avec des lettres minuscules et les colonnes avec des lettres majuscules, comme suit:

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

L'algorithme indique que vous choisissez une colonnede manière déterministe (en utilisant n'importe quelle règle que vous souhaitez), et il suggère de choisir une colonne avec le plus petit nombre de 1 "s. Donc, nous allons procéder comme vous le suggérez et choisir la colonne UNE. La seule ligne avec un 1 dans la colonne UNE est rangée une, donc nous choisissons la ligne une et ajoutez-le à la solution possible { une }. Maintenant, rangée une a 1 dans les colonnes UNE et B, nous devons donc supprimer ces colonnes, ainsi que toutes les lignes contenant des 1 dans ces colonnes, c'est-à-dire les lignes une et b, tout comme vous l'avez fait. La matrice résultante a une seule colonne C et pas de lignes:

   | C
-------

Ce n'est pas une matrice vide (il reste une colonne). Cependant, la colonne C n'a pas de 1, donc nous nous terminons sans succès, comme l'indique l'algorithme.

Cela peut sembler étrange, mais c'est un cas très important si nous avons l'intention d'utiliser une matrice d'incidence pour le Problème de couverture exact, car les colonnes représentent des éléments de l'ensemble Xque nous souhaitons couvrir et les lignes représentent des sous-ensembles de X. Ainsi, une matrice avec quelques colonnes et aucune ligne représente le problème de couverture exact où la collection de sous-ensembles à choisir est vide (mais il y a encore des points à couvrir).

Si cette description pose des problèmes pour votremise en œuvre, il existe une solution de contournement simple: il suffit d'inclure l'ensemble vide dans chaque problème. L'ensemble vide (ne contenant aucun point de X) est représenté par une ligne de tous les zéros. Il n'est jamais sélectionné par votre algorithme dans le cadre d'une solution, ne se heurte jamais à aucune autre ligne sélectionnée, mais garantit toujours que la matrice est non vide (il y a au moins une ligne) jusqu'à ce que toutes les colonnes aient été supprimées, ce qui est vraiment tout ce que vous attention car vous devez vous assurer que chaque colonne est couverte par une ligne.

---