如何根据单元的期望邻域度重新排序？（正在处理中）

Question

我需要帮助来实现一个允许生成建筑平面图的算法，这是我最近在阅读Kostas Terzidis教授的最新出版物：Permutation Design: Buildings, Texts and Contexts（2014）时偶然发现的。在

上下文

• 考虑一个被划分为网格系统（a）的站点（b）。在
• 让我们也考虑一个空间列表，在场地的限制（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+邻居的权重之和）
• 最后，如果邻接概率很高的话，就把这个单元放进去

大致可以理解为：

^{pr2}$

考虑到大部分单元不会在第一次运行时放置（因为相邻概率很低），我们需要反复迭代，直到找到所有单元都可以拟合的随机分布。在

经过几千次迭代后，找到了一个合适的，并且所有相邻的需求都得到了满足。在

但是注意这个算法是如何产生分离的组而不是像所提供的示例中那样的非分割和统一的堆栈。我还应该补充说，近5000次迭代远远超过了Terzidis先生在他的书中提到的274次迭代。在

问题：

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

Answer 1

我相信Kostas Terzidis教授将是一个优秀的计算机理论研究者，但他的算法解释一点帮助也没有。在

首先，邻接矩阵没有意义。你在提问中说：

"the higher that value is, the higher the probability that the two spaces are adjecent is"

但是m[i][i] = 0，这意味着在同一个“办公室”的人更喜欢其他办公室作为邻居。你所期望的恰恰相反，不是吗？我建议改用这个矩阵：

With 1 <= i, j <= 5:

              +        +
              | 10  6  1  5  2 |
              |    10  1  4  0 |
    m[i][j] = |       10  8  0 |  
              |          10  3 |
              |             10 |
              +        +

有了这个矩阵

• 最高值是10。所以m[i][i] = 10正是你想要的：同一个办公室的人应该在一起。在
• 最小值为0。（根本不应该有任何联系的人）

算法

第1步：开始随机放置所有位置

（很抱歉基于1的矩阵索引，但它必须与邻接矩阵一致。）

^{pr2}$

第2步：给解决方案打分

对于所有位p[x][y]，使用邻接矩阵计算分数。例如，第一位1有2和{}作为邻居，因此得分为11：

score(p[1][3]) = m[1][2] + m[1][4] = 11

所有个人得分之和即为解决方案得分。在

第3步：通过交换位置来优化当前解决方案

对于每对位置p[x1][y1], p[x2][y2]，交换它们并再次评估解决方案，如果得分更好，则保留新的解决方案。在任何情况下，重复第3步，直到任何排列都不能改善解决方案。在

例如，如果将p[1][4]与p[2][1]交换：

            +          -+
            | -  -  1  1  1  4  3 |
            | 2  2  4  5  1  4  3 |
  p[x][y] = | 2  4  2  4  3  2  4 |
            | -  -  -  -  3  2  4 |
            | -  -  -  -  5  3  3 |
            +          -+

您将找到一个得分更高的解决方案：

交换前

score(p[1][3]) = m[1][2] + m[1][4] = 11
score(p[2][1]) = m[1][2] + m[1][2] = 12

交换后

score(p[1][3]) = m[1][1] + m[1][4] = 15
score(p[2][1]) = m[2][2] + m[2][2] = 20

所以保留它，继续交换位置。在

一些注意事项

• 请注意，如果在迭代的某一点上，您无法交换两个位置并获得更好的分数，那么算法将始终最终确定。在
• 在含有N个位置的矩阵中，存在N x (N-1)个可能的交换，并且可以以一种有效的方式完成（因此，不需要暴力）。在

希望有帮助！在

Answer 2

我提出的解决这个问题的方法是在记录有效解的同时重复算法几次。由于解不是唯一的，我希望算法抛出多个解。邻居们的亲和力是基于他们的亲和力。在

我将调用一个“尝试”来完成整个运行，试图找到一个有效的工厂分布。完整脚本运行将包含N次尝试。在

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

• 网格起点
• 启动办公室

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

每一个新的区块都按照他的程序设置：

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

在每一个办公区被放置之后，还需要另一个统一的随机选择：下一个要放置的办公室。在

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

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

则尝试无效，应将其降级为全新的随机尝试。在

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

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

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

注意：我相信亲和力计算过程可以改进，甚至可以尝试使用一些不同的方法。这只是一个帮助你得到解决方案的想法。在

希望有帮助。在