Trouver un nombre minimum de 1 pour que la matrice se compose d'une région connectée de 1

8

Soit une matrice . Nous disons que deux entrées sont voisines si elles sont adjacentes horizontalement ou verticalement, et les deux entrées sont à . On veut trouver un nombre minimum de à ajouter, donc chaque peut atteindre un autre à travers une séquence de voisins.M(0,1)111

Exemple:

100
000
001

Ici, nous avons besoin de 3 :1

100
100
111

Comment trouver efficacement le nombre minimum de à ajouter, et où?1

algorithms graph-theory matrices Chao Xu
la source
Il est souvent utile de présenter un problème comme un problème d'un autre type; par exemple cette fois un problème de matrice comme un problème de graphe. Cela vous donne tous les outils de la théorie des graphes avec lesquels travailler. À première vue, votre problème m'a semblé être le plus court.
Juho

Réponses:

5

Si vous modélisez votre problème avec des graphiques, votre problème est comme le problème de Steiner Tree :

Voir ici pour la définition la plus simple possible.

Étant donné un graphique pondéré dans lequel un sous-ensemble de sommets sont identifiés comme des terminaux, trouvez un sous-graphique connecté de poids minimum qui inclut tous les terminaux.

Comme vous pouvez le voir, c'est un PNJ en général, mais dans votre cas, votre graphique est un graphique en grille, peut-être que vous pouvez trouver une bonne solution pour cela, mais pour votre exemple actuel (lorsque les terminaux sont à la limite), vous pouvez voir l' arbre de Steiner dans du papier de graphiques en grille .

Quoi qu'il en soit, il existe d'excellentes heuristiques pour le problème de Steiner Tree, vous pouvez appliquer une approche similaire à votre problème.

PS: Vous pouvez supposer que les voisins 1 sont des nœuds connectés, après quoi vous pouvez contracter leurs bords pour créer un nouveau graphique, votre nouveau graphique créé est planaire et si vous pouviez résoudre l'arbre Steiner pour cela, vous pouvez résoudre votre problème, mais peut être il existe une bonne solution à votre problème, indépendante de Steiner Tree.


la source
2
Si quelqu'un se pose la question, le problème reste NP-complet même si les bords ont un poids unitaire.
Juho
@mrm, Oui, en fait un lien wikipedia, dit à propos de la version non pondérée (implicitement) Voir sa généralisation . Je pensais que le lien wiki n'était peut-être pas clair à première vue, alors j'ai cité une définition simple.
Notez également que tous les 1 ne doivent pas être sur la frontière de la matrice pour être sur la frontière du graphique en grille résultant
Joe
Vous semblez réduire le problème d'OP à Stiener Tree, qui dit que Stiener Tree est au moins aussi difficile que le problème d'OP. Pas l'inverse: la première phrase est trompeuse. Bien sûr, la page wiki que vous avez liée parle également du problème de l'arbre de Stiener rectiligne, qui semble être tout à fait pertinent.
Aryabhata
@Aryabhata, Non, je n'ai fait aucune réduction, juste un certain format de problème de PO est exactement le même que le problème de Stiener Tree, donc c'est au moins aussi difficile que Stiener Tree, mais comme je l'ai mentionné, le problème de PO fonctionne sur les grilles, et si Stiener Tree est résoluble sur les grilles, il peut le faire pour son problème, mais le cas rectiligne est plus difficile que les grilles, en fait, les grilles sont un cas spécial de graphiques rectilignes, j'ai donc suggéré un papier pour les graphiques de grille, qui peut résoudre un cas spécial dans les grilles en , dans l'ensemble, je n'ai jamais dit que son problème était un PNJ ou quelque chose comme ça, et si vous pensez avoir dit cela, dites-moi s'il vous plaît de le supprimer. P