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

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

回答此问题可获得 20 贡献值，回答如果被采纳可获得 50 分。

我需要帮助来实现一个允许生成建筑平面图的算法，这是我最近在阅读Kostas Terzidis教授的最新出版物：<a href="https://books.google.com/books/about/Permutation_Design.html?id=govtnQEACAAJ&source=kp_book_description&redir_esc=y" rel="noreferrer">Permutation Design: Buildings, Texts and Contexts</a>（2014）时偶然发现的。在 上下文 <ul> <li>考虑一个被划分为网格系统（a）的站点（b）。在</li> <li>让我们也考虑一个空间列表，在场地的限制（c）和邻接矩阵，以确定这些空间（d）的放置条件和相邻关系</li> </ul> <a href="https://i.stack.imgur.com/mCkiS.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/mCkiS.jpg" alt="enter image description here"/></a> 引用Terzidis教授的话： <blockquote> "A way of solving this problem is to stochastically place spaces within the grid until all spaces are fit and the constraints are satisfied" </blockquote> 上图显示了这样一个问题和一个示例解决方案（f）。在 算法（如书中所述） 1/“每个空间都与一个列表相关联，该列表包含根据所需邻域度排序的所有其他空间。” 2/”然后从列表中选择每个空间的每个单元，然后逐个随机放置在场地中，直到它们适合场地并且满足相邻条件。（如果失败，则重复该过程）” 九个随机生成的计划示例： <a href="https://i.stack.imgur.com/35i4I.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/35i4I.jpg" alt="enter image description here"/></a> 我要补充的是，作者稍后解释了该算法不依赖于暴力技术。在 问题 如您所见，解释相对模糊，步骤2也相当不清楚（就编码而言）。到目前为止，我只有“拼图碎片”： <ul> <li>“站点”（所选整数的列表）</li> <li>邻接矩阵（嵌套列表）</li> <li>“空格”（列表用语）</li> </ul> 对于每个单元： <ul> <li>返回其直接邻居的函数</li> <li>其理想邻居的列表，其索引按排序顺序排列</li> <li>基于实际邻居的健康评分 <pre><code>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.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(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 </code></pre></li> </ul> <a href="https://i.stack.imgur.com/xRN87.png" rel="noreferrer"><img src="https://i.stack.imgur.com/xRN87.png" alt="enter image description here"/></a> 如果有人能帮我把这些问题联系起来并向我解释一下，我将不胜感激： <ul> <li>如何根据单元的理想邻域度重新排序？</li> </ul> 编辑 正如你们中的一些人所注意到的，该算法基于某些空间（由单元组成）相邻的可能性。根据逻辑，每个单元在现场范围内随机放置： <ul> <li>我们事先检查它的直接邻居（上、下、左、右）</li> <li>如果至少有2个邻居，则计算一个适合度得分。（=这2+邻居的权重之和）</li> <li>最后，如果邻接概率很高的话，就把这个单元放进去</li> </ul> 大致可以理解为： ^{pr2}$ 考虑到大部分单元不会在第一次运行时放置（因为相邻概率很低），我们需要反复迭代，直到找到所有单元都可以拟合的随机分布。在 <a href="https://i.stack.imgur.com/SARen.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SARen.png" alt="enter image description here"/></a> 经过几千次迭代后，找到了一个合适的，并且所有相邻的需求都得到了满足。在 但是注意这个算法是如何产生分离的组而不是像所提供的示例中那样的非分割和统一的堆栈。我还应该补充说，近5000次迭代远远超过了Terzidis先生在他的书中提到的274次迭代。在 问题： <ul> <li>我处理这个算法的方式有问题吗？在</li> <li>如果没有，那么我缺少什么隐含条件？在</li> </ul>

0 条评论
分类：Python问答

默认排序时间排序

1 个回答

匿名 1天前

　擅长：python、mysql、java

我相信Kostas Terzidis教授将是一个优秀的计算机理论研究者，但他的算法解释一点帮助也没有。在 首先，邻接矩阵没有意义。你在提问中说： <blockquote> "the higher that value is, the higher the probability that the two spaces are adjecent is" </blockquote> 但是<code>m[i][i] = 0</code>，这意味着在同一个“办公室”的人更喜欢其他办公室作为邻居。你所期望的恰恰相反，不是吗？我建议改用这个矩阵： <pre><code>With 1 <= i, j <= 5: + + | 10 6 1 5 2 | | 10 1 4 0 | m[i][j] = | 10 8 0 | | 10 3 | | 10 | + + </code></pre> 有了这个矩阵 <ul> <li>最高值是10。所以<code>m[i][i] = 10</code>正是你想要的：同一个办公室的人应该在一起。在</li> <li>最小值为0。（根本不应该有任何联系的人）</li> </ul> <h2>算法</h2> 第1步：开始随机放置所有位置 （很抱歉基于1的矩阵索引，但它必须与邻接矩阵一致。） ^{pr2}$ 第2步：给解决方案打分 对于所有位<code>p[x][y]</code>，使用邻接矩阵计算分数。例如，第一位<code>1</code>有<code>2</code>和{<cd6>}作为邻居，因此得分为11： <pre><code>score(p[1][3]) = m[1][2] + m[1][4] = 11 </code></pre> 所有个人得分之和即为解决方案得分。在 第3步：通过交换位置来优化当前解决方案 对于每对位置<code>p[x1][y1], p[x2][y2]</code>，交换它们并再次评估解决方案，如果得分更好，则保留新的解决方案。在任何情况下，重复第3步，直到任何排列都不能改善解决方案。在 例如，如果将<code>p[1][4]</code>与<code>p[2][1]</code>交换： <pre><code> + -+ | - - 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 | + -+ </code></pre> 您将找到一个得分更高的解决方案： 交换前 <pre><code>score(p[1][3]) = m[1][2] + m[1][4] = 11 score(p[2][1]) = m[1][2] + m[1][2] = 12 </code></pre> 交换后 <pre><code>score(p[1][3]) = m[1][1] + m[1][4] = 15 score(p[2][1]) = m[2][2] + m[2][2] = 20 </code></pre> 所以保留它，继续交换位置。在 <h2>一些注意事项</h2> <ul> <li>请注意，如果在迭代的某一点上，您无法交换两个位置并获得更好的分数，那么算法将始终最终确定。在</li> <li>在含有<code>N</code>个位置的矩阵中，存在<code>N x (N-1)</code>个可能的交换，并且可以以一种有效的方式完成（因此，不需要暴力）。在</li> </ul> 希望有帮助！在

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

1 个回答

相关Python问题