python - 如何根据理想邻域的程度重新排序单元？ (进行中)

Question

我需要帮助来实现允许生成建筑计划的算法，这是我最近在阅读 Kostas Terzidis 教授的最新出版物时偶然发现的:Permutation Design: Buildings, Texts and Contexts (2014 年)。

上下文

• 考虑一个分为网格系统 (a) 的站点 (b)。
• 我们还要考虑一个要放置在 field 范围内的空间列表 (c) 和一个邻接矩阵，以确定这些空间的放置条件和相邻关系 (d)

引用 Terzidis 教授的话:

"A way of solving this problem is to stochastically place spaces within the grid until all spaces are fit and the constraints are satisfied"

上图显示了这样一个问题和一个示例解决方案(f)。

算法(如书中简要描述)

1/"每个空间都与一个列表相关联，该列表包含所有其他空间，这些空间根据它们的理想邻域程度排序。"

2/"然后从列表中选择每个空间的每个单元，然后一个一个地随机放置在站点中，直到它们适合站点并且满足相邻条件。(如果失败则该过程是重复)”

九个随机生成的计划示例:

我应该补充一点，作者稍后解释说此算法不依赖于蛮力技术。

问题

如您所见，解释相对模糊，第 2 步 也不清楚(就编码而言)。到目前为止，我只有“拼图”:

• 一个“站点”(选定整数的列表)
• 邻接矩阵(嵌套列表)
• “空格”(列表字典)

每个单元:

• 一个返回其直接邻居的函数
• 其理想邻居的列表及其按排序顺序排列的索引

• 基于其实际邻居的适应度得分

  from random import shuffle
  
  n_col, n_row = 7, 5
  to_skip = [0, 1, 21, 22, 23, 24, 28, 29, 30, 31]
  site = [i for i in range(n_col * n_row) if i not in to_skip]
  fitness, grid = [[None if i in to_skip else [] for i in range(n_col * n_row)] for e in range(2)]
  
  n = 2
  k = (n_col * n_row) - len(to_skip)
  rsize = 50
  
  #Adjacency matrix
  adm = [[0, 6, 1, 5, 2],
         [6, 0, 1, 4, 0],
         [1, 1, 0, 8, 0],
         [5, 4, 8, 0, 3],
         [2, 0, 0, 3, 0]]
  
  
  spaces = {"office1": [0 for i in range(4)], 
            "office2": [1 for i in range(6)], 
            "office3": [2 for i in range(6)],
            "passage": [3 for i in range(7)],
            "entry": [4 for i in range(2)]}
  
  
  def setup():
      global grid
      size(600, 400, P2D)
      rectMode(CENTER)
      strokeWeight(1.4)
  
      #Shuffle the order for the random placing to come
      shuffle(site)
  
      #Place units randomly within the limits of the site
      i = -1   
      for space in spaces.items():
          for unit in space[1]:    
              i+=1
              grid[site[i]] = unit
  
  
      #For each unit of each space... 
      i = -1   
      for space in spaces.items():
          for unit in space[1]:    
              i+=1
  
              #Get the indices of the its DESIRABLE neighbors in sorted order
              ada = adm[unit]
              sorted_indices = sorted(range(len(ada)), key = ada.__getitem__)[::-1]
  
              #Select indices with positive weight (exluding 0-weight indices)
              pindices = [e for e in sorted_indices if ada[e] > 0] 
  
              #Stores its fitness score (sum of the weight of its REAL neighbors)
              fitness[site[i]] = sum([ada[n] for n in getNeighbors(i) if n in pindices])
  
      print 'Fitness Score:', fitness
  
  def draw():
      background(255)
  
      #Grid's background
      fill(170)
      noStroke()
      rect(width/2 - (rsize/2) , height/2 + rsize/2 + n_row , rsize*n_col, rsize*n_row)
  
  
      #Displaying site (grid cells of all selected units) + units placed randomly
      for i, e in enumerate(grid):
          if isinstance(e, list): pass
          elif e == None: pass
          else:
              fill(50 + (e * 50), 255 - (e * 80), 255 - (e * 50), 180)
              rect(width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(i+1))/n_col * rsize), rsize, rsize)
              fill(0)
              text(e+1, width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(i+1))/n_col * rsize))
  
  
  
  
  def getNeighbors(i):
      neighbors = []
  
      if site[i] > n_col and site[i] < len(grid) - n_col:
          if site[i]%n_col > 0 and site[i]%n_col < n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col]) 
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
      if site[i] <= n_col:
          if site[i]%n_col > 0 and site[i]%n_col < n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
          if site[i]%n_col == 0:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
          if site[i] == n_col-1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
      if site[i] >= len(grid) - n_col:
          if site[i]%n_col > 0 and site[i]%n_col < n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
          if site[i]%n_col == 0:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
          if site[i]%n_col == n_col-1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      if site[i]%n_col == 0:
          if site[i] > n_col and site[i] < len(grid) - n_col:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      if site[i]%n_col == n_col - 1:
          if site[i] > n_col and site[i] < len(grid) - n_col:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      return neighbors
  

如果有人可以帮助连接点并解释我，我将非常感激:

• 如何根据理想的邻里程度对单元进行重新排序？

编辑

正如你们中的一些人所注意到的，该算法基于某些空间(由单元组成)相邻的可能性。逻辑上是每个单元随机放置在站点范围内:

• 我们事先检查它的直接邻居(上、下、左、右)
• 如果至少有 2 个邻居，则计算适应度分数。 (=这 2 个以上邻居的权重之和)
• 如果邻接概率很高，最后放置该单元

大概会这样翻译:

    i = -1   
    for space in spaces.items():
        for unit in space[1]:    
            i+=1

            #Get the indices of the its DESIRABLE neighbors (from the adjacency matrix 'adm') in sorted order
            weights = adm[unit]
            sorted_indices = sorted(range(len(weights)), key = weights.__getitem__)[::-1]

            #Select indices with positive weight (exluding 0-weight indices)
            pindices = [e for e in sorted_indices if weights[e] > 0] 


            #If random grid cell is empty
            if not grid[site[i]]:

                #List of neighbors
                neighbors = [n for n in getNeighbors(i) if isinstance(n, int)]

                #If no neighbors -> place unit
                if len(neighbors) == 0:
                    grid[site[i]] = unit 

                #If at least 1 of the neighbors == unit: -> place unit (facilitate grouping)
                if len(neighbors) > 0 and unit in neighbors:
                    grid[site[i]] = unit  

                #If 2 or 3 neighbors, compute fitness score and place unit if probability is high
                if len(neighbors) >= 2 and len(neighbors) < 4:

                    fscore = sum([weights[n] for n in neighbors if n in pindices]) #cumulative weight of its ACTUAL neighbors
                    count = [1 for t in range(10) if random(sum(weights)) < fscore] #add 1 if fscore higher than a number taken at random between 0 and the cumulative weight of its DESIRABLE neighbors

                    if len(count) > 5: 
                        grid[site[i]] = unit

                #If 4 neighbors and high probability, 1 of them must belong to the same space
                if len(neighbors) > 3:

                    fscore = sum([weights[n] for n in neighbors if n in pindices]) #cumulative weight of its ACTUAL neighbors                    
                    count = [1 for t in range(10) if random(sum(weights)) < fscore] #add 1 if fscore higher than a number taken at random between 0 and the cumulative weight of its DESIRABLE neighbors

                    if len(count) > 5 and unit in neighbors:                       
                        grid[site[i]] = unit


            #if random grid cell not empty -> pass
            else: pass

鉴于大部分单元不会在第一次运行时放置(因为邻接概率低)，我们需要一遍又一遍地迭代，直到找到可以拟合所有单元的随机分布。

经过几千次迭代后，找到了合适的并满足了所有相邻要求。

但请注意，此算法如何生成分离的组，而不是像提供的示例中那样生成非分割和统一的堆栈。我还应该补充一点，近 5000 次迭代比 Terzidis 先生在他的书中提到的 274 次迭代要多得多。

问题:

• 我处理这个算法的方式有问题吗？
• 如果没有，那么我缺少什么隐含条件？

Answer 1

我为解决这一挑战而提出的解决方案是基于多次重复该算法，同时记录有效的解决方案。由于解决方案不是唯一的，我希望算法会抛出超过 1 个解决方案。他们每个人都会有一个基于邻居亲和力的分数。

我将调用一次“尝试”来完整运行以尝试找到有效的植物分布。完整的脚本运行将包含 N 次尝试。

每次尝试以 2 个随机(统一)选择开始:

• 网格中的起点
• 开始办公室

一旦定义了一个点和一个办公室，它就会出现一个“扩展过程”，试图将所有的办公大楼都放入网格中。

每个新 block 都按照他的程序设置:

• 第一。计算每个相邻单元与办公室的亲和性。
• 第二。随机选择一个站点。选择应该由亲和力加权。

每一个办公大楼都放好后，需要另一个统一的随机选择:下一个要放置的办公室。

一旦选定，您应该再次计算每个站点的亲和度，并随机(加权)选择新办公室的起点。

0 affinity offices don't add. Probability factor should be 0 for that point in the grid. Affinity function selection is an iteresting part of this problem. You could try with the addition or even the multiplication of adjacent cells factor.

扩展过程再次参与，直到办公室的每个街区都被放置。

所以基本上，办公室挑选遵循均匀分布，然后，针对选定办公室进行加权扩展过程。

尝试什么时候结束？,如果:

• 没有必要在网格中放置一个新办公室(都具有 affinity = 0)
• Office 无法扩展，因为所有关联权重都等于 0

那么尝试无效，应该被丢弃，转而进行全新的随机尝试。

否则，如果所有 block 都适合:它是有效的。

关键是办公室应该团结在一起。这是算法的关键点，它会根据亲和力随机尝试适合每个新办公室，但仍然是一个随机过程。如果条件不满足(无效)，随机过程再次开始，选择一个新的随机网格点和办公室。

抱歉，这里只有一个算法，但没有任何代码。

注意:我确信亲和力计算过程可以改进，甚至您可以尝试一些不同的方法。这只是一个帮助您获得解决方案的想法。

希望对你有帮助。