Encuentre el número mínimo de 1 para que la matriz consista en 1 región conectada de 1

8

Sea una matriz . Decimos que dos entradas son vecinas si son adyacentes horizontal o verticalmente, y ambas entradas son 's. Uno quiere encontrar un número mínimo de para agregar, por lo que cada puede alcanzar a otro a través de una secuencia de vecinos.M(0,1)111

Ejemplo:

100
000
001

Aquí necesitamos 3 's:1

100
100
111

¿Cómo podemos encontrar eficientemente la cantidad mínima de 's para agregar y dónde?1

algorithms graph-theory matrices Chao Xu
fuente
A menudo es útil considerar un problema como un problema de otro tipo; Por ejemplo, esta vez un problema de matriz como un problema gráfico. Esto le brinda todas las herramientas de la teoría de grafos para trabajar. A primera vista, su problema me pareció un problema de camino más corto para mí.
Juho

Respuestas:

5

Si modela su problema con gráficos, su problema es como el problema de Steiner Tree :

Vea aquí la definición más simple posible.

Dado un gráfico ponderado en el que un subconjunto de vértices se identifican como terminales, encuentre un subgráfico conectado de peso mínimo que incluya todos los terminales.

Como puede ver, es NPC en general, pero en su caso su gráfico es un gráfico de cuadrícula, puede encontrar una buena solución para él, pero para su ejemplo actual (cuando los terminales están en el límite) puede ver el árbol Steiner en el papel de gráficos de cuadrícula .

De todos modos, existen excelentes heurísticas para el problema de Steiner Tree, puede aplicar un enfoque similar a su problema.

PD: puede suponer que los vecinos 1 son nodos conectados, después de eso puede contraer sus bordes para hacer un nuevo gráfico, su nuevo gráfico creado es plano, y si pudiera resolver el Árbol Steiner, puede resolver su problema, pero puede ser Hay una buena solución para su problema que es independiente de Steiner Tree.


fuente
2
En caso de que alguien se pregunte, el problema sigue siendo NP completo incluso si los bordes tienen un peso unitario.
Juho
@mrm, sí, en realidad el enlace de Wikipedia, dice acerca de la versión no ponderada (implícitamente). Vea su generalización . Pensé que podría ser un enlace wiki no está claro a primera vista, así que cité una definición simple.
También tenga en cuenta que no todos los 1 deben estar en el límite de la matriz para estar en el límite del gráfico de cuadrícula resultante
Joe
Parece que estás reduciendo el problema de OP a Stiener Tree, que dice que Stiener Tree es al menos tan difícil como el problema de OP. No al revés: es decir, la primera oración es engañosa. Por supuesto, la página wiki que vinculaste también habla sobre el problema Rectilinear Stiener Tree, que parece ser bastante relevante.
Aryabhata
@Aryabhata, no, no hice ninguna reducción, solo algunos formatos del problema de OP son exactamente iguales al problema del árbol Stiener, por lo que es al menos tan difícil como el árbol Stiener, pero como mencioné, el problema OP funciona en las cuadrículas, y si Stiener Tree es solucionable en cuadrículas, puede hacer esto por su problema, pero el caso rectilíneo es más difícil que las cuadrículas, de hecho, las cuadrículas son casos especiales de gráficos rectilíneos, por lo que sugerí un papel para gráficos de cuadrícula, que puede resolver casos especiales en cuadrículas en , en general, nunca dije que su problema es NPC o algo así, y si crees que dije esto, por favor dígame que lo elimine. P