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

我需要帮助来实现一种允许生成建筑计划的算法，这是我最近在阅读 Kostas Terzidis 教授的最新出版物时偶然发现的： (2014).

CONTEXT

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

引用 Terzidis 教授的话：

“解决这个问题的一种方法是在网格内随机放置空间，直到所有空间都适合并且满足约束”

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

算法（如书中简要描述）

1/“每个空间都与一个列表相关联，该列表包含根据其所需邻域程度排序的所有其他空间。”

2/“然后从列表中选择每个空间的每个单元，然后将它们一一随机放置在场地中，直到它们适合场地并且满足邻近条件。（如果失败则重复该过程）”

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

我应该补充一点，作者后来解释说该算法不依赖于暴力技术.

PROBLEMS

正如你所看到的，解释相对模糊并且step 2相当不清楚（就编码而言）。到目前为止我所拥有的只是“拼图的碎片”：

• 一个“站点”（选定整数的列表）
• 邻接矩阵（嵌套列表）
• “spaces”（列表词典）

对于每个单元：

• 返回其直接邻居的函数
• 其所需邻居的列表及其按排序顺序的索引

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

  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
  

如果有人能帮助连接这些点并解释我，我将非常感激：

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

EDIT

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

• 我们事先检查它的直接邻居（上、下、左、右）
• 如果至少有 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 次迭代要多得多。

问题：

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

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

我会打电话给'attempt' 来完整运行，试图找到有效的植物分布。完整的脚本运行将包括N尝试。

每次尝试都从 2 个随机（统一）选择开始：

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

一旦定义了一个点和一个办公室，就会出现“扩张过程'试图将所有办公大楼纳入网格中。

每个新块都是根据他的程序设置的：

• 第一。计算每个相邻单元格与办公室的亲和力。
• 第二。随机选择一个站点。选择应该根据亲和力来衡量。

每个办公大楼放置完毕后，需要进行另一个统一的随机选择：下一个要放置的办公室。

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

0亲和办公室不添加。概率因数应该是0对于网格中的那个点。亲和函数选择是这个问题的一个有趣的部分。您可以尝试使用相邻单元格因子的加法甚至乘法。

扩建过程再次进行，直到办公室的每一块都被放置完毕。

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

尝试什么时候结束？, If:

• 在网格中放置新办公室是没有意义的（所有办公室都有affinity = 0)
• Office 无法扩展，因为所有关联权重都等于 0

那么该尝试无效，应被丢弃并转移到全新的随机尝试。

否则，如果所有块都适合：它是有效的。

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

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

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

希望能帮助到你。