如何根据他们理想的社区程度重新订购单位？(进行中)
sol*_*lub 31 python processing permutation
我需要帮助来实现一个允许生成建筑计划的算法,我最近在阅读Kostas Terzidis教授的最新出版物:排列设计:建筑,文本和上下文(2014)时偶然发现了这一点.
CONTEXT
- 考虑一个分为网格系统(a)的站点(b).
- 让我们考虑一个位于场地(c)范围内的空间列表和一个邻接矩阵来确定这些空间的放置条件和相邻关系(d)
引用Terzidis教授:
"解决这个问题的一种方法是随机地在网格中放置空格,直到所有空间都合适并且满足约束条件"
上图显示了这样的问题和样本解决方案(f).
算法(如书中简要描述)
1 /"每个空格都与一个列表相关联,该列表包含根据其所需邻域的程度排序的所有其他空格."
2 /"然后从列表中选择每个空间的每个单元,然后逐个放置在站点中,直到它们适合站点并满足相邻条件.(如果失败,则重复该过程)"
九个随机生成计划的示例:
我应该补充一点,作者后来解释说这个算法不依赖于暴力技术.
问题
如您所见,解释相对模糊,第2步相当不清楚(在编码方面).到目前为止我所有的都是"拼图":
- "网站"(所选整数列表)
- 邻接矩阵(嵌套列表)
- "空格"(列表字典)
每个单位:
- 返回其直接邻居的函数
- 它的理想邻居列表,其索引按排序顺序排列
基于其实际邻居的健康分数
Run Code Online (Sandbox Code Playgroud)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个邻居,则计算健身分数.(=这两个邻居的权重之和)
- 如果邻接概率很高,最后放置该单位
粗略地说,它会转化为:
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 个随机（统一）选择开始：
- 网格中的起点
- 开始办公
一旦定义了一个点和一个办公室，就会出现一个“扩展过程”，试图将所有办公大楼纳入网格中。
每个新块都是根据他的程序设置的：
- 第一。计算每个相邻单元格与办公室的亲和力。
- 第二。随机选择一个站点。选择应该根据亲和力来衡量。
每个办公大楼放置完毕后，需要进行另一个统一的随机选择：下一个要放置的办公室。
一旦选择，您应该再次计算每个站点的亲和力，并随机（加权）选择新办公室的起点。
0亲和办公室不添加。概率因子应该0针对网格中的该点。亲和函数选择是这个问题的一个有趣的部分。您可以尝试使用相邻单元格因子的加法甚至乘法。
扩建过程再次进行，直到办公室的每一块都被放置完毕。
所以基本上，办公室挑选遵循均匀分布，之后，对选定的办公室进行加权扩展过程。
尝试什么时候结束？， 如果：
- 在网格中放置新办公室没有意义（都有
affinity = 0） - Office 无法扩展，因为所有关联权重都等于 0
那么该尝试无效，应被丢弃并转移到全新的随机尝试。
否则，如果所有块都适合：它是有效的。
关键是办公室应该团结在一起。这是该算法的关键点，该算法根据亲和力随机尝试适应每个新办公室，但仍然是一个随机过程。如果不满足条件（无效），则随机过程再次开始，选择新的随机网格点和办公室。
抱歉，这里只有一个算法，但没有任何代码。
注意：我确信亲和力计算过程可以改进，甚至您可以尝试使用一些不同的方法。这只是一个帮助您获得解决方案的想法。
希望能帮助到你。