Théorème des quatre couleurs

[invitec0f983f7]

A vrai dire, je ne comprends pas si vous lancez un défi mathématique (algorithme, calcul de complexité, etc) ou informatique (écrire un module, qui utilise une donnée de départ sous forme géographique, sans prétraitement, etc)
-----

[Dlzlogic]

*** Inutilement agressif ***
Pour résumer, le théorème des quatre couleurs est démontré. Il n'y a aucun doute.
Il se trouve qu'on a peut-être besoin de colorier un ensemble de zones en n'utilisant que quatre couleurs. On sait que c'est possible, cf. le théorème sus-nommé. Le but de ce topic est "comment fait-on ?". L'algorithme proposé (Wiki) me parait inacceptable pour un grand nombre de zones et in-intéressant de façon générale.
Je reprécise les données : on dispose d'une liste de zones répondant aux hypothèses du théorème des quatre couleurs. Ces zones sont définies par leur périmètre.
Ma question (défi) : écrire un algorithme permettant d'attribuer une couleur conformément aux hypothèses précitées.

[Dlzlogic]

Petit complément à mon message précédent.
J'ai l'impression que JohnArto fait un amalgame ou une confusion entre "algorithme" et "code".
Un algorithme est une suite d'instructions logiques écrites dans une langue quelconque, de préférence en français pour ou forum français, mais compréhensible par tout le monde, un code est une suite d'instructions logiques écrites dans un certain langage compréhensible par un programme informatique. Naturellement les individus, appelés généralement informaticiens, comprennent ce langage s'ils l'on étudié.
Le terme "prétraitement", employé par notre ami, mérite d'être expliqué.

[Deedee81]

Salut,

A vrai dire, je n'ose pas imaginer le temps d'exécution que ça prendrait. Faire un boucla systématique, c'est casse-cou en informatique.

D'accord, merci. Il est vrai que je ne les ai pas essayé.

J'ai l'impression que JohnArto fait un amalgame ou une confusion entre "algorithme" et "code".

Ben non, il ne confond pas puisque justement il dit qu'il n'a pas compris si la question portait sur l'un ou sur l'autre.

Ta question porte sur l'algorithme, si j'ai bien compris, et non son implémentation. Tu confirmes ?

Le prétraitement fait sans doute référence à la mise en forme des données, par exemple satellite, pour en faire des données exploitables par un programme de coloriage. John Arto confirmera
(c'est amusant mais on a le même au boulot. Je travaille au Ministère de l'Agriculture et les photos satellites sont converties informatiquement en parcelles. Mais je ne connais pas les algo employé. Faudrait que je pose la question, un des cracs du domaine est justement à l'étage en dessous du miens. C'est la remarque sur le prétraitement qui m'y a fait penser ).

[invitec0f983f7]

Bonjour
Dlzlogic, je ne confonds pas et je n'amalgame pas les termes algorithme et code, j'entends très bien votre explication à ce sujet.

Seulement, dans votre premier message introduisant la discussion, vous écrivez qu'il parait intéressant d'écrire un module (donc du code !) et qu'il est bien évident que la donnée de départ est sous forme géographique (géométrique ? ensemble de points) et non un pré-traitement de proximité réalisé par un humain (à vous d'expliquer ce terme "pré-traitement").

Puis après, dans votre message juste ci-dessus, votre défi est d'écrire un algorithme (donc pas du code !) permettant d'attribuer une couleur conformément aux hypothèses du théorème des 4 couleurs, en mettant l'accent sur l'inefficacité de l'algo proposé sur wiki (lien direct avec la complexité).

[minushabens]

Ma question (défi) : écrire un algorithme permettant d'attribuer une couleur conformément aux hypothèses précitées.

il me semble qu'il en existe déjà quelques-uns. Beaucoup de cartes peuvent être coloriées avec 3 couleurs (mais pas la carte des départements français à cause du département de la Seine) et il existe des algorithmes de 3-coloriage, qui donc ne réussissent pas toujours.

