Bonjour,
D'abord merci à l'avance a quiconque contribuera à ce que j'en arrive à règler mon problème.
J'ai passé beaucoup de temps à fouiller les forums et par extension, me retrouver à lire et tenter de comprendre un tant soit peu, un paquet de choses sur des problèmes NP-complet, divers algorithmes (Dijkstra, Lin-Kernigan, le cycle hamiltonien, le problème du voyageur de commerce, le problème du postier chinois, etc. ). Au final, je n'ai pas de solution à mon "problème", probablement du fait qu'il est toujours diffèrents en quelques sortes par rapport à la lecture que je fait.
Par exemple, le cas du voyageur de commerce m'apparait un fort bonne piste, mais dans mon cas il y a notamment la différence que je n'ai pas a organiser mon ittinéraire en considérant devoir revenir au point d'origine (ce qui devrait devrait avoir l'avantage d'être moins complexe...).
Voilà un fichier exposant où j'en suis :
Le but :
Créer des regroupements de lieux.
Les"consignes" que je dois respecter :
Je dois arriver a ralier tous les lieux identifiés (désigné par la lattitude (colonne H) et la longitude(colonne I)).
Je dois débuter par le lieux situé le plus au nord-est (désigné par la valeur la plus faible sur l'axe des X (colonne H) et la plus élevé sur l'axe des Y (colonne I)).
Je dois progresser en passant chaque fois par le lieux le plus près (distance à vol d'oiseau).
Je connais la population de chaque lieu (colonne L).
Chaque fois que le cumul de la population des lieux raliers dépasse 15 000 habitants, je dois créer un code (ex. : Regroup1; Regroup2, etc.) qui désigne les lieux inclut dans le regroupement et l'indiquer dans la colonne M.
Je débute ensuite un nouveau regroupement avec le lieux le plus près du dernier lieux inclut dans le regroupement précédent.
Autre petites contrainte : les regroupements ne doivent pas compter plus de 16 000 habitants, donc même si je n'ai pas atteint 15000 habitants dans un regroupement, je ferme ce regroupement plutot que de lui ajouter un lieu qui ferait passé sa population a plus de 16 000 habitants.
D'abord merci à l'avance a quiconque contribuera à ce que j'en arrive à règler mon problème.
J'ai passé beaucoup de temps à fouiller les forums et par extension, me retrouver à lire et tenter de comprendre un tant soit peu, un paquet de choses sur des problèmes NP-complet, divers algorithmes (Dijkstra, Lin-Kernigan, le cycle hamiltonien, le problème du voyageur de commerce, le problème du postier chinois, etc. ). Au final, je n'ai pas de solution à mon "problème", probablement du fait qu'il est toujours diffèrents en quelques sortes par rapport à la lecture que je fait.
Par exemple, le cas du voyageur de commerce m'apparait un fort bonne piste, mais dans mon cas il y a notamment la différence que je n'ai pas a organiser mon ittinéraire en considérant devoir revenir au point d'origine (ce qui devrait devrait avoir l'avantage d'être moins complexe...).
Voilà un fichier exposant où j'en suis :
Le but :
Créer des regroupements de lieux.
Les"consignes" que je dois respecter :
Je dois arriver a ralier tous les lieux identifiés (désigné par la lattitude (colonne H) et la longitude(colonne I)).
Je dois débuter par le lieux situé le plus au nord-est (désigné par la valeur la plus faible sur l'axe des X (colonne H) et la plus élevé sur l'axe des Y (colonne I)).
Je dois progresser en passant chaque fois par le lieux le plus près (distance à vol d'oiseau).
Je connais la population de chaque lieu (colonne L).
Chaque fois que le cumul de la population des lieux raliers dépasse 15 000 habitants, je dois créer un code (ex. : Regroup1; Regroup2, etc.) qui désigne les lieux inclut dans le regroupement et l'indiquer dans la colonne M.
Je débute ensuite un nouveau regroupement avec le lieux le plus près du dernier lieux inclut dans le regroupement précédent.
Autre petites contrainte : les regroupements ne doivent pas compter plus de 16 000 habitants, donc même si je n'ai pas atteint 15000 habitants dans un regroupement, je ferme ce regroupement plutot que de lui ajouter un lieu qui ferait passé sa population a plus de 16 000 habitants.
