Quatre couleurs

[Dlzlogic]

Bonjour,
Le théorème ou théorie des 4 couleurs dit que, étant donnée des zones jointives, sans recouvrement, comme par exemple les départements, il est possible de colorer ces zones avec seulement 4 couleurs, tel que 2 zones ayant une limite commune soient colorées avec 2 couleurs différentes.
La question posée : établir un algorithme qui réalise cela.

[Doraki]

Je propose l'algorithme qui prend un graphe planaire et qui explore tous ses coloriages à 4 couleurs possibles jusqu'à ce qu'il en trouve un qui marche.

[Dlzlogic]

Oui, il est vrai que un graphe est utilisé, encore faut-il le créer.
Les zones sont défies par de lignes fermées. la comparaison de deux zones limitrophes est bonne, c'est à dire que leur frontière commune sera effectivement un arc du graphe.
Pour des raisons de temps de traitement, il est exclu de faire une recherche systématique. En d'autres termes il faut orienter la recherche de façon à y arriver très vite.
De ce que je sais des graphes, ils traitent des chemins et non des zones, mais je peux me tromper.

[fatal_error]

De la même manière mais en élaguant:
on représente nos noeuds X_1,...,X_n qui prennent une valeur parmi 4 différente (1,2,3,4 par ex)
Et on écrit les relations X_i!=X_j quand avéré.
Et après on envoit ca a un solveur!

Genre en prolog ca doit etre immédiat.

[Dlzlogic]

Bonjour,

Et après on envoit ca a un solveur!
Genre en prolog ca doit etre immédiat.

Tu imagines ce que ça pourrait faire pour 99 départements .
Une zone peur avoir de 1 à n voisins.
En tout cas, tel que tu le décris, je ne saurais pas le développer.
J'avais lu une description de la méthode de Monté Carlo, est-ce à un truc de ce genre que tu fais allusion par "solveur"?

[fatal_error]

Tu imagines ce que ça pourrait faire pour 99 départements .

vaguement oui, en comparant a un sudoku de 81 variables.

En tout cas, tel que tu le décris, je ne saurais pas le développer.
J'avais lu une description de la méthode de Monté Carlo, est-ce à un truc de ce genre que tu fais allusion par "solveur"?

pas du tout. plutot dans ce genre

[Dlzlogic]

Moi qui pensais proposer un défi intéressant :cry:

Voila l'algorithme que j'utilise :
Les polygones définissent des chemins. Un chemin est une ligne brisée qui ne coupe aucun autre autre chemin.
Les extrémités de ces chemins sont les points permettent de définir une
triangulation de Delaunay
On remplace les côtés de triangle par la diagonale du quadrilatère correspondant
si celle-ci est un côté de polygone.
Les triangles strictement contenus dans le polygone sont supprimés.
A chaque triangle on attribue une couleurs (de 1 à 4) telle qu'un côté de triangle
est une séparation de couleur.
Pour chaque polygone, on attribue une couleur.
Les couleurs des triangles contenus dans le polygone seront modifiées et les triangles
voisins seront modifiés de la même façon, pour respecter la différenciation
des couleurs entre 2 triangles voisins.

La méthode est basée sur le fait qu'un triangle a 3 voisins. Sa couleur, plus celle de ses 3 voisins font toujours 4 couleurs, dans tous les cas.
Il peut arriver que, à la fin des échanges de couleur, on tombe sur une impossibilité. Le polygone de départ a été mal choisi, on recommence avec un autre. Des simulations ont montré que deux ou trois essais permettaient d'aboutir à la solution.

[mathieuH]

Bonjour,

Pour ceux qui aiment l'algèbre, voici comment résoudre ce problème:
chaque pays est représenté par une variable qui est l'une des couleurs .
Alors la solution du coloriage est la solution complexe du système contenant les équations:
- pour chaque pays,
- pour chaque frontière entre le pays X_i et X_j,

cela peut se résoudre automatiquement en cherchant les générateurs de l'idéal associé à ce système => bases de Groebner. La solution donne alors un coloriage admissible.
On peut même exprimer ceci pour 3 couleurs, ce qui permet de vérifier automatiquement l'existence ou non d'une solution à 3 couleurs.

bonne réflexion

[Dlzlogic]

@ MathieuH
Là j'avoue que ça me dépasse complètement.
Par contre, quand je lis "... est la solution ...", cela sous-entend que la solution existe toujours, à condition que ce système comporte toujours au moins une solution.
Or, d'après mes lectures, ce théorème n'a pas (encore) été démontré. Soit ce système permettrait de le démontrer, soit ce système admet au moins une solution, mais on ne sait pas le démontrer.

Pour être rigoureux dans les termes, j'ai cru comprendre que des pseudo-démonstrations on été faites, ce qui rend ce théorème incontestable et incontesté, par contre aucune démonstration "rigoureuse" n'a été acceptée par la communauté scientifique.

Par ailleurs, tout le monde a compris que ce qui m'intéressait dans cet algorithme est l'utilisation des triangles.

Ce système est facile ou possible à résoudre par un traitement informatique ? Peut-on le mettre sous forme linéaire. Pardon, ce sont des questions d'ignorant. :marteau:

[Doraki]

Or, d'après mes lectures, ce théorème n'a pas (encore) été démontré. Soit ce système permettrait de le démontrer, soit ce système admet au moins une solution, mais on ne sait pas le démontrer.

Il a été démontré par des longs calculs en 1976. Longs calculs que personne ne peut raisonnablement vérifier à la main mais que des ordinateurs peuvent vérifier sans problème.
Depuis il a été simplifié et entièrement formalisé et prouvé dans l'assistant de preuves Coq.

Par ailleurs, tout le monde a compris que ce qui m'intéressait dans cet algorithme est l'utilisation des triangles.

J'ai absolument rien compris à ton algorithme, mais ça m'a rappelé un sujet d'informatique du concours de polytechnique d'il y a longtemps.

Ce système est facile ou possible à résoudre par un traitement informatique ? Peut-on le mettre sous forme linéaire. Pardon, ce sont des questions d'ignorant. :marteau:

En programmation logique (prolog), essentiellement on essaye de colorier de proche en proche en revenant en arrière si on y arrive pas. La complexité devrait être exponentielle.

Peut-être qu'en tirant au sort quelques trucs puis en essayant de compléter de manière déterministe, on obtient un bon truc, mais faudrait avoir une idée de la pire probabilité de succès possible (faudrait que je me rappelle de ce sujet de polytechnique).

A part ça, [url]http://fr.wikipedia.org/wiki/Théorème_des_quatre_couleurs[/url] mentionne qu'on peut tirer un algorithme quadratique à partir de la preuve de Appel et Haken.
Vu que le théorème a été prouvé dans l'assistant de preuves Coq, celui-ci peut automatiquement en extraire un algorithme, mais je sais pas s'ils ont essayé de voir sa complexité.

[Dlzlogic]

@ Doraki,
Bien-sûr j'avais déjà lu tout ça et même d'autres choses.
Ce que j'ai dit est que le théorème avait été vérifié, mais non démontré.
Il y a eu il y a environ 1 ans de nouveaux essais. J'ai pas tout compris mais il me semble que la logique adoptée était de faire un "algorithme de démonstration", c'était toujours la machine qui bossait mais en prenant le problème par l'autre bout.
En fait la seule chose qui m'intéresse vraiment c'est de pouvoir colorer des zones.
Qu'est-ce qui n'est pas clair dans l'algorithme que j'ai décrit ?