[Dlzlogic]

Bonjour,
Je vais essayer de répondre aux questions.
"Il serait intéressant d'écrire un module", Oui, si on veut utiliser l'algorithme qu'on a écrit, J'ai écrit le code, parce que j'en avais besoin, mais pour celui qui n'en a pas besoin, il peut se contenter de l'algorithme, l'écriture du code, il pourra le confier à n'importe qui et qui l'écrira avec le langage de son choix.

Je crois avoir précisé que la donnée de départ était une liste de zones sans trou ni recouvrement, définies par leur périmètre. Donc, je ne vois pas de quel prétraitement il pourrait s'agir. Les logiciels de DAO produisent des données qui sont écrites dans un format qui répond à ces hypothèses. Pour être tout à fait précis dans ma réponse, "sans trou ni recouvrement" signifie que le tronçon de ligne qui définit la limite deux zones doit être constitué exactement des mêmes points.

Par contre, le traitement à partir de photos satellite pose d'autres problèmes, d'abord un problème de redressement et de calage, que je connais un peu en matière de photos aérienne, mais pas de photo-satellite. Donc concernant ce point, je suis ignorant. J'imagine que l'intérêt de telles photos réside dans le fait qu'on peut différencier les zones par la différenciation de couleur.

J'ai un peu de mal à imaginer un algorithme à 3-coloriage, puisque la figure la plus petite (simple) est le triangle, et un triangle a 3 voisins, donc 4 couleurs au moins. Un lien m'intéresserait.

[feanorel]

Admettons qu'à partir des périmètres (on ne sait pas comment ils sont donnés, ni si les données sont cohérentes...) on soit capable de déterminer quels sont les départements voisins les uns des autres. On peut donc construire le graphe des contingence et se ramener à colorier le graphe. Pour colorier le graphe 3 méthodes possibles :
- une résolution quasi-brutale simple à coder : je donne récursivement la première couleur admissible à un voisin de mon point courant, et retourne en arrière si je dois dépasser 4. Extrêmement lent.
- une heuristique (type recuit simulé ou algorithme génétique) un peu plus compliqué à coder mais probablement assez efficace dans la majorité des cas.
- une méthode exacte et rapide : voir par exemple http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf (tirée de la preuve du théorème des 4 couleurs). Elle le fait en temps quadratique.

[Deedee81]

- une méthode exacte et rapide : voir par exemple http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf (tirée de la preuve du théorème des 4 couleurs). Elle le fait en temps quadratique.

Ah, j'allais parler de la méthode DSATUR (après avoir été consulter mon collègue), heuristique. Mais une méthode exact quadratique c'est franchement pas mal.

[invitec0f983f7]

Admettons qu'à partir des périmètres (on ne sait pas comment ils sont donnés, ni si les données sont cohérentes...) on soit capable de déterminer quels sont les départements voisins les uns des autres. On peut donc construire le graphe des contingence et se ramener à colorier le graphe. Pour colorier le graphe (...)

c'est en substance ce que j'ai répondu (message n°2 de cette discussion).

3 méthodes possibles :
- une résolution quasi-brutale simple à coder : je donne récursivement la première couleur admissible à un voisin de mon point courant, et retourne en arrière si je dois dépasser 4. Extrêmement lent.
- une heuristique (type recuit simulé ou algorithme génétique) un peu plus compliqué à coder mais probablement assez efficace dans la majorité des cas.
- une méthode exacte et rapide : voir par exemple http://people.math.gatech.edu/~thomas/PAP/fcstoc.pdf (tirée de la preuve du théorème des 4 couleurs). Elle le fait en temps quadratique.

Bien sûr votre liste ne se veut pas exhaustive, mais est-ce que cet ensemble de méthodes que vous avez choisies de citer montre que les algorithmes naïfs ont peu de chance d'être efficaces ?

[invite75a796c1]

Salut,

il n'y a pas d'algo connu facile ou bien alors ce sont des heuristiques approchées ( cf Wiki le lien de Deedee ) .
Pour les heuristiques utilisées professionnellement, je suppose qu'avec quelques contraintes précisées i, on peut rendre des cartes difficiles solubles rapidement.

En fait, très peu de problèmes sont démontrés comme fondamentalement NP-hard. C'est plutôt l'algo utilisé qui l'est. On peut tout à fait en découvrir un facile auquel personne n'avait pensé. C'est pourquoi je demandais des détails à DlzLogic au début du fil

[Dlzlogic]

Pour répondre à Mike,
Les départements Français sont un bon exemple, sachant que le problème des enclaves est un point supplémentaire ne faisant pas partie du problème lui-même, qui consiste à colorier n'importe quel ensemble de zones accolées, de façon que 2 zones limitrophes aient des couleurs différentes. Il s'agit exactement et strictement de mettre en oeuvre ce théorème.
Un petit indice, il est bon d'utiliser Delaunay (mathématicien Russe comme son nom l'indique).

[minushabens]

J'ai un peu de mal à imaginer un algorithme à 3-coloriage, puisque la figure la plus petite (simple) est le triangle, et un triangle a 3 voisins, donc 4 couleurs au moins. Un lien m'intéresserait.

c'est plus simple de raisonner sur le graphe dual. Le triangle et ses trois voisins qui se touchent deux à deux, en dual c'est le graphe complet à 4 sommets, K4. L'obstruction la plus simple au 3-coloriage est le fait d'avoir K4 comme sous-graphe. Mais il y a des graphes qui ne contiennent pas K4 et qui ne sont pas 3-coloriables. Si tu regardes une carte de états-unis, tu verras que le Nevada est entouré d'une couronne de 5 états. On ne peut pas colorier ces 6 états avec 3 couleurs. Un sommet entouré d'une couronne de 5 sommets est une obstruction au 3-coloriage. Il y en a d'autres.

[invite75a796c1]

Un petit indice, il est bon d'utiliser Delaunay (mathématicien Russe comme son nom l'indique).

Donc, on a des graphes et leurs sous graphes, chaque graphe unitaire peut utiliser 4 couleurs et exporte une partie d'entre elles en tant que sous-graphe vers le graphe d'ordre supérieur. Donc, au début les palettes sont locales à chaque sous graphe. On peut ne les rapprocher qu'à la fin ou bien avant, sur certains noeuds, ceux où les couleurs exportées par les sous-graphes n'ont pas besoin de passer au noeud supérieur. Avec les couleurs "flottantes", ce serait ma simplification principale , utilisant déjà ce mécanisme dans un pré-compilateur. Certaines infos exportées vers les parents sont perdues après 2 ou 3 pas, ce qui réduit considérablement les calculs.

Comment la base est elle fournie ? suite de points à joindre et bouclant sur le 1er ?
Il est utile de retrouver la démo pour la liste des sous-graphes. Ensuite les reconnaitre et pour chacun s'assurer de savoir retrouver sa solution. Si les graphes de base sont faciles à distinguer , il y a moyen d'être performant.

Il faut transformer les données efficacement et après, coder les 500 sous-graphes possibles. Faisable mais c'est un programme assez lourd à écrire. Avoir celui de la démo ferait gagner plusieurs jours. Il faudrait un challenge avec temps d'exécution pour 100.000 zones sur la carte et la promesse que ça serve à quelque chose ...

[invitec0f983f7]

un triangle a 3 voisins, donc 4 couleurs au moins

un carré a 4 voisins, donc 5 couleurs au moins ?

[Dlzlogic]

Bonjour,
@ Mike.
Je ne comprends pas pourquoi tu parles de graphe et surtout de sous-graphe. Je ne vois pas l'intérêt d'utiliser la notion de graphe dans le présent problème. Pour moi, mais j'ai certainement tort, l'intérêt des graphe est évident lorsqu'il y a la notion de chemin et de nœuds, il ne me semble pas que ce soit le cas ici.
La base est constituée d'une liste de zones. Une zone est constituée d'une liste ordonnée de points. Le dernier est effectivement identique au premier (c'est une convention généralement adoptée). Les formats les plus connus sont DXF, dwg Jsi, XYZ, Shp, Mif. Chacun a ses petites particularités mais le principe reste le même.
Tu parles aussi de "démo", je ne vois pas à quoi tu fais allusion.
100 000 zones ça parait beaucoup, quel serait le contexte ?
Concernant la promesse que ça serve à quelque-chose ??? La question a été posée sur un forum de SIG, donc, on peut supposer que c'était pour servir. J'ai en face de moi la carte de France administrative, avec ses anciennes régions. Les régions utilisent quatre couleurs : jaune-orangé, vert, violet et bleu. Les département, à l'intérieur des régions sont coloriés avec des nuances de la couleur principale.
Article lu dans mon journal préféré : "L'IGN édite la nouvelle carte de France administrative". J'ai une toute petite image. Le coloriage est fait sur le même principe que l'ancienne.

@ JohnArto.
Une ile, quelle que soit sa forme a 0 voisin. Un département de métropole a généralement au moins 1 voisin (ex Corse). On peut être "presque sûr" qu'un département ordinaire, c'est à dite non limitrophe à une frontière, a au moins 3 voisins, un à droite, un à gauche et un en bas. La forme géométrique n'a rien à voir. C'est la disposition qui est intéressante à utiliser. J'avoue que j'ai un peu de mal à comprendre ta question, c'est à dire où tu veux réellement en venir.

[minushabens]

Je ne comprends pas pourquoi tu parles de graphe et surtout de sous-graphe. Je ne vois pas l'intérêt d'utiliser la notion de graphe dans le présent problème.

c'est pourtant en raisonnant sur le graphe dual de la carte qu'on a démontré le théorème des quatre couleurs. Tu peux en rester à la carte mais puisque le problème est combinatoire, il te faut de toutes façons "oublier" la forme des contours et considérer une idéalisation, le graphe sous-jacent à la carte.

[Dlzlogic]

Bonjour Minushabens,
J'ai l'impression que je n'ai pas bien posé ma question d'origine.
1- je sais qu'il y a un "fameux" théorème des quatre couleurs. Je crois avoir lu à peu près tout ce qu'il peut y avoir sur le net à ce sujet. Il est même cité à titre d'exemple à différents points de vue.
2- ma préoccupation ne consiste en aucun cas à discuter du sujet "démonstration du théorème des quatre couleurs". J'admets la validité de ce théorème.
3- ma question consiste à appliquer ce théorème, c'est à dire colorier un ensemble de zones qui répondent à ces hypothèses. La conclusion du théorème est que cette opération est possible, donc je propose de la réaliser.
4- je la formule sous la forme "écrire un algorithme". Si on veut aussi écrire un code, pourquoi pas, mais autant commencer par l'algorithme. L'écriture du code dépend du langage et est à la portée de tout le monde qui sait coder dans son langage préféré.
5- je donne une piste, la caractéristique d'un triangle. Mais ce n'est qu'un avis personnel.

Même si je n'en comprends pas la raison, je veux bien qu'on parle de graphe. Je me permets tout de même de rappeler qu'un algorithme doit être compréhensible par n'importe quel programmeur, n'y connaissant rien en mathématique, géométrie et autres sciences abstraites. Sa participation doit se limier à traduire ce qui a été écrit en français dans le langage que son compilateur connait

[invitec0f983f7]

Bonjour,
C'est étonnant de dire qu'on a lu à peu près tout sur le sujet (déjà surprenant), et ne pas comprendre qu'on parle de graphe quand on veut colorier une carte...

Sinon, l'algorithme ne peut-il pas commencer par ceci ?
- Les données étant des listes de points (segments ?) formant les périmètres de chaque zone, on peut établir la liste des zones adjacentes (un segment commun sur les périmètres indique des zones limitrophes).
- Puis une fois les zones adjacentes connues, on peut se lancer dans la résolution proprement dite du problème de coloration en 4 couleurs avec le graphe dont les sommets désignent les zones et les arrêtes marquent la relation de voisinage.

[Dlzlogic]

@ JohnArto,
Oui, bien-sûr, tu peux essayer cela, mais je doute fort que tu arrives au bout. Pour une petite dizaine de zones, ça marcherait sûrement, mais à la main, on irait aussi vite. Il vaut mieux trouver autre-chose.

[invite75a796c1]

ce que ces graphes ont de remarquable, c'est qu'une donnée qu'on pourrait croire universelle ou absolue ( la couleur ) est en fait un index dans une palette locale. Elle n'est caractérisée que si on le veut et en général plus tard. On peut en fixer arbitrairement quelques unes mais pas toutes.

Dans les graphes de généalogie d'espèces et de toute filiation par génération/mutation-rupture , c'est pareil mais là c'est une échelle de durées qui est locale.

C'est léger au 1er abord mais exact ...

[invitec0f983f7]

@Dlzlogic,
Ne pas arriver, je veux bien, mais où est le problème : c'est la détection des zones voisines ou la coloration du graphe ?

[Dlzlogic]

@ Mike,
Oui, j'ai peu utilisé cette logique des graphes, mais je crois la connaitre suffisamment pour dire qu'utilisée telle quelle, je doute de l'efficacité. Mais évidemment, sur le principe, ça pourrait marcher. En informatique, on appelle ça quelque-fois, la "force brute". En fait, rien ne prouve que le programme ne bouclerait pas, sauf à conserver en mémoire toutes les étapes précédentes. De toute façon, il faudrait apprendre à la machine ce qu'est un graphe.
Pour concrétiser ce que je veux dire, une zone peut avoir un nombre variable de voisins, ce qui risque de rendre la méthode de graphe inefficace.

[feanorel]

Les graphes ici servent à formaliser proprement et sans information superflu le problème. L'algo utilisé ensuite pour colorer le graphe peut-être l'un de ceux que j'ai (ou que d'autres ont) cités précedemment sans forcément être de la force brute. Comme je l'ai dis il y a même un algo en temps quadratique...
Par ailleurs il peut être intéressant de savoir qu'une bonne partie des cours de recherche opérationelle (une branche des mathématiques appliquées, parfois ratachée à l'informatique) commence en expliquant que le graphe est l'élément de base de la modélisation. Et on peut représenter de nombreux problème à l'aide de graphe sur lesquels ont peu appliqué des algos très efficaces (plus court chemin, max-flow / min-cut, etc.). Exemple de problème où il n'y a pas a priori de graphe naturel :
- on dispose d'un appartement à louer pendant l'été
- on dispose d'une liste de demandes contenant (jour d'arrivée - jour de départ - prix proposé)
question : lesquelles choisir pour maximiser ses gains sur l'été ?
(ceci se résout facilement avec un algo de plus court chemin).

[invitec0f983f7]

Dlzlogic,
La force brute ne fonctionne pas beaucoup, mais il y a des algorithmes sur les graphes bien plus efficaces.
Vous avez lu beaucoup de choses sur le sujet, que pensez-vous des algorithmes dont que feanorel a présentés ici ? http://forums.futura-sciences.com/ma...ml#post5620135

[Dlzlogic]

Ok pour le terme "graphe".
Par contre, ce que j'essaye de suggérer est que cela ne me semble pas une bonne idée de prendre pour point, ou noeud, l'identité zone.
C'est le seul intérêt et la seule raison pour laquelle j'ai créé ce sujet.
Mais il est vrai que ma méthode met en oeuvre une organisation du type "graphe", mais pas de la façon que l'on peut lire sur le net.

[Médiat]

Bonjour,

Quel est l'intérêt de ce fil ?

Vous prétendez avoir un algorithme pour résoudre un problème pour lequel on connaît des algorithmes, et vous ne voulez rien dire du vôtre, ni même s'il est mieux que "temps quadratique" ?

[invite75a796c1]

@ Mike,
Oui, j'ai peu utilisé cette logique des graphes, mais je crois la connaitre suffisamment pour dire qu'utilisée telle quelle, je doute de l'efficacité. Mais évidemment, sur le principe, ça pourrait marcher. En informatique, on appelle ça quelque-fois, la "force brute". En fait, rien ne prouve que le programme ne bouclerait pas, sauf à conserver en mémoire toutes les étapes précédentes. De toute façon, il faudrait apprendre à la machine ce qu'est un graphe.
Pour concrétiser ce que je veux dire, une zone peut avoir un nombre variable de voisins, ce qui risque de rendre la méthode de graphe inefficace.

m'enfin ! une démonstration sait retrouver la solution pour chacun des sous graphes possibles. Partant de là, il suffirait de faire de la recherche de patterns et d'appliquer des solutions aménagées pour l'optimisation ; histoire de s'amuser, je propose l'établissement d'une grammaire et de procéder comme un pré compilateur. C'est de la recherche brute mais qui collerait à la démo en utilisant des outils informatiques rodés.

Ou bien alors, on déroule l'autre hypothèse : votre algo est exact, il est moins difficile que celui donné en référence dans la littérature et wiki et il faut 1) le vérifier 2) le publier si tout est ok.

En attendant les resultats du bremain, je vais aller à la recherche de la démo afin d'être plus précis en pointant sur ce qu'il faut en récupérer.

[Dlzlogic]

Bonsoir,
Je n'ai jamais cherché à cacher quoi que ce soit.
Les détails sur mon algo, je les ai décrits il y a quelques années dans le cadre du forum de SIG concerné. Il a été lu et approuvé par le modérateur spécialiste de ce genre de chose, mais pas d'autre réaction.
Depuis j'ai évoqué le sujet (au moins une fois) et à part des réactions du genre "le théorème a été démontré", cela n'a pas semblé intéresser grand-monde.
Naturellement, à l'époque, suite à mes lectures, l'ai commencé par écrire un truc basé sur les "graphes". Je me suis bien vite rendu compte que ce n'était pas réaliste.
Alors, en gros, voila ma méthode :
1- j'identifie tous les points caractéristiques, c'est à dire les "points communs" à 3 zones.
2- à l'aide de ces points je crée une triangulation (cf Delaunay).
3- éventuellement certains côté (diagonales) doivent être échangés.
4- chaque zone est maintenant constituée de triangles. C'est à dire que tous les triangles de cette zone ont la même couleur.
5- point très important et qui justifie la méthode, un triangle ne peut avoir que 3 voisins. Comme la couleur de ce triangle est fixée, ainsi que le voisin qui l'a colorié, il reste au maximum 2 couleurs possibles.

L'intérêt de cette méthode est qu'il n'y a pas de retour en arrière. Si on tombe sur un cul-de-sac, on recommence au départ en prenant un autre triangle comme origine.
Tous les détails voulus demain. Si on m'avait dit depuis le début "donne ta méthode", je l'aurais fait.
Bonne soirée.

[invitec0f983f7]

Par contre, ce que j'essaye de suggérer est que cela ne me semble pas une bonne idée de prendre pour point, ou noeud, l'identité zone.
C'est le seul intérêt et la seule raison pour laquelle j'ai créé ce sujet.

Okey, je comprends maintenant !

De toute manière, tout coloriage de la carte correspond au coloriage du graphe des zones adjacentes...