Bonjour,

J'ai un fichier qui comporte les donnés suivantes :

5 5
Rennes 0 1 25 30
Paris 2 1 55 10
Lille 4 0 10 45
Lyon 2 3 5 55
Marseille 2 4 47 22

Ces données que j'avais récolté dans une liste et un tableau représente en fait un territoire (en forme de rectangle de largeur x hauteur) de plusieurs villes (formée par des rectangle de 1x1) avec leur coordonnées et le nombre de votants de la population pour deux parti :

Dans l'exemple ci-dessus on a en fait :

5 5 (Un territoire 5x5)

Rennes 0 1 25 30 (Nom de la ville, Coordonnée x (Largeur), Coordonné y (Hauteur), Nombre de votant pour le partie N°1, Nombre de votant pour le partie N°2).

Mon but pour l'instant serait de couper en trois rectangle le territoire de façon à ce que le parti N°1 gagne mais aussi qu'il le gagne de façon équilibré.

Pour découper un rectangle en 3 rectangle il faut que le premier placé (rectangle en noir) touche deux bords du territoire et les deux autres (jaune et vert) sont crée par prolongation en largeur ou en hauteur (Configuration A) ou bien le premier placé touche 3 bords du territoire et les deux autres sont crée de telle dans la Configuration B.



Mon idée avant tout était de créer une fonction qui lorsqu'on place un curseur sur le tableau divise le territoire correctement et ainsi on en plaçant le curseur sur toutes les cases on regarde toutes les configurations possible et donc on peut voir quelles sont les configurations avantageuse pour le premier partie.

Mais après je ne sais pas trop ce que signifie de façon équilibré ;

  -  Le Parti N°1 et N°2 soient proche des 50 % ?
  -  Essayer de ne pas regrouper tout les villes N°1 dans un rectangle puis découper en plusieurs N°2 ?
  - Essayer de regrouper les villes gagnante N°1 et N°2 avec un même taux (regrouper Paris dont N°1 gagne (avec 55%) avec Marseille qui gagne N°2 (avec a peu près 55 %) et non la regrouper avec un Lyon qui gagne à 95 % ?


Mais je pense que cette méthode est trop brute (il y a trop de cas), vous connaissez pas une méthode plus élégante/optimal ? Parce que ça me semble un problème connu...

Merci.