python中地圖着色的隨機實例

我需要在python中生成隨機地圖着色問題實例來實現最小衝突求解器。我應該遵循這個策略：在單位正方形上分散n個點;隨機選擇一個點X，通過一條線段將X連接到最近的點Y，使得X尚未連接到Y，並且該線段不與其它線段交叉（例如，請參閱此處如何測試線段交叉點）。重複上一步直到不再有可能的連接。這些點表示地圖上的區域，並且這些線路將鄰居連接起來。我甚至不知道如何開始。python中地圖着色的隨機實例

來源

2016-02-10 canaio

從一段代碼開始，這段代碼將在一個正方形上選擇你的'n'點，如果你至少知道Python的基本知識，這應該不難。接下來，編寫三個函數：段分段交叉檢查器，距離計算器，給定X的函數返回Y最接近X並且未連接到X的Y，並且可以按照規則進行連接。如果您遇到任何這些功能的問題，請提供另一個提供更多詳細信息並顯示您嘗試的內容的問題。 – Maciek

我正在努力的事情是如何代表廣場。二維列表太天真了嗎？ – canaio

這取決於「平方單位」有多大，以及您要從中選擇多少點。我會親自跳過整個「字段」的表示，只保留圖形節點作爲具有座標的對象。然後使用字典詞典快速訪問它們或其他方便的收藏。 – Maciek

東西給你啓動，藉此類：

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

最難的部分將被檢測點是否你試圖讓不會與其他連接交叉，但我會之間的連接留給你。

來源

2016-02-10 14:02:59 Maciek

python中地圖着色的隨機實例

回答

相關問題