Bonjour à tous,
 
J'ai un problème d'algo que je n'arrive vraiment pas à résoudre en vu d'une implémentation.
 
 
Alors voilà: j'ai une carte (une ville) contenant n intersections. Je voudrais diviser cette carte en cellules (m) de sort qu'il y est le même nombre de n par m. Je n'ai vraiment aucune idée par où commencer. Quel serait l'algo idéal pour arriver à segmenter cette carte. Les recherches google ne retourne absolument rien.
Des idées?

ca sent le graphe ça. En gros tu as un graphe de n sommet que tu veut partitionner en m sous-graphes tel que qqsoit i, Card(Mi) = k, k cste.
 
Mon oreillette me dit : http://en.wikipedia.org/wiki/Graph_partition
et que c'est NP-complet. Mais, apparemment y a des heuristiques pas dégeu qui existe. Essaye de google 'partitionnement de graphe' pour voir.

Ah j'ai pas pensé aux graphes!
 
Merci beaucoup pour cette piste