Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Couper un territoire en deux le plus simplement possible
6 views
Skip to first unread message
Yliur
Oct 14, 2011, 7:16:58 PM10/14/11
to
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
Pascal J. Bourguignon
Oct 14, 2011, 8:09:35 PM10/14/11
to
Yliur <yl...@free.fr> writes:
> 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,
> 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.
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 {}.
Yliur
Oct 15, 2011, 1:27:09 PM10/15/11
to
Le Sat, 15 Oct 2011 02:09:35 +0200
"Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
> Yliur <yl...@free.fr> writes:
> > 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.
"Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
> Yliur <yl...@free.fr> writes:
> > 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.
>
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.
Pascal J. Bourguignon
Oct 15, 2011, 2:15:55 PM10/15/11
to
Yliur <yl...@free.fr> writes:
> 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
> 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).
(ayant le moins d'arc).
Mais de toutes façons, il faut faire preuve d'imagination pour inventer
un algorithme ou une heuristique.
Yliur
Oct 15, 2011, 2:40:02 PM10/15/11
to
Le Sat, 15 Oct 2011 20:15:55 +0200
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.
> Yliur <yl...@free.fr> writes:
>
> > 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
>
> > 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).
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.
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.
Olivier Miakinen
Oct 15, 2011, 7:32:34 PM10/15/11
to
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
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 :) .
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
Jean-Marc Bourguet
Oct 19, 2011, 3:51:45 PM10/19/11
to
Yliur <yl...@free.fr> writes:
> 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 ?
Si j'ai bien compris, le problème dont tu cherches la solution s'appelle
> 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 ?
min cut.
A+
--
Jean-Marc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Yliur
Oct 19, 2011, 7:26:51 PM10/19/11
to
Le Wed, 19 Oct 2011 21:51:45 +0200
Jean-Marc Bourguet <j...@bourguet.org> a écrit :
J'ai regardé les histoires de coupe minimale, mais ça semble
s'appliquer à des graphes de flux. Des questions de flux maximal entre
deux noeuds, ...
Dans mon problème la distance entre deux noeuds est toujours la même
(et sans intérêt en fait). Il s'agit d'une grille de cases et je
cherche à programmer quelque chose qui se fait très facilement de
manière visuelle : trouver des portions du territoire qui ont l'air
isolées (rattachées au reste par un "petit bout") et les petits bouts
en question. Il n'y a pas de solution unique, il peut y avoir plusieurs
découpages possibles, qui doivent ensuite être évalués selon l'effort
nécessaire (le nombre de cases à retirer pour le découpage) et la
qualité du résultat (la valeur des régions isolées du reste)
Je vais essayer de faire plus concret : il s'agit d'un jeu de stratégie
sur une grille de cases, chaque case appartenant à un joueur. Les cases
d'un joueur constituent son territoire, en un ou plusieurs blocs. Pour
que le joueur puisse conserver une case, il faut qu'il existe un chemin
entre la case et une des cases-villes du joueur.
Donc le but est de permettre à l'IA de trouver quelles portions du
territoire pourraient être facilement séparées du reste : il s'agit de
couper du reste du monde un ou des ensembles de cases ne contenant pas
de ville, en faisant le moins d'effort possible et en isolant le plus
de cases possibles.
Jean-Marc Bourguet <j...@bourguet.org> a écrit :
s'appliquer à des graphes de flux. Des questions de flux maximal entre
deux noeuds, ...
Dans mon problème la distance entre deux noeuds est toujours la même
(et sans intérêt en fait). Il s'agit d'une grille de cases et je
cherche à programmer quelque chose qui se fait très facilement de
manière visuelle : trouver des portions du territoire qui ont l'air
isolées (rattachées au reste par un "petit bout") et les petits bouts
en question. Il n'y a pas de solution unique, il peut y avoir plusieurs
découpages possibles, qui doivent ensuite être évalués selon l'effort
nécessaire (le nombre de cases à retirer pour le découpage) et la
qualité du résultat (la valeur des régions isolées du reste)
Je vais essayer de faire plus concret : il s'agit d'un jeu de stratégie
sur une grille de cases, chaque case appartenant à un joueur. Les cases
d'un joueur constituent son territoire, en un ou plusieurs blocs. Pour
que le joueur puisse conserver une case, il faut qu'il existe un chemin
entre la case et une des cases-villes du joueur.
Donc le but est de permettre à l'IA de trouver quelles portions du
territoire pourraient être facilement séparées du reste : il s'agit de
couper du reste du monde un ou des ensembles de cases ne contenant pas
de ville, en faisant le moins d'effort possible et en isolant le plus
de cases possibles.
Pascal J. Bourguignon
Oct 20, 2011, 9:15:20 AM10/20/11
to
Yliur <yl...@free.fr> writes:
> Le Wed, 19 Oct 2011 21:51:45 +0200
> Jean-Marc Bourguet <j...@bourguet.org> a écrit :
>
>> Yliur <yl...@free.fr> writes:
>>
>> > 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 ?
>>
>> Si j'ai bien compris, le problème dont tu cherches la solution
>> s'appelle min cut.
>
> J'ai regardé les histoires de coupe minimale, mais ça semble
> s'appliquer à des graphes de flux. Des questions de flux maximal entre
> deux noeuds, ...
>
> Dans mon problème la distance entre deux noeuds est toujours la même
> (et sans intérêt en fait).
Un peu d'imagination!
> Le Wed, 19 Oct 2011 21:51:45 +0200
> Jean-Marc Bourguet <j...@bourguet.org> a écrit :
>
>> Yliur <yl...@free.fr> writes:
>>
>> > 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 ?
>>
>> Si j'ai bien compris, le problème dont tu cherches la solution
>> s'appelle min cut.
>
> J'ai regardé les histoires de coupe minimale, mais ça semble
> s'appliquer à des graphes de flux. Des questions de flux maximal entre
> deux noeuds, ...
>
> Dans mon problème la distance entre deux noeuds est toujours la même
> (et sans intérêt en fait).
Si chaque case represente un noeud du graphe, et chaque côté commun un
arc, tu peux assigner une capacité de 1.0 à chaque arc, et choisir une
source et une cible à deux extrémités du graphe (par exemple, en les
choisissant sur un diamètre du graphe).
Alors le théorème du flot max / coupe min s'applique parfaitement.
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
> Il s'agit d'une grille de cases et je
> cherche à programmer quelque chose qui se fait très facilement de
> manière visuelle : trouver des portions du territoire qui ont l'air
> isolées (rattachées au reste par un "petit bout") et les petits bouts
> en question. Il n'y a pas de solution unique, il peut y avoir plusieurs
> découpages possibles, qui doivent ensuite être évalués selon l'effort
> nécessaire (le nombre de cases à retirer pour le découpage) et la
> qualité du résultat (la valeur des régions isolées du reste)
avec des réseaux de neurones artificiels. Mais ce sera probablement
plus chèr en calcul.
Yliur
Oct 20, 2011, 1:15:43 PM10/20/11
to
Le Thu, 20 Oct 2011 15:15:20 +0200
"Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
> Yliur <yl...@free.fr> writes:
>
> > Le Wed, 19 Oct 2011 21:51:45 +0200
> > Jean-Marc Bourguet <j...@bourguet.org> a écrit :
> >
> >> Yliur <yl...@free.fr> writes:
> >>
> >> > 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 ?
> >>
> >> Si j'ai bien compris, le problème dont tu cherches la solution
> >> s'appelle min cut.
> >
> > J'ai regardé les histoires de coupe minimale, mais ça semble
> > s'appliquer à des graphes de flux. Des questions de flux maximal
> > entre deux noeuds, ...
> >
> > Dans mon problème la distance entre deux noeuds est toujours la même
> > (et sans intérêt en fait).
>
> Un peu d'imagination!
Le problème c'est surtout d'essayer de comprendre ce que font les
algorithmes concrètement, pour voir s'ils correspondent à mes besoins.
Trouver des explications sous forme de formules c'est bien, mais ça
aide difficilement à se représenter ce que fait "réellement"
l'algorithme pour ensuite l'adapter à autre chose.
> Si chaque case represente un noeud du graphe, et chaque côté commun un
> arc, tu peux assigner une capacité de 1.0 à chaque arc, et choisir une
> source et une cible à deux extrémités du graphe (par exemple, en les
> choisissant sur un diamètre du graphe).
>
> Alors le théorème du flot max / coupe min s'applique parfaitement.
>
> http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
L'algo doit savoir détecter les régions, je ne les ai pas à l'avance.
Donc pour la source j'ai les villes et pour la destination (le "puits")
j'ai toutes les autres cases. Ça ne colle pas très bien au modèle
une source / un puits, mais je retiens l'idée du flot qui s'écoule : les
régions qui m'intéressent sont celles pour lesquelles le débit d'un
flux qui s'écoulerait depuis les villes serait faible (passerait par un
goulet d'étranglement). Je vais jeter un oeil sur les algorithmes de
flots, voir s'il est possible de les adapter pour les "paralléliser",
c'est-à-dire considérer un grand torrent qui s'écoule des villes vers
le reste du monde.
> > Il s'agit d'une grille de cases et je
> > cherche à programmer quelque chose qui se fait très facilement de
> > manière visuelle : trouver des portions du territoire qui ont l'air
> > isolées (rattachées au reste par un "petit bout") et les petits
> > bouts en question. Il n'y a pas de solution unique, il peut y avoir
> > plusieurs découpages possibles, qui doivent ensuite être évalués
> > selon l'effort nécessaire (le nombre de cases à retirer pour le
> > découpage) et la qualité du résultat (la valeur des régions isolées
> > du reste)
>
> Si tu veux avoir une approche "visuelle" de la chose, tu peux le faire
> avec des réseaux de neurones artificiels. Mais ce sera probablement
> plus chèr en calcul.
Cette idée m'a bien traversé l'esprit, mais je crois que je vais éviter
de me lancer là-dedans si j'ai une solution plus simple :) . D'autant
que les réseaux de neurones nécessitent un jeu d'apprentissage plus ou
moins complet, ce qui est déjà compliqué à mettre en place.
"Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
> Yliur <yl...@free.fr> writes:
>
> > Le Wed, 19 Oct 2011 21:51:45 +0200
> > Jean-Marc Bourguet <j...@bourguet.org> a écrit :
> >
> >> Yliur <yl...@free.fr> writes:
> >>
> >> > 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 ?
> >>
> >> Si j'ai bien compris, le problème dont tu cherches la solution
> >> s'appelle min cut.
> >
> > J'ai regardé les histoires de coupe minimale, mais ça semble
> > s'appliquer à des graphes de flux. Des questions de flux maximal
> > entre deux noeuds, ...
> >
> > Dans mon problème la distance entre deux noeuds est toujours la même
> > (et sans intérêt en fait).
>
> Un peu d'imagination!
algorithmes concrètement, pour voir s'ils correspondent à mes besoins.
Trouver des explications sous forme de formules c'est bien, mais ça
aide difficilement à se représenter ce que fait "réellement"
l'algorithme pour ensuite l'adapter à autre chose.
> Si chaque case represente un noeud du graphe, et chaque côté commun un
> arc, tu peux assigner une capacité de 1.0 à chaque arc, et choisir une
> source et une cible à deux extrémités du graphe (par exemple, en les
> choisissant sur un diamètre du graphe).
>
> Alors le théorème du flot max / coupe min s'applique parfaitement.
>
> http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Donc pour la source j'ai les villes et pour la destination (le "puits")
j'ai toutes les autres cases. Ça ne colle pas très bien au modèle
une source / un puits, mais je retiens l'idée du flot qui s'écoule : les
régions qui m'intéressent sont celles pour lesquelles le débit d'un
flux qui s'écoulerait depuis les villes serait faible (passerait par un
goulet d'étranglement). Je vais jeter un oeil sur les algorithmes de
flots, voir s'il est possible de les adapter pour les "paralléliser",
c'est-à-dire considérer un grand torrent qui s'écoule des villes vers
le reste du monde.
> > Il s'agit d'une grille de cases et je
> > cherche à programmer quelque chose qui se fait très facilement de
> > manière visuelle : trouver des portions du territoire qui ont l'air
> > isolées (rattachées au reste par un "petit bout") et les petits
> > bouts en question. Il n'y a pas de solution unique, il peut y avoir
> > plusieurs découpages possibles, qui doivent ensuite être évalués
> > selon l'effort nécessaire (le nombre de cases à retirer pour le
> > découpage) et la qualité du résultat (la valeur des régions isolées
> > du reste)
>
> Si tu veux avoir une approche "visuelle" de la chose, tu peux le faire
> avec des réseaux de neurones artificiels. Mais ce sera probablement
> plus chèr en calcul.
de me lancer là-dedans si j'ai une solution plus simple :) . D'autant
que les réseaux de neurones nécessitent un jeu d'apprentissage plus ou
moins complet, ce qui est déjà compliqué à mettre en place.
Pascal J. Bourguignon
Oct 20, 2011, 3:30:55 PM10/20/11
to
Yliur <yl...@free.fr> writes:
> Le Thu, 20 Oct 2011 15:15:20 +0200
> "Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
>
> Le Thu, 20 Oct 2011 15:15:20 +0200
> "Pascal J. Bourguignon" <p...@informatimago.com> a écrit :
>
>> Un peu d'imagination!
>
> Le problème c'est surtout d'essayer de comprendre ce que font les
> algorithmes concrètement, pour voir s'ils correspondent à mes besoins.
> Trouver des explications sous forme de formules c'est bien, mais ça
> aide difficilement à se représenter ce que fait "réellement"
> l'algorithme pour ensuite l'adapter à autre chose.
Le plus simple, c'est de l'implémenter et de voir ce que ça donne. C'est
>
> Le problème c'est surtout d'essayer de comprendre ce que font les
> algorithmes concrètement, pour voir s'ils correspondent à mes besoins.
> Trouver des explications sous forme de formules c'est bien, mais ça
> aide difficilement à se représenter ce que fait "réellement"
> l'algorithme pour ensuite l'adapter à autre chose.
pour ça qu'on a inventé Lisp.
>> Si chaque case represente un noeud du graphe, et chaque côté commun un
>> arc, tu peux assigner une capacité de 1.0 à chaque arc, et choisir une
>> source et une cible à deux extrémités du graphe (par exemple, en les
>> choisissant sur un diamètre du graphe).
>>
>> Alors le théorème du flot max / coupe min s'applique parfaitement.
>>
>> http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
>
> L'algo doit savoir détecter les régions, je ne les ai pas à l'avance.
> Donc pour la source j'ai les villes et pour la destination (le "puits")
> j'ai toutes les autres cases.
Mais de toutes façons, si tu implémente l'algorithme ci-dessus et si tu
le comprends, avec un peu d'imagination tu n'auras aucune difficulté à
inventer un algorithme similaire pour séparer sur plusieurs régions
plusieurs noeuds.
0 new messages