Encontre um número mínimo de 1 para que a matriz seja composta por 1 região conectada de 1

8

Seja uma matriz . Dizemos que duas entradas são vizinhas se forem adjacentes na horizontal ou na vertical, e ambas as entradas são 1 's. Quer-se encontrar o número mínimo de 1 para adicionar, para que cada 1 possa alcançar outro através de uma sequência de vizinhos.M(0,1)111

Exemplo:

100
000
001

Aqui temos 3 1 's:

100
100
111

Como podemos encontrar com eficiência o número mínimo de 1 para adicionar e onde?

algorithms graph-theory matrices Chao Xu
fonte
Muitas vezes, é útil lançar um problema como um problema de outro tipo; por exemplo, desta vez, um problema de matriz como um problema de gráfico. Isso fornece todas as ferramentas da teoria dos grafos para trabalhar. À primeira vista, seu problema parecia um caminho mais curto para mim.
Juho

Respostas:

5

Se você modelar seu problema com gráficos, seu problema é como o problema da Steiner Tree :

Veja aqui a definição mais simples possível.

Dado um gráfico ponderado no qual um subconjunto de vértices é identificado como terminal, encontre um subgrafo conectado de peso mínimo que inclua todos os terminais.

Como você pode ver, é o NPC em geral, mas, no seu caso, seu gráfico é um gráfico de grade, pode ser que você possa encontrar uma boa solução para isso, mas para o seu exemplo atual (quando os terminais estão no limite), você pode ver a árvore Steiner no papel de gráficos de grade .

De qualquer forma, existem excelentes heurísticas para o problema do Steiner Tree, você pode aplicar uma abordagem semelhante ao seu problema.

PS: Você pode assumir que os vizinhos 1s são nós conectados; depois disso, você pode contratar as arestas para criar um novo gráfico, o novo gráfico criado é plano e, se você puder resolver a Árvore Steiner, poderá resolver seu problema, mas pode ser: existe uma boa solução para o seu problema, independente da Steiner Tree.


fonte
2
Caso alguém esteja se perguntando, o problema permanece NP-completo, mesmo que as bordas tenham peso unitário.
Juho
@ RM, Sim, na verdade, link da Wikipedia, diz sobre a versão não ponderada (implicitamente) Veja a sua generalização . Eu pensei que pode ser link wiki não está claro à primeira vista, então eu citei uma definição simples.
Também nota que nem todos os 1s tem que ser no limite da matriz, a fim de estar no limite da grade gráfico resultante
Joe
Você parece estar reduzindo o problema do OP para o Stiener Tree, que diz que o Stiener Tree é pelo menos tão difícil quanto o problema do OP. Não o contrário: ou seja, a primeira frase é enganosa. Obviamente, a página wiki que você vinculou também fala sobre o problema da Árvore Rectilinear Stiener, que parece ser bastante relevante.
Aryabhata
@Aryabhata, Não, eu não fiz nenhuma redução, apenas algum formato do problema dos OPs é exatamente o mesmo que o problema da Árvore Stiener, por isso é pelo menos tão difícil quanto a Árvore Stiener, mas como eu mencionei isso, o problema dos OPs funciona em grades e, se Stiener Tree é solucionável em grades, ele pode fazer isso por seu problema, mas o caso retilíneo é mais difícil do que as grades; na verdade, as grades são casos especiais de gráficos retilíneos, então sugeri um documento para gráficos de grade, que pode resolver casos especiais em grades in , No geral, eu nunca disse que o problema dele é NPC ou algo assim, e se você acha que eu disse isso, por favor me diga para excluí-lo. P