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

How to re-order units based on their degree of desirable neighborhood ? (in Processing)

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

上下文

引用 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/"Each space is associated with a list that contains all other spaces sorted according to their degree of desirable neighborhood."

2/"Then each unit of each space is selected from the list and then one-by-one placed randomly in the site until they fit in the site and the neighboring conditions are met. (If it fails then the process is repeated)"

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

我要补充一点，作者稍后会解释这个算法不依赖于暴力破解技术。

问题

如您所见，解释相对含糊，步骤 2 相当不清楚（在编码方面）。到目前为止我只有 "pieces of a puzzle":

每个单元：

如果有人能帮我解释一下，我将不胜感激：

编辑

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

粗略地说，它会翻译成这样：

    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 个解决方案。他们每个人都会有一个基于邻居亲和力的分数。

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

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

  • 网格中的起点
  • 就职

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

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

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

放置完每一个办公楼后，还需要统一随机选择：下一个要放置的办公楼。

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

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.

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

所以基本上，办公室选择遵循均匀分布，然后，加权扩展过程发生在 selected 办公室。

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

  • 没有必要在网格中放置一个新办公室（都有affinity = 0）
  • Office 无法扩展，因为所有亲和力权重都等于 0

那么该尝试无效，应该放弃并转向全新的随机尝试。

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

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

抱歉，这里只有算法，没有代码。

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

希望对您有所帮助。

我相信 Kostas Terzidis 教授会是一位出色的计算机理论研究人员，但他的算法解释根本无济于事。

首先，邻接矩阵没有任何意义。在你说的问题评论中：

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

但 m[i][i] = 0，这意味着同一 "office" 的人更喜欢其他办公室作为邻居。这与您的预期完全相反，不是吗？我建议改用这个矩阵：

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 的矩阵索引，但它要与邻接矩阵保持一致。）

With 1 <= x <= 5 and 1 <= y <= 7:

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

第 2 步：对解决方案进行评分

对于所有个地方p[x][y]，使用邻接矩阵计算得分。例如，第一名1有2和4为邻居，所以得分为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

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

一些笔记

  • 请注意，鉴于在迭代的某个时刻您将无法交换 2 个位置并获得更好的分数，因此算法将始终最终确定。
  • 在一个有 N 个位置的矩阵中，有 N x (N-1) 个可能的交换，并且可以通过有效的方式完成（因此，不需要蛮力）。

希望对您有所帮助！