Création d'une liste suivant des contraintes

Bonjour,

Je cherche à créer une liste , voire des listes, en fonction de cotraintes imposées. Je dois selectionner des polygones (zones) sachant que je ne peux pas selectionner un polygone le jouxtant pendant les 30 tirages suivants, un tirage correspondant à une année et ce sur une période de 80 ans (80 tirages). J’ai la liste des 49 polygones, la liste pour chaque polygone des polygones limitrophes. Le premier tirage est fixé, et si ne peux pas faire de tirage (pas de possibilité) je passe au tirage suivant.

Exemple début en 2018 avec le polygone 2016, en 2020 les polygones 16 29 24 ont été séléctionnés les autres polygones hachurés ne sont plus sélectionnables, les polygones 10 et 11 ne seront disponibles qu’en 2048 mais le polygone 11 pourra n’être disponible que plus tard si le polygone 13 est sélectionné avant !

Je cherche bien sûr les listes contenant le plus d’éléments (43 44 , …).

Voici un exemple de résultat obtenu : [16,"","",29,"",24,3,"","","",44,27,13,15,25,47,34,38,14,49,"","","","","","","","","","","",10,"",7,21,"",33,4,11,23,"",35,51,"",8,20,45,26,32,30,48,"","","","","","","","","","","","","","",28,"",31,6,2,18,5,43,52,50,12,9,36,22,39] - 44 zones traitées

"" correspond à une année sans ouverture, aucun zone possible . Le début de la liste [16,"","",29,"",24] est imposé car déjà réalisé, la suite [3,"","","",44,27] plus ou moins mais les 3 zones doivent être travaillées dans la période de ces 6 années, ensuite c’est plus libre.

Le script python que j’ai réalisé fonctionne par tirage au sort dans une liste des zones possibles chaque année modifiée en fonction des tirages réalisés.

Je cherche donc une méthode plus rapide. Je suis plutôt géomaticien que matheux ou statisticiens ..

Merci de votre aide

Frédéric

D’où viennent tes cartes exactement ? Je conjecture que le problème général (où 80, 49, etc. sont des variables) est difficile, mais on peut probablement résoudre tes exemples optimalement en bidouillant.

En fait on peut facilement trouver des bornes inférieures pour ton problème à partir d’un problème de coloriage : les sommets que tu tires dans les temps 1 à 30, 31 à 60 et 61 à 80 forment des ensembles indépendants, donc si jamais il y a une solution à ton problème contenant tous les sommets, alors ça veut dire qu’on peut colorier ta carte avec 3 couleurs (sans que 2 zones adjacentes aient la même couleur). En fait, je ne sais pas si ce cas est exclu, parce que c’est pas très clair si ta carte est 3-coloriable ou pas (une obstruction simple à ça c’est si t’as un cycle induit de taille 4, or il est assez remarquable qu’il n’y en a pas sur ton exemple, ie. il n’y a pas de zone enclavée par 3 autres zones — d’où ma question sur l’origine de tes cartes).

En bref : c’est pas clair, il est pas impossible que la solution optimale soit quelque part entre 44 et 49, et c’est pas évident à vue d’oeil si telle ou telle heuristique va mieux marcher qu’une autre à cette échelle (donc si jamais t’as les cartes sous un format plus lisible, pour tester…). D’ailleurs d’où vient l’exemple de résultat que tu donnes ? Ça ressemble pas vraiment à ce que tu obtiendrais typiquement avec une stratégie de tirage aléatoire.

Dans la lignée des bornes inf, un truc à tester : prendre un grand ensemble indépendant entre 1 et 30, un grand ensemble indépendant dans ce qui reste entre 31 et 60 puis choisir un ordre sur ces deux ensembles pour maximiser ce qu’on peut faire dans les temps 61 à 80. Suivant ce qu’on s’autorise en terme de pénibilité de code, on peut avoir des approximations plus ou moins bonnes…

La carte correspond à la zone géographique étudiée avec des "parquets" délimités. Elle présente l’état en 2020, ou après 3 tirage si on oublie les années sans tirage. Les zones 16, 29 et 24 ont été selectionnées, du coup les zones hachurées ne peuvent plus être sélectionnées pour une période de 30 ans. Lez zones 40 et 37 présentes sur la carte sont en réserve et donc non cincernées par l’étude.

Je présente un cas précis mais effectivement le problème est plus général. La temporalité est importante 80 ans car à partir d’un certain nombre de tirage, il n’y a plus de possibilités les zones ont été selectionnées ou ne peuvent être sélectionnées (contrainte), mais après quelques tirages à vide, des zones redeviennent sélectionnables, la contrainte disparaissant.

Je n’ai pas bien compris l’histoire du coloriage, les couleurs sur la carte ne sont qu’une visualisation du tirage finale de la liste à une certaine date (2020).

Voici comme a été généré le resultat exemple : [16,"","",29,"",24,3,"","","",44,27,13,15,25,47,34,38,14,49,"","","","","","","","","","","",10,"",7,21,"",33,4,11,23,"",35,51,"",8,20,45,26,32,30,48,"","","","","","","","","","","","","","",28,"",31,6,2,18,5,43,52,50,12,9,36,22,39]

année 2015 : tirage de la zone 16 paramétre fixé par le gestionnaire - les polygones 11, 17, 26, 22, 10 et 5 sont bloqués jusqu’à 2045 année 2016 : pas de tirage - fixé par le gestionnaire année 2017 : pas de tirage - fixé par le gestionnaire année 2018 : tirage de la zone 29 paramétre fixé par le gestionnaire - les polygones 21, 36, 35, 39, 30 sont bloqués jusqu’à 2048 année 2019 : tirage de la zone 24 paramétre fixé par le gestionnaire - les polygones 33, 19, 23, sont bloqués jusqu’à 2049 année 2020 : tirage de la zone 3 - les polygones 2, 4, 11,5, sont bloqués jusqu’à 2050, les zones 11 et 5 impactées par le tirage en 2015 sont de onouveau impactées en 2020 année 2021 : pas de tirage - fixé par le gestionnaire année 2021 : pas de tirage - fixé par le gestionnaire année 2022 : pas de tirage - fixé par le gestionnaire année 2023 : tirage de la zone 44 - les polygones 50, 51,46, 43, 35,36, sont bloqués jusqu’à 2053, année 2024 : tirage de la zone 27 - les polygones 28,17,26, sont bloqués jusqu’à 2054, le polygone 34 n’est pas considéré comme limitrophe, la zone 16 est déjà selectionnée donc n’intervient plus année 2025 : tirage de la zone 13 - les polygones 18, 20, 9, 7, 6, 4, 11, sont bloqués jusqu’à 2054 année 2026 : tirage de la zone 15 - les polygones 31, 8, 19, 20, 9, sont bloqués jusqu’à 2054 année 2027 :seule une des zone parmis les zones suivantes 14, 12, 25, 38, 52, 49, 42, 48, 47, 45, 34, ou 32 peut être sélectionnée en l’occurence la 25 dans l’exemple du résultat. etc …

En espérant avoir été plus clair. L’objectif est d’obtenir le nombre maximum d’entités sélectionnées dans la liste ou les listes résultat et de connaître les différentes listes.

L’image que tu as postée n’est pas visible, mais ce n’est pas trop grave.

Réussir à faire 44 années, avec les contraintes que tu décris, ça paraît une belle performance.

En moyenne, un polygone jouxte combien d’autres polygones. Autrement dit, à chaque étape, on retire temporairement combien de polygones de l’univers ?

Si chaque polygone a 3 ou 4 voisins, alors on a l’impression que 44 étapes, avec un univers de 49 polygones , c’est énorme. Et si chaque polygone a seulement 1 ou 2 voisins, pourquoi pas, ça devient une performance moins surprenante.

Tu dis qu’à chaque étape, tous les voisins du polygone choisi sont 'retirés’ pour 30 ans. J’imagine que le polygone choisi est également retiré pour 30 ans ? Sinon ce serait trop facile.

Si tu peux partager ton fichier avec les 49 lignes (liste des voisins de chaque polygone), cet exercice peut en amuser certains.

Dans ton 2ème message, tu dis que l’année initiale est imposée, mais tu parles également de situations 'imposées par le gestionnaire’.

Par exemple, 2022 : pas de tirage, fixé par le gestionnaire.

Ca veut dire que cette année là est une année blanche ? On ne colorie aucun polygone, On incrémente juste le compteur des années, ce qui fait que la contrainte des 30 ans, c’est en fait une contrainte sur 29 ou 28 'cycles’, c’est ça ?

Auquel cas, si les polygones bloqués se libèrent plus vite que prévus, c’est une bonne nouvelle.

Et donc , dans les données d’entrée du problème, on a

• la carte des polygones (=liste des voisins de chaque polygone)
• le n° des polygones imposés pour certaines années ( 2015=n°16 ; 2018=n°29 ; etc)
• La liste des années où on ne fait rien.

Pour ceux qui cherchent, l’image du post initial est la suivante (obtenue pour une raison que j’ignore via "copy image location" dans l’OP) :

La carte correspond à la zone géographique étudiée avec des "parquets" délimités. Elle présente l’état en 2020, ou après 3 tirage si on oublie les années sans tirage. Les zones 16, 29 et 24 ont été selectionnées, du coup les zones hachurées ne peuvent plus être sélectionnées pour une période de 30 ans. Lez zones 40 et 37 présentes sur la carte sont en réserve et donc non cincernées par l’étude.

J’avais bien compris ça, mais tu essayes de résoudre un problème réel ou c’est des cartes qui te sont données comme ça ? T’as combien de cartes à traiter ? À quel point tu veux faire un truc qui marche bien en général ?

Je n’ai pas bien compris l’histoire du coloriage, les couleurs sur la carte ne sont qu’une visualisation du tirage finale de la liste à une certaine date (2020).

J’ai été peut-être un peu vite, mais en gros tu peux modéliser ton problème avec un graphe, en remplaçant chaque zone par un sommet et en mettant une arête entre deux sommets si les deux zones se touchent. Une question que tu peux poser sur un graphe, c’est "est-ce qu’il est 3-coloriable ?", à savoir est-ce qu’on peut colorier chacun des sommets en rouge, bleu et vert de telle manière que 2 sommets adjacents ne soient jamais de même couleur. Ce que j’ai fait remarquer plus haut, c’est que SI tu as une solution à ton problème qui fait intervenir TOUTES les zones, alors le graphe est 3-coloriable (on n’a pas de contradiction ici, c’est juste une remarque avec les mains pour préciser pourquoi je pense que c’est un problème difficile en général).

J’avais bien compris ça aussi mais comment tu as généré cette solution ? Elle me paraît plutôt bonne par rapport à ce que tu obtiendrais avec ton algo.

Merci et super si le sujet peut interesser quelques personnes Et oui c’est un cas réel, la carte représente bien les zones définies sur le terrain.

Pour l’instant c’est un test et si on arrive à sortir quelque chose d’interessant on généralisera certainement la méthode.

Info : Il semble qu’il fasse faire un clic droit pour ouvrir le plan proposé.

Quelques compléments une fois un polygone selectionné il ne peut plus être selectionnés (ou dans 180 ans !!) Les contraintes imposées sont les suivantes :

• passage 2015 = 16, 2018 = 29, 2020 = 24
• passage entre 2021 et 2026 : uniquement les zones 27, 3 et 44
• entre 2027 et 2036 : les zones 13, 20 et 14
• pour les zones limitrophes des zones 13,20 et 14 la période de blocage n’est pas de 30 ans mais de 17 ans quand ouvre , sélectionne, les zones 13, 20 ou 14; précision : par exemple la zone 25 est bloquée pour 30 ans si on ouvre le polygone 30 mais seulement pour 17 an si on selectionne la zone 20.
• Il y a forcément blocage entre les zones 13 et 20 car limitrophes, de fait il faut donc selectionner une des deux en 2027 et faire en sorte qu’en 2044 on selectionne l’autre.
• les années sans selection peuvent être considérées comme un cycle en moins mais elle ont tout de même leur importance car l’année d’ouverture, de selection finale est importante.

Et oui je rajoute un peu de piment !!

Avec toutes ces contraintes mon script a tourné durant 30 h (je n’ai pas une bête de course), testé 900 000 listes possibles pour obtenir 200 cas avec 44 zones sur 49 et pour 80 ans.

Voici la liste des polygones limitrophes : https://3hg.fr/CHATONS/Pastebin/?556f7b5983bf4fe0#3V9MN5edJoosi1qA89mBTAhs2RHquKWkhakcpopkSdju

Quand on sélectionne les zones 13, 14 ou 20, la période de blocage des zones voisines est de 17 ans, au lieu de 30. Ok.

Mais si je sélectionne une zone voisine de la 14 en 2028 par exemple, je dois attendre 17 ans, ou bien 30 ans, pour pouvoir sélectionner la zone 14 ?

Pour les zones 13 et 20, on a 2 infos contradictoires. D’une part on dit que ces zones doivent être sélectionnées en 2027 pour l’une et 2044 pour l’autre (13 puis 20, ou 20 puis 13) ; mais d’autre part on dit que les zonnes 13 et 20 (et 14 également) doivent être sélectionnées entre 2027 et 2036. C’est contradictoire.

Dernier point : puisqu’une zone sélectionnée ne peut plus l’être avant 180 ans, et qu’on a (beaucoup) moins de 180 zones, de toutes façons on ne pourra pas sélectionner 2 fois la même zone.

Au mieux, on aura donc un process de 49 ans (plus les quelques années blanches). La durée de 80 ans qu’on a quelque part ne correspond à rien.

Il faudrait en effet clarifier les règles qui limites certaines zones à certaines années. En disant entre 2027 et 2036 : les zones 13, 20 et 14, est-ce que ça veux dire que seul ces zones-là peuvent être sélectionnés durant cette période (mais qu’elles peuvent être sélectionnés à d’autres années aussi)? Est-ce que ça veux dire qu’elles ne peuvent être sélectionnés que durant cette période, mais que d’autres zones peuvent aussi être sélectionnés durant cette période? Un combinaison des deux? Pareil pour 2021–2026 avec [27, 3, 44].

Pour l’instant, j’ai juste testé du brute force (générer 10000 listes aléatoires de manière gourmande) et regarder combien des zones ont étés sélectionnés.

Sans limiter certaines zone à certaines années, j’arrive facilement à 46 zones en 80 ans:

16, None, None, 29, None, 24, 48, 3, 52, 15, 14, 42, 44, 34, 13, 38, 27, 25, 45, None, None, None, None, None, None, None, None, 12, None, None, 10, 6, None, 21, None, 33, None, 2, 11, 49, 9, None, 51, 43, 32, 39, 26, 20, 47, None, None, None, None, None, None, None, None, 23, None, None, None, None, None, 28, None, 19, None, 4, 17, 5, 8, 7, 50, 46, None, 30, 22, 35, 36, None

En supposant que les limitations d’années-zones veulent dire qu’on ne peut sélectionner que ces zones durant la période (mais qu’on peut les sélectionner à d’autre moment aussi), j’arrive à 40 zones:

16, None, None, 29, None, 24, 44, 27, 3, None, None, None, 13, 14, None, None, None, None, None, None, None, None, 49, 45, 15, 34, 42, 38, 25, 7, 10, 12, None, 21, None, 33, 51, None, 4, 11, None, None, None, None, None, None, None, None, None, None, None, None, 48, None, None, 32, 26, 35, 30, 20, 9, 23, None, 28, 36, 19, 50, 52, 2, 18, 5, 6, None, None, None, None, None, None, None, None

En supposant que les limitations d’années-zones veulent dire qu’on ne peut sélectionner ces zones que durant la période (mais qu’on peut sélectionner d’autres zones aussi durant la période), j’arrive à 45 zones:

16, None, None, 29, None, 24, 38, 44, 3, 49, 18, 27, 34, 42, 45, 7, 14, 8, 20, None, None, None, None, None, None, None, None, None, None, None, 22, None, None, None, None, 23, 31, 30, 5, 4, 46, 50, 28, 48, 17, 35, 32, 36, 9, None, None, None, None, None, None, None, None, None, None, None, 26, None, None, None, None, 12, None, 25, 10, 2, 6, 52, 33, None, 11, 39, 43, 21, 15, 47

En supposant que les limitations d’années-zones veulent dire qu’on ne peut sélectionner ces zone que durant la période et que seules ces zones peuvent être sélectionnés durant la période, j’arrive à 39 zones:

16, None, None, 29, None, 24, 3, 44, 27, None, None, None, 14, 20, None, None, None, None, None, None, None, None, 45, 49, 7, 32, 18, 38, 42, 12, 10, 15, None, None, None, 33, 4, 51, 26, 28, None, None, None, None, None, None, None, None, None, None, None, None, None, 48, None, None, 17, 25, 43, 36, 39, 5, 23, 8, None, 19, 2, 50, 52, 22, 34, 6, None, None, None, None, None, None, None, None

Au pifomètre, je dirais qu’il n’est pas possible d’explorer de manière exhaustive l’espace des possibilités car ça prendrait trop de temps. En revanche, il est possible de calculer rapidement (et relativement facilement) certaines choses qui pourraient être utile pour construire des heuristiques. Par exemple, si on pouvait sélectionner plusieurs zone pour la même année, il est possible de calculer le nombre maximum de zones qui peuvent être sélectionnés en même temps (en respectant toutes les autres règles). Typiquement, c’est le genre de chose qui permet d’orienter le choix vers des zones qui vont moins bloquer les choix future.

Voici les précisions demandées :

• 2021–2026 on ne peut choisir que ces 3 zones 27, 3 et 44, il y a donc des années blanches, l’ordre de passage est libre, les années blanches pas fixées. Il y a 120 permutations possibles.
• 2027–2036 il faudrait passer les zones 13, 14 et 20 mais au vu des contraintes imposées au polygones limitrophes il y a impossibilité entre les zones 13 et 20. Du coup cela contraint à choisir la zone 13 ou 20 en 2027 (le plus tôt possible), et respectivement la 20 ou 13 en 2044 17 ans plus tard; on fait au mieux !!
• C’est le type de parquet ouvert qui impose le délais pour les parquets limitrophes, le temps que la végétation repousse et ait attend une certaine hauteur. Du coup l’ouverture du parquet 14 bloque les parquets 12 et 23 pour 17 ans , mais l’ouverture du parquets 12 bloque les parquets limitrophes dont le 14 pour 30 ans.

Je ne connais pas les heuristiques mais la solution pourrait m’interesser.

Au vu de vos retours avec 44 zones sélectionnées je ne dois pas être trop mauvais. Il est effectivement impossible de traiter tous les cas !

On peut de toutes façons voir qu’on ne trouvera pas de chemin avec les 49 zoones.

Si on regarde le triplet (31,32,34), ces 3 zones se touchent 2 à 2. Et donc elles seront planifiées au mieux en année a,a+30 et a+60. Idem, les zones 46, 51 et 52, qui seront planifiées en années a+1, a+31, a+61. Même chose pour 17,18 et 21, qui seront planifiées en a+2, a+32, a+62.

Même chose pour 36,40 et 45

Même chose pour 35, 42 et 43

Même chose pour 30, 38 et 39

Ei il y en a probablement d’autres.

Sauf erreur, j’en suis à 6 triplets disjoints ; pour chacun de ces 6 triplets, on ne pourra traiter que 2 zones sur 3. Et donc, on ne pourra traiter que 43 zones sur 49.

Peut-être que j’ai mal lu les numéros sur la carte, ou alors il y a une 'restriction de contrainte' que je n’ai pas vue. Parce que, si je ne me suis pas trompé, on ne peut pas arriver à une solution avec 44 zones.