Couper un territoire en deux le plus simplement possible

La question :

Bonjour

J'ai un problème et j'aimerais savoir si vous connaissez des
algorithmes tout prêts pour ça ou si vous avez de bonnes
idées/pistes .

Le problème : pour un territoire de forme quelconque, constitué de
cases, j'aimerais trouver les manières les plus simples de couper le
territoire en deux (par "plus simple" j'entends en retirant le moins de
cases possibles).

C'est assez court comme description, mais je ne vois pas quoi ajouter
pour que ce soit plus clair. N'hésitez pas à demander des
précisions .

Il y a bien une technique de brutasse : j'essaie d'enlever les cases
une par une, je regarde si ça permet des coupures. Puis j'essaie avec
toutes les combinaisons de 2 cases, puis de 3, ... Mais ça va
devenir assez rapidement très long à calculer.

Une autre idée est de repérer les "points faibles", ceux où le
territoire est "étroit", mais c'est un vision analogique du monde,
difficile à implanter. Et si deux grosses parties sont rattachées par
deux petites branches ça ne fonctionne pas.

Voilà, toutes les idées sont les bienvenues

Merci

Yliur

Poser votre question sur le forum Programmation

Les 10 réponses :

Yliur a écrit :


Une autre idée est de repérer les "points faibles", ceux où le
territoire est "étroit", mais c'est un vision analogique du monde,
difficile à implanter. Et si deux grosses parties sont rattachées par
deux petites branches ça ne fonctionne pas.


Il suffit de représenter le territoire d'une façon utile. Par example,
par un graphe où chaque noeud représente une case, et où chaque arc
représente la connexion entre deux cases.

Il est alors possible d'appliquer les algorithms de la théorie des
graphes, pour détecter les sous-graphes connexes, les cycles, etc, et de
comptage de degré des noeuds, pour trouver les noeuds intéressants à
couper.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Le Sat, 15 Oct 2011 02:09:35 +0200
"Pascal J. Bourguignon" a écrit :


Yliur a écrit :


Une autre idée est de repérer les "points faibles", ceux où le
territoire est "étroit", mais c'est un vision analogique du monde,
difficile à implanter. Et si deux grosses parties sont rattachées
par deux petites branches ça ne fonctionne pas.


Il suffit de représenter le territoire d'une façon utile. Par
example, par un graphe où chaque noeud représente une case, et où
chaque arc représente la connexion entre deux cases.

Il est alors possible d'appliquer les algorithms de la théorie des
graphes, pour détecter les sous-graphes connexes, les cycles, etc, et
de comptage de degré des noeuds, pour trouver les noeuds intéressants
à couper.


Hum... je ne vois pas. Je peux faire ce dont je parlais dans un
paragraphe précédent, en retirant des cases/noeuds et en regardant ce
que ça donne, mais c'est un peu par force brute. Je me demande s'il n'y
a pas une méthode pour déterminer les "points faibles" du graphe (ou
découper le graphe en sous-ensembles en retirant le moins de noeuds
possibles). Pour trouver les sous-graphes, il faut que le graphe soit
déjà découpé en morceaux, alors que le mien est connexe et je cherche
à le découper. Une idée plus précise pour ce découpage ?

Ça me fait penser à mes cours de traitement d'image. Je peux
tenter d'éroder le territoire en retirant ses cases frontalières : ça
permet un découpage en grandes zones, ça peut être un début.

Yliur a écrit :


Hum... je ne vois pas. Je peux faire ce dont je parlais dans un
paragraphe précédent, en retirant des cases/noeuds et en regardant ce
que ça donne, mais c'est un peu par force brute. Je me demande s'il n'y
a pas une méthode pour déterminer les "points faibles" du graphe (ou
découper le graphe en sous-ensembles en retirant le moins de noeuds
possibles).


Les "points faibles" sont les noeuds du graphe de plus petit degré ≥ 2
(ayant le moins d'arc).

Mais de toutes façons, il faut faire preuve d'imagination pour inventer
un algorithme ou une heuristique.



--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Le Sat, 15 Oct 2011 20:15:55 +0200
"Pascal J. Bourguignon" a écrit :


Yliur a écrit :


Hum... je ne vois pas. Je peux faire ce dont je parlais dans un
paragraphe précédent, en retirant des cases/noeuds et en regardant
ce que ça donne, mais c'est un peu par force brute. Je me demande
s'il n'y a pas une méthode pour déterminer les "points faibles" du
graphe (ou découper le graphe en sous-ensembles en retirant le
moins de noeuds possibles).


Les "points faibles" sont les noeuds du graphe de plus petit degré ≥ 2
(ayant le moins d'arc).


Oui, mais c'est un peu facile . Si la bande reliant deux territoires
est un peu plus large, cette méthode ne permet par de différencier une
frontière quelconque d'une bande étroite.

Exemples (le nombre représente le degré du noeud) :

Territoire large

35555553
58888885
58888885
35555553


Bande (entre deux parties plus larges

.... ...
....6555556...
....6555556...
.... ...


Mais de toutes façons, il faut faire preuve d'imagination pour
inventer un algorithme ou une heuristique.


Je me demandais s'il y avait des algos déjà découverts pour ça. Ou des
idées dans lesquelles piocher.

Pour l'instant j'ai la possibilité érosion + force brute sur les cases
mises en valeur (celles qui, une fois supprimées par l'érosion, ont
permis un découpage en zones intéressant). Mais si d'autres ont des
idées alternatives ça peut m'intéresser.

Bonjour,

Le 15/10/2011 01:16, Yliur a écrit :



Le problème : pour un territoire de forme quelconque, constitué de
cases, j'aimerais trouver les manières les plus simples de couper le
territoire en deux (par "plus simple" j'entends en retirant le moins de
cases possibles).

C'est assez court comme description, mais je ne vois pas quoi ajouter
pour que ce soit plus clair. N'hésitez pas à demander des
précisions .


Je pense qu'il faudrait préciser un peu plus ce que l'on veut
garder. Par exemple, considère le territoire suivant (avec une
police de caractères à espacement fixe c'est mieux) :

########################### ####################################
########################### ####################################
########################### ####################################
##################################################################
##################################################################
##################################################################
##################################################################
##################################################################
########################### ####################################
########################### ####################################
########################### ####################################

Tu devrais trouver facilement comment le couper en deux en ne
retirant que cinq cases, par exemple comme ceci :

########################### ####################################
########################### ####################################
########################### ####################################
############################ #####################################
############################ #####################################
############################ #####################################
############################ #####################################
############################ #####################################
########################### ####################################
########################### ####################################
########################### ####################################

Mais sans précision supplémentaire un programme devrait le couper en
deux en retirant encore moins de cases (trois exactement, voire deux
si les cases doivent se toucher par un côté et pas par un coin pour
faire partie d'un seul et même territoire) :

# ######################### ####################################
######################### ####################################
########################### ####################################
##################################################################
##################################################################
##################################################################
##################################################################
##################################################################
########################### ####################################
########################### ####################################
########################### ####################################

Cordialement,
--
Olivier Miakinen

Poser votre question sur le forum Programmation

Questions similaires :

Où couper une ligne

Bonjour, Je suis confronté à un petit problème fort sympathique, mais plutôt que vouloire réinventer la roue, je me demandais s'il y avait des pistes intéressantes à suivre. J'ai une table des matières classique, soit . Souvent, la longueur est supérieure à la taille de la...