Compte tenu d'une grande matrice clairsemée (disons 10k + par 1M +), je dois trouver un sous-ensemble, pas nécessairement continu, des rangées et des colonnes qui forment une matrice dense (tous les éléments non nuls). Je veux que cette sous-matrice soit aussi grande que possible (pas la plus grande somme, mais le plus grand nombre d'éléments) dans certaines contraintes de ratio d'aspect.
existe-t-il des solutions exactes ou apoxamates connues à ce problème?
Une analyse rapide sur Google semble donner beaucoup de résultats proches mais pas-exactement. Quels termes dois-je rechercher?
éditer: juste pour clarifier; La sous-matrice ne doit pas être continue . En fait, la ligne et la commande de colonne sont totalement arbitraires afin que la adjacence est complètement non pertinente.
Une pensée basée sur l'idée de Tchad Okere
4 Réponses :
éditer. Ce n'est pas la même chose que le problème ci-dessous .. mon mauvais ...
Mais sur la base du dernier commentaire ci-dessous, cela pourrait être équivalent aux éléments suivants:
Puis la région horizontale que vous recherchez est le rectangle qui convient entre ces deux paires de points?
Ce problème exact est discuté dans un joyau d'un livre appelé "Perles de programmation" de Jon Bentley, et, comme je me souviens bien, bien qu'il y ait une solution dans une dimension, il n'y a pas de réponse facile pour le 2-D ou supérieur Variantes dimensionnelles ...
Le problème 1 = D est, efficacement, trouve la plus grande somme d'un sous-ensemble contigu d'un ensemble de nombres:
Itérate à travers les éléments, en gardant une trace d'un total exécuté à partir d'un élément précédent spécifique et le sous-total maximum vu jusqu'à présent (et l'élinité de départ et de fin qui le génère) ... à chaque élément, si le sous-total maxrunning est Plus grand que le total maximum vu jusqu'à présent, le maximum vu jusqu'à présent et endelemnt sont réinitialisés ... Si le total de l'exécution maximum est inférieur à zéro, l'élément de démarrage est réinitialisé à l'élément actuel et le total exécuté est réinitialisé à zéro ...
Le problème 2-D provenait d'une tentative visant à générer un algorithme de traitement d'image visuel, qui tentait de trouver, dans un flux de valeurs de luminosité représentant des pixels dans une image de 2 couleurs, trouve la zone rectangulaire "plus brillante" de la image. CE, Consultez la sous-matrice 2-D contenue avec la somme la plus élevée de valeurs de luminosité, où la "luminosité" a été mesurée à la différence entre la valeur de la brillance du pixel et la luminosité moyenne globale de l'image entière (tant d'éléments avaient des valeurs négatives)
Edit: Pour rechercher la solution 1-D, je suis dragué ma copie de la 2e édition de ce livre et, dedans Jon Bentley, dit "La version 2-D reste non résolue car cette édition va à l'impression ... "Ce qui était en 1999.
Je ne suis pas suivi. Je ne pense pas que le problème puisse exister du tout en 1-d.
Théoriquement, cela peut, mais pas avec vos spécifications données.
La seule version 1-D que je puisse penser à des montants à "Sélectionner tous les non-Zeros forment une liste" mais ce n'est pas intéressant de première année CS.
Mot clé de la version 1-D qui le rend légèrement intéressant est "Trouver le plus grand Continu Ensemble de non-zéro dans une liste".
Cela répond à une question totalement différente. Dans la question de l'OP, il souhaite sélectionner un sous-ensemble (pas nécessairement continu) qui est tout non-zéro (pas la plus haute somme)
Ensuite, il s'agit de trivialo, il suffit de sélectionner toutes les valeurs positives ... J'ouille-moi de "... former une matrice dense ..." qu'il devait être un sous-ensemble contigu dans la matrice d'origine .. "Mais tu as raison IDID n'inclut pas la restriction que la région sélectionnée ne peut pas avoir de valeurs négatives ...
Positif / négatif n'est pas pertinent car je ne me soucie pas du tout quelles valeurs la sous-matrice a, mais qu'aucun élément n'est égal à zéro. Pour cette affaire, vous pouvez y penser comme une matrice booléenne.
est-ce un Netflix Problème ?
MATLAB ou certaines autres bibliothèques matricielles pourraient avoir des moyens de gérer cela.
Votre intention d'écrire votre propre?
Peut-être que l'approche 1D pour chaque ligne vous aiderait. L'algorithme pourrait ressembler à ceci:
À ce stade, je commence à devenir floue (désolé, pas de concepteur d'algorithme). J'essaierais de boucler sur chaque rangée, alignant les index du point de départ, à la recherche de la course maximale non nulle d'index de colonne que je pouvais.
Vous ne spécifiez pas si la matrice dense doit être carrée ou non. Je suppose que non.
Je ne sais pas à quel point cela est efficace ou quel serait son comportement Big-O. Mais c'est une méthode de force brute pour commencer.
"Le problème Netflix? Non, pourquoi demandez-vous?)" Je ne sais pas si vous supposez que je veux une sous-matrice continue ou non. Pour l'enregistrement, je m'en fiche si le résultat est une sous-matrice continue.
Pourquoi dois-je demander? Une simple curiosité. En ce qui concerne la continuité, je suppose que vous voulez dire que vous pouvez réorganiser des lignes pour les rendre continus si vous le souhaitez. Calculez l'index de départ et une longueur maximale pour chaque ligne, puis déterminez la plus grande sous-chaîne dense de ce résultat.
Ce premier bit était censé être ironique (en fait, il est lié à la forme générale du "problème Netflix"). Ce que je ne reçois pas, c'est de la "longueur" que vous parlez de. Je suis libre de réorganiser des lignes et des colonnes afin que le plus proche que je doive une longueur est un nombre d'éléments non zéro.
Je suppose que vous voulez quelque chose comme ça. Vous avez une matrice comme vous voulez des colonnes 1,2,5,7 et des rangées 1 et 2, non? Cette sous-chaîne serait 4x2 avec 8 éléments. Ou vous pouvez aller avec des colonnes 1,5,7 avec des rangées 1,2,3 qui constitueraient une matrice 3x3. Si vous souhaitez une méthode «approximative», vous pouvez commencer par un seul élément non nulle, puis continuer à trouver un autre élément non nul et l'ajoutez à votre liste de lignes et de colonnes. À un moment donné, vous rencontrerez un élément non nul qui, si ses lignes et vos colonnes ont été ajoutées à votre collection, votre collection ne serait plus entièrement nulle. Donc, pour la matrice ci-dessus, si vous avez ajouté 1,1 et 2,2, vous auriez des rangées 1,2 et des colonnes 1,2 dans votre collection. Si vous avez essayé d'ajouter 3,7, cela causerait un problème car 1,3 est zéro. Donc, vous ne pouviez pas l'ajouter. Vous pouvez ajouter 2,5 et 2,7 cependant. Création de la sous-chaîne 4x2. Vous iriez essentiellement itérer jusqu'à ce que vous ne trouviez plus de nouvelles lignes et colonnes à ajouter. Cela vous ferait trop un minimum local. Vous pouvez stocker le résultat et recommencer avec un autre point de départ (peut-être un qui ne correspondait pas à votre solution actuelle). Ensuite, arrêtez-vous quand vous ne pouvez plus trouver après un certain temps. Cela, évidemment, prendrait beaucoup de temps, mais je ne sais pas si vous pourrez le faire plus rapidement.
Cela fonctionnerait mais je pense que ce sera O (n!) ou pire. OTOH je me suis donné une idée ...
BCS: Vous recherchez essentiellement un élément du produit direct de l'ensemble de lignes de lignes et de la puissance des colonnes. Les chercheurs de puissance vont généralement être (IIRC) NP-dur. Vous devez trouver une solution approximative. L'idée avec l'algorithme que j'ai posté ci-dessus est que vous continuez à le faire, espérons-le, trouver des solutions meilleures et meilleures avec chaque course. Combien de temps cela prendra-t-il réellement dépend de la matrice. Une matrice entièrement dense ne prendrait que O (max (n, m)) (car il n'y a pas de conflit) où N et M sont le nombre de lignes et de colonnes.
Je soupçonnais que c'était Np-dur
Je sais que tu ne travailles plus sur ce sujet, mais je pensais que quelqu'un pourrait avoir la même question que moi à l'avenir.
Donc, après avoir réalisé qu'il s'agit d'un problème du NP-dur (par réduction de max-clique), j'ai décidé de trouver une heuristique qui a bien fonctionné pour moi jusqu'à présent:
Compte tenu d'un N x M matrice binaire / booléen, trouve une grande subatrix dense:
Initialement, chacun des vecteurs Partie II : SubmitRics de score et de candidat
J'ai également eu quelques considérations concernant le nombre min de lignes qui devaient être préservées à partir de la matrice complète initiale et je supplierais toute soumission candidate qui n'a pas répondu à ce critère avant de sélectionner une sous-chaîne avec max
Selon les limites du rapport de format, cela peut valoir la recherche d'une recherche à partir de là en ajoutant des lignes de trading pour les colonnes (et l'inverse de l'inverse).
La définition d'une limite inférieure sur la sous-chaîne facilitera le problème.
@Sev: Pourriez-vous élaborer? Je ne suis pas sûr du type de limite inférieure que vous parlez.
Si vous choisissez une sous-chaîne minimale spécifique P x Q à trouver, de sorte que tout soit inférieur à celui qui sera jeté, peut simplifier le problème, si votre minimum est suffisamment grand.
Sev: Vous n'avez aucune idée si une sous-chaîne P x Q existe avant de commencer.
BCS: C'est une bonne idée. Vous commencez avec une matrice "grande, mince" et soyez plus courte et plus large jusqu'à ce que la zone cesse d'augmenter. Une suggestion: après la première itération, passez des colonnes plutôt que des rangées.
@Chad: Encipation sur elle est suspect que la ligne Perf de la colonne VS dépendra dans une large mesure sur le type d'indexation que je peux gérer. Il pourrait s'avérer que la possibilité de se développer dans les deux sens et de choisir l'une ou l'autre de manière dynamique (basée sur la situation) pourrait bien fonctionner.
@BCS Avez-vous déjà trouvé une solution optimale au problème (peut-être quelque chose impliquant une programmation dynamique)?
@awesomo: Nope, et je ne me souviens même pas de ce que je faisais avec ça.
@BCS En fait, sur une enquête plus approfondie, elle est durable de la réduction de la réduction de la max-clique (la subatrix dense équivaut à une clique si vous pensez de votre matrice comme une matrice de adjacence), de sorte que les heuristiques devront suffire.
@awesomol Je vois la réduction à max-clique pour le cas où la matrice d'entrée et la sous-matrice sont limitées au carré. Dans ce cas, les deux ne sont pas si restreints. OTOH, je soupçonne que vous êtes correct, même si aucune réduction triviale n'existe.