Trouvez la clôture la plus courte qui entoure une zone sur une grille 2D

Question

J'ai un 50 x 50 grille 2D. Les cellules de la grille peut avoir l'un des trois états suivants:

1: "inside"
2: "empty"
3: "wall"

Ma configuration initiale est une grille avec des cellules (peut-être 10% d'entre eux, la plupart contigus) marqués comme "à l'intérieur". Au hasard il y a quelques "mur" des cellules. Les autres cellules sont "vides".

Je suis en train d'essayer de trouver le plus court de la clôture , je peux construire autour de "l'intérieur" des cellules, de sorte que tous les "à l'intérieur" des cellules sont fermées (clôtures sont construites en changeant de "vider" les cellules de la paroi des cellules). Si nous sommes de notation des solutions, la meilleure solution sera de minimiser le nombre de "vider" les cellules qui doivent être modifiés pour le "mur" des cellules.

De manière plus rigoureuse, dans la configuration finale, il y a la contrainte que pour chaque "l'intérieur" de la cellule il n'y a pas de chemin vers le bord de la grille qui ne passe pas par un "mur" de la cellule. Dans mon cas, les mouvements en diagonale est autorisé.

Je suppose que je peux faire quelque chose d'intelligent impliquant la distance transformer, ou de l'informatique topologiques du squelette de la grille, mais il n'est pas immédiatement évident pour moi. Si c'est un problème d'optimisation classique, je ne sais pas ce que les termes de google.

Est-il un O(n^2) algorithme pour trouver le plus court de la clôture?

EDIT: Il n'est pas aussi facile que juste de trouver l'enveloppe convexe de "l'intérieur" des cellules, parce pré-existantes "mur" cellules sont gratuits. Imaginez un "C"-en forme de morceau de pré-mur existant, avec tous les "à l'intérieur" des cellules à l'intérieur de la C. la Plupart du temps, remplissant le C avec le "mur" des cellules sera moins cher que le dessin d'une enveloppe convexe autour de tous les "à l'intérieur" des cellules. C'est ce qui rend ce problème difficile.

Answer 1

Beau problème!

Comme @qwertyman a remarqué, le problème est de trouver un minimum de vertice coupure entre "intérieur" des cellules et des limites de la grille. S'il est imaginable que ce problème particulier sur une grille pourrait avoir une solution plus facile, je ne pense pas que tout les autres solutions de résoudre le problème dans tous les cas.

Les cellules sur place des grilles peut être considérée comme ayant jusqu'à quatre ou à huit voisins (@tobias_k et @hidefromkgb). Si l'on fait abstraction de l'existant (gratuit) cellules de la paroi, voici ce que typique des clôtures sur les 4 - et 8-grilles:

Pas que dans les deux cas, il y a beaucoup plus minime des clôtures, mais ces rectangulaires et octogonales les cases sont à la fois minimal et facile à trouver. En outre, ils sont minimes clôtures avec le maximum d'espace intérieur.

Il y a deux complications: sans pré-existantes, les cellules de la paroi, et la possibilité que de multiples petites clôture composants sont moins cher que le gros de la boîte englobante.

Les deux complications sont bien résolus en un minimum de vertice couper problème; pré-existantes, les cellules de la paroi peut juste être supprimé à partir du graphique (et à l'intérieur des cellules peut être fusionné avec d'autres, connecté intérieur des cellules, laissant seulement une cellule interne pour chaque composante connexe de cellules intérieures). Malheureusement, un minimum de coupes sont généralement considérés comme le retrait des bords plutôt que des sommets!

Je doute qu'aucun algorithme sera plus facile que la mise en œuvre d'un chiffon propre vertice coupe de l'algorithme. Voici ce à quoi nous sommes confrontés:

Dans cet exemple, quatre petites clôtures sont moins cher que grand, mais qui dépend des proportions exactes. Nous pourrions commencer par une grande clôture et essayer de l'améliorer par la division, à l'instar de @LazyMammal n', ou avec de l'escrime chaque composant séparément, mais dans les deux cas, ces situations ne sont pas triviales.

Celui-ci est trop problématique:

Doit-on utiliser le grand gratuit clôture segment? Doit-on clôture de chaque petit point séparément? Nous utilisons trois moyen de clôtures? Peu importe si nous sommes de plus en grand et se divisent, comme @LazyMammal n', ou de commencer avec chacun des boîtes englobantes et se joindre à eux, ces situations semblent présenter les mêmes problèmes que le général minimum de coupes de problèmes.

Si vous êtes d'accord avec les approximations de solutions optimales, ou peut-être vous limiter à des cas sur 50 par 50 grilles et peut rapidement éliminer ces complications, peut-être il ya quelque chose de facile et rapide? Je ne sais pas.

Pour un connectés ensemble G des cellules intérieures, de trouver une moins chère clôture, fonctionnent comme ceci:

• Trouver un plus court "flux" chemin d'accès de FL de cellules vides de ce groupe à la frontière.

• Trouver un moins cher "clôture" chemin de FE dans l'ensemble du groupe à l'aide de toutes les cellules ne sont pas dans le G ou FL. Essayez chaque cellule de la FL en tant que point de départ, ou n'importe quelle cellule qui est à la fois en floride et en G du grillage. Le coût de cellules vides est 1, le coût des cellules de la paroi est de 0, et le coût de l'intérieur les cellules ne sont pas dans G est de 0. Vous aurez à couper la grille le long de FL pour s'assurer FE tourne autour de G.

(Mais je ne sais pas comment combler les lacunes de l'un des groupes afin de connecter l'ensemble de ses cellules en présence de cellules de la paroi.)

Alors peut-être que la vraie question est de savoir lequel des cellules intérieures de clôture ensemble? Connecté cellules intérieures doivent rester en contact, d'accord. En outre, si minime clôtures toucher, de rejoindre leurs groupes. Autres que que, approximatif, juste en essayant différentes combinaisons?

Je ne sais pas; je crois que le problème sur de grandes grilles présente les mêmes complications et de la complexité que le général minimale de la coupe des problèmes - donc, si vous avez vraiment besoin d'optimalité, résoudre les ceux qui.

Pertinentes: https://cstheory.stackexchange.com/questions/2877/ (merci qwertyman), https://en.wikipedia.org/wiki/Vertex_separator avec une notion différente de la "minimale" des séparateurs.

Answer 2

Ce que vous voulez probablement, c'est un 2-dimensions de l'enveloppe convexe.

Je recommanderais le soi-disant cadeau de l'algorithme. Son temps de la complexité est O(n2) dans le pire des cas. Son résumé est comme suit.

Sans perte de généralité, supposons qu'il n'existe pas de 3 points dans le nuage, qui sont colinéaires.

1. Nous commençons avec la partie gauche d'un point, comme chaque coque sur un corps fini de nuage de points doit inclure au moins un point qui est le plus à gauche (et, en considérant les restrictions ci-dessus, pas plus de deux d'entre eux sont possibles, et ils appartiennent tous deux à la coque).
2. Puis nous commençons par la force brute tel point que tous les autres sont sur le même des deux demi-plans, dans lequel la première de l'avion est divisé par une ligne tracée à partir du point initial à celui recherché.
3. Maintenant, nous faisons l'un trouvé un nouveau initiale, puis répétez [2-3] jusqu'à ce que la coque est fermée.

[N.-B.] de l'ours à l'esprit que la recherche d'un point qui est un prédécesseur de l'actuel premier vous mène nulle part (comme ceci: • ⇌ •), il devrait donc être ignorées, à moins qu'il n'y a pas plus de points à l'exception de ces deux.

Answer 3

Si vous entendez par clôture la plus courte, celle qui prend un nombre minimal de cellules "murales", la clôture avec un rectangle de séparation minimal fonctionnera.

Answer 4

Pour moi, c'est toujours une enveloppe convexe de la variante. vous devez inclure dans votre enveloppe convexe toutes les cellules qui sont voisins à l'intérieur de la cellule et qui ne sont pas à l'intérieur de la cellule + contiennent des cellules qui sont à l' [début] et [fin] d'un mur (contiguë au mur). Alors important est de s'exclure voisin cellules si ces cellules sont à l'intérieur d'un mur. Pour vérifier si la cellule est à l'intérieur d'un mur en forme de C par exemple, (I) vous pouvez calculer ax+b de la ligne de p1--p2, puis à l'aide d'une sorte de point de partitionnement check des aiguilles d'une montre/dans le sens antihoraire, puis plus loin de la paroi des points avec votre prochain point de l'exclure de la recherche. Dans l'exemple ci-dessous les points voisins je vais être exclus. Ainsi, l'algorithme trouverez p1->p2 connexion p1-p2 en tant que droit de l'avant.

...[.p1]
. I 
. I 
...[.p2]

Dans l'exemple ci-dessous, T points sont des points voisins

               TTT
...[.p1]       TIT
. I            TTT
. I 
...[.p2]

après l'enveloppe convexe algo, vous obtiendrez:

               [T3]
...[.p1]        I[T2]
. I            [T1] 
. I 
...[.p2]

que signifie un chemin p2[T1][T2][T3]p1 et entre les lignes entre les points vous donne minimale de les emballer. Comme vous pouvez le voir chaque mur de magasin ainsi une valeur si j'prochain point est à l'INTÉRIEUR d'un mur de forme (comme C), ces murs doivent être inclus dans l'enveloppe convexe, mais ceux qui n'ont pas interne voisins peut être utilisé seulement si la distance au prochain point est plus petit à l'aide de coût zéro mur existant.. eh Bien c'est un peu compliqué pour une explication rapide mais je suppose que vous pouvez obtenir quelque chose à partir de ce..

EDIT: Sur que le calcul de la convexes vous devrez exécuter aussi min débit à régler des cas comme:

...........[.]
.
.
. 
.
.         
.
.         I  I
.
.
.
.
.
. 
...........[.]

où l'on de I est à l'intérieur, mais min clôture autour de moi sans que p1 et p2 sont impliqués. Dans algo p1 et p2 seront sélectionnés, puis pour tous les murs qui ont des I vous avez à calculer dist(p1,externalI)+dist(p2,externalI) avec la dist(internalI,eternalI)et de choisir la plus petite..externalI est celui connecté à p1 et p2 (peut-être un ou deux points extérieurs..)

Answer 5

Ce problème peut être résolu par un graphe de simplification problème:

1. créer un graphique de la grille (pas de diagonales)
2. remove (supprimer) à l'Intérieur de nœuds
3. effondrement (fusion) de la Paroi nœuds
4. décrire un chemin autour de l'arête du graphe
5. itérer le long du chemin
   • vérifier si le chemin d'accès nœuds partagent un graphique vide voisin (à proximité = chemin des nœuds[n .. n+k] )
   • vérifier si le nouveau chemin d'accès à distance <= chemin d'accès existant à distance (nombre d'arêtes)
   • vérifier si l'Intérieur de nœud seraient bloqués par raccourci (ne pas autoriser)
   • ajuster le chemin d'accès si les conditions sont remplies
   • supprimer (delete) de noeuds d'un graphe qui ne sont plus nécessaires
6. arrêter lorsque le chemin ne peut pas être réduit plus

Pire des cas, vous devez parcourir tout le sommet de nœuds dans le graphe un peu de temps pour chaque bord. De sorte qu'il ressemble O(V * E) ou en d'autres termes O(N^2).