Trouver une commande optimale

9

J'ai rencontré ce problème et j'ai du mal à trouver un moyen de l'aborder. Toutes les pensées seraient grandement appréciées!

Supposons que l'on nous donne une matrice , par exemple,{1,0,1}n × k

[1010110001011011101110001]

Sans essayer chaque permutation, trouvez un ordre des colonnes qui maximise le nombre de lignes pour lesquelles le premier élément non nul est .ci1

Pour l'exemple ci-dessus, un tel ordre (ce n'est pas unique!) Est , c'est-à-dire,(c3,c4,c1,c2,c5)

[1010100101100110111100101]

Ici, pour rangées sur le premier élément non nul est .451

haijo
la source
Quelles approches algorithmiques avez-vous essayées? Où avez-vous rencontré ce problème? Pouvez-vous créditer la source d'origine? Pouvez-vous partager quelque chose sur le contexte ou la motivation? Cette page pourrait vous être utile pour améliorer votre question.
DW
1
Je veux suggérer une étape de prétraitement: Soit une colonne semi-positive (resp. Ligne) une colonne (resp. Ligne) avec seulement 0 et 1. La suggestion est de supprimer toutes les colonnes semi-positives, ainsi que les lignes avec un 1 dans une colonne semi-positive. Dans votre exemple, cela supprimerait les lignes 1, 3 et 4. Il vous reste maintenant des lignes et des colonnes qui contiennent toutes -1s. Cela pourrait ne pas aider, mais il pourrait être plus simple de raisonner.
Pål GD
Peut-on supposer que le nombre de lignes est beaucoup plus petit que le nombre de colonnes? Cela pourrait faciliter le problème.
Angela Pretorius
1
@ Pål, un prétraitement similaire est possible avec des lignes et des colonnes qui ne contiennent pas de 1. Cependant, je ne pense pas que cela facilite la réflexion: juste plus petit.
Peter Taylor
1
FWIW c'est un cross-post . haijo, si vous ne recevez pas de réponse sur une pile et pensez qu'une autre pourrait être meilleure, vous pouvez la signaler et demander une migration. La publication croisée n'est pas une bonne étiquette car les répondeurs ne sont pas au courant des réponses que vous avez reçues sur l'autre site et peuvent perdre leur temps à les répéter.
Peter Taylor

Réponses:

4

Ce problème, que j'appellerai CO pour la commande de colonnes, est NP-difficile . Voici une réduction du problème NP-hard Vertex Cover (VC):

Formes de problème de décision de VC et CO

Soit l'instance VC d'entrée (V,E,k) . Il représente la question: "Étant donné le graphique (V,E) , est-il possible de choisir un ensemble d'au plus k sommets dans V telle sorte que chaque arête dans E soit incidente sur au moins un sommet choisi?" Nous allons construire une instance (A,k) de CO qui représente la question: "Étant donné la matrice A avec des éléments dans {1,0,1}, Est - il possible de permuter les colonnes de A telle que 1 apparaît avant -1 sur au moins k lignes « Ces deux problèmes sont énoncés dans? Problème de décision sous forme, par laquelle la réponse à chacune est OUI ou NON: formellement , c'est cette forme de problème qui est NP-complet (ou pas) .Il n'est pas trop difficile de voir que la forme de problème d'optimisation la plus naturelle énoncée dans la question du PO est à peu près équivalente en termes de complexité: recherche binaire sur le seuil Le paramètre peut être utilisé pour résoudre le problème d'optimisation à l'aide d'un résolveur de problème de décision, tandis qu'une seule invocation d'un résolveur de problème d'optimisation, suivie d'une seule comparaison, suffit pour résoudre le problème de décision.

Construire une instance de CO à partir d'une instance de VC

Soit n=|V|et m=|E|. Nous allons construire une matrice A avec (n+1)m+n lignes et n+1 colonnes. Les m rangées supérieures (n+1)m seront formées de m blocs de n+1 rangées chacun, chaque bloc représentant un bord à recouvrir . Le fond n les lignes contiennent des "drapeaux" de sommet, ce qui entraînera un coût fixe pour une colonne (correspondant à un sommet) si elle est incluse dans le côté gauche de la solution de CO (correspondant à un sommet inclus dans la couverture de sommet du Solution VC).

Pour chaque sommet vi , créez une colonne dans laquelle:

  • entre la partie supérieure (n+1)m rangées, le j bloc -ième de n+1 lignes contiennent tous un 1 lorsque arête ej est incidente sur vi , et 0 sinon, et
  • les n lignes du bas sont toutes à 0 sauf pour le i -ième, qui est -1.

Créez une autre colonne "clôture" qui se compose de (n+1)m copies de -1, suivies de n copies de +1.

Enfin, fixons le seuil k pour l'instance CO construite: (n+1)m+nk . En d'autres termes, nous autorisons au plus k lignes dans lesquelles un -1 apparaît avant un +1. Appelons ce nombre de lignes violées le «coût» d'une solution de CO.

Preuve

La correspondance entre une solution à l'instance CO et un ensemble de sommets dans l'instance VC d'origine est la suivante: chaque colonne à gauche de la clôture correspond à un sommet qui se trouve dans l'ensemble et chaque colonne à droite de la clôture correspond à un sommet qui ne l'est pas.

Intuitivement, les -1 en haut de la colonne "clôture" forcent la sélection d'un sous-ensemble de colonnes à placer à sa gauche qui contiennent ensemble + 1 dans toutes ces positions - correspondant à un sous-ensemble de sommets qui sont incidents sur chaque bord. Chacune de ces colonnes qui apparaît à gauche de la "clôture" a un -1 sur une ligne distincte quelque part dans les n lignes du bas , entraînant un coût de 1; les +1 dans le bas de la "clôture" garantissent que toutes les colonnes placées à sa droite n'encourent pas de tels frais.

Clairement, une solution VC utilisant au plus k sommets donne une solution à l'instance de CO construite avec un coût au plus k : ordonnez simplement les colonnes correspondant aux sommets dans la couverture de sommets arbitrairement, suivies de la colonne de clôture, puis de toutes les colonnes restantes dans n'importe quel ordre .

Reste à montrer qu'une solution à l'instance CO avec un coût au plus k correspond à une couverture de vertex avec au plus k sommets.

Supposons au contraire qu'il existe une solution à l'instance CO avec un coût au plus k qui laisse une ligne dans les rangées supérieures (n+1)m avec un -1 avant un +1. Cette ligne appartient à un bloc de (n+1) lignes correspondant à un bord particulier uv . Chaque ligne de ce bloc dans l'instance d'origine A est identique par construction; permuter les colonnes peut modifier ces lignes, mais n'affecte pas le fait qu'elles sont identiques. Ainsi, chacune de ces n+1 lignes identiques a un -1 avant un +1 dans la solution, ce qui implique un coût d'au moinsn+1 . Maiskn<n+1 : contradiction.

Étant donné que chacun des m blocs de rangées dans les rangées supérieures (n+1)m a un +1 avant un -1, chacun des bords correspondants est couvert par un sommet correspondant à une colonne à gauche de la clôture: c'est-à-dire , ce sous-ensemble de sommets constitue une couverture de sommets. Puisqu'aucune des m (n+1)m rangées n'a un -1 avant un +1, le seul endroit où le coût peut s'accumuler dans la solution est dans les n rangées, des colonnes placées à gauche de la clôture. Chacune de ces colonnes a coûté exactement 1, donc étant donné que le coût est d'au plus k , il doit y avoir au plus kces colonnes, et donc au plus k sommets dans la couverture.

Enfin, il est clair que l'instance CO peut être construite en temps polynomial à partir de l'instance VC, ce qui signifie que si un algorithme polynomial existait pour résoudre le CO, toute instance VC pourrait également être résolue en temps polynomial en construisant d'abord une instance CO comme décrit ci-dessus, puis le résoudre. Puisque VC est NP-dur, le CO l'est aussi.

j_random_hacker
la source
Chaque fois qu'il y a une réponse aussi intéressante, je me demande si les "Hot Network Questions" devraient être remplacées ou jointes par quelque chose comme "Valuable Network Answers".
John L.
Pourriez-vous nous éclairer sur la façon dont vous trouvez la réponse? Cela devrait être encore plus instructif que la réponse elle-même.
John L.
1
@ Apass.Jack: Merci! :) Je n'ai pas de stratégie spéciale et je peux passer longtemps à errer dans la mauvaise direction. Par exemple, j'ai passé beaucoup de temps à penser que je pouvais réduire le cycle hamiltonien (qui est similaire dans la mesure où il s'agit de commander des éléments) avant de réaliser que ma construction permettrait des configurations correspondant à des sous-circuits, et ne fonctionnerait donc pas. En règle générale, j'essaie toujours des réductions de Vertex Cover ou Partition, puis peut-être Clique. "Valuable Network Answers" sonne comme une excellente idée :)
j_random_hacker
1
rkr
1
n+1
2

S

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Ensuite, vous devez faire une exploration complète de la combinatoire en utilisant de manière itérative la fonction pick:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

Après chaque sélection, vous pouvez faire une simplification pour éventuellement réduire le nombre de possibilités à explorer. Je suggère d'explorer goulûment en commençant par la colonne ayant le moins -1, ainsi vous pouvez atteindre une borne inférieure faisant un critère d'arrêt.

Sur l'exemple donné, la première simplification donne (comme Pål GD l'a expliqué en commentaire)

  • S[0]=c3
  • S[1]=c4
  • S[2]=c2
    [1111]

[110000110000001100001100000011000011]

Néanmoins, la simplification épargne encore environ la moitié des étapes d'exploration. Et ce type de matrice peut être divisé en plusieurs sous-matrices indépendantes.

Optidad
la source
1
@ Apass.Jack j'ai édité pour être plus précis. Oui, je voulais dire la position de la colonne dans la séquence de sortie.
Optidad
Le vote de l'étape de simplification pourrait être suffisant pour des raisons pratiques (comme des exercices de programmation en ligne?).
John L.
Merci, en fait j'étais intéressé à estimer le coût en temps amorti mais je ne sais pas vraiment comment faire. Est-ce possible ? Ou est-ce trop dépendant du problème?
Optidad
2
ijijjij
1
ijijijijikk