J'ai besoin de générer des instances aléatoires de la carteproblème de coloration en python pour implémenter un résolveur min-conflit. Je devrais suivre cette stratégie: disperser n points sur la case de l’unité; sélectionnez un point X au hasard, connectez X par un segment de ligne au point Y le plus proche de telle sorte que X ne soit pas déjà connecté à Y et que le segment ne croise aucun autre segment (voir, par exemple, comment tester l'intersection segment-segment); Répétez l'étape précédente jusqu'à ce qu'il n'y ait plus de connexions possibles. Les points représentent les régions sur la carte et les lignes connectent les voisins. Je ne sais même pas comment commencer.
Réponses:
0 pour la réponse № 1Quelque chose pour vous pour commencer, prenez ce cours:
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.neighbours = set()
def is_neighbour(node: Node):
return node in self.neighbours
def connect(node: Node):
self.neighbours.add(node)
node.neighbours.add(self)
def distance(node: Node):
return ((self.x - node.x)**2 + (self.y - node.y)**2)**0.5
La partie la plus difficile sera de détecter si la connexion entre les points que vous "essayez de faire" ne sera pas croisée avec une autre connexion, mais je vous la laisserai.