Finden Sie die minimale Anzahl von 1, damit die Matrix aus 1 verbundenen Region von 1 besteht

8

Sei eine Matrix. Wir sagen , zwei Einträge Nachbarn sind , wenn sie neben horizontal oder vertikal sind, und beide Einträge sind ‚s. Man will Mindestanzahl von finden ‚s hinzuzufügen, so dass jeder eine andere durch eine Folge von Nachbarn zu erreichen.M(0,1)1 1111

Beispiel:

100
000
001

Hier brauchen wir 3 's:1

100
100
111

Wie können wir effizient die minimale Anzahl von finden ‚s hinzuzufügen, und wo?1

algorithms graph-theory matrices Chao Xu
quelle
Es ist oft hilfreich, ein Problem als ein Problem eines anderen Typs zu betrachten. Zum Beispiel diesmal ein Matrixproblem als Graphproblem. Dies gibt Ihnen alle Werkzeuge der Graphentheorie, mit denen Sie arbeiten können. Auf den ersten Blick schien mir Ihr Problem ein Problem mit dem kürzesten Weg zu sein.
Juho

Antworten:

5

Wenn Sie Ihr Problem mit Diagrammen modellieren, ist Ihr Problem wie das Steiner Tree-Problem :

Siehe hier für eine möglichst einfache Definition.

Suchen Sie anhand eines gewichteten Diagramms, in dem eine Teilmenge von Scheitelpunkten als Terminals identifiziert wird, einen verbundenen Subgraphen mit minimalem Gewicht, der alle Terminals enthält.

Wie Sie sehen können, handelt es sich im Allgemeinen um einen NPC. In Ihrem Fall handelt es sich bei Ihrem Diagramm jedoch um ein Rasterdiagramm. Möglicherweise finden Sie eine gute Lösung dafür. In Ihrem aktuellen Beispiel (wenn sich die Terminals an der Grenze befinden) sehen Sie den Steiner-Baum in Rasterdiagrammpapier .

Auf jeden Fall gibt es ausgezeichnete Heuristiken für das Steiner Tree-Problem. Sie können einen ähnlichen Ansatz für Ihr Problem anwenden.

PS: Sie können davon ausgehen, dass Nachbarn 1s verbundene Knoten sind. Danach können Sie ihre Kanten zusammenziehen, um ein neues Diagramm zu erstellen. Ihr neu erstelltes Diagramm ist planar. Wenn Sie den Steiner-Baum dafür lösen könnten, könnten Sie Ihr Problem lösen, aber möglicherweise Für Ihr Problem gibt es eine gute Lösung, die unabhängig von Steiner Tree ist.


quelle
2
Falls sich jemand wundert, bleibt das Problem NP-vollständig, selbst wenn Kanten ein Einheitsgewicht haben.
Juho
@mrm, Ja, eigentlich Wikipedia-Link, sagt über ungewichtete Version (implizit) Siehe seine Verallgemeinerung . Ich dachte, dass ein Wiki-Link auf den ersten Blick nicht klar ist, also zitierte ich eine einfache Definition.
Beachten Sie auch, dass nicht alle Einsen an der Grenze der Matrix liegen müssen, um an der Grenze des resultierenden Gittergraphen zu sein
Joe
Sie scheinen das Problem von OP auf Stiener Tree zu reduzieren, was besagt, dass Stiener Tree mindestens so schwer ist wie das Problem von OP. Nicht umgekehrt: dh der erste Satz ist irreführend. Natürlich spricht die von Ihnen verlinkte Wiki-Seite auch über das Problem des geradlinigen Stiener-Baums, das ziemlich relevant zu sein scheint.
Aryabhata
@Aryabhata, Nein, ich habe keine Reduzierung vorgenommen, nur ein Format des OPs-Problems ist genau das gleiche wie das Stiener Tree-Problem. Es ist also mindestens so schwer wie das Stiener Tree-Problem, aber wie ich bereits erwähnt habe, funktioniert das OPs-Problem in Grids, und wenn Stiener Tree ist auf Gittern lösbar, er kann dies für sein Problem tun, aber der geradlinige Fall ist schwieriger als die Gitter. Tatsächlich sind Gitter ein Sonderfall für geradlinige Graphen. Daher habe ich ein Papier für Gittergraphen vorgeschlagen, mit dem Sonderfälle in Gittern gelöst werden können in , Insgesamt habe ich nie gesagt, dass sein Problem NPC oder so etwas ist, und wenn du denkst, dass ich das gesagt habe, sag mir bitte, ich soll es löschen. P