Как переупорядочить юниты в зависимости от степени желательности соседства? (в процессе)
Мне понадобится помощь в реализации алгоритма, позволяющего генерировать планы зданий, на который я недавно наткнулся при чтении последней публикации профессора Костаса Терзидиса: " Проект перестановок: здания, тексты и контексты" (2014).
КОНТЕКСТ
- Рассмотрим сайт (б), который разделен на сетку (а).
- Давайте также рассмотрим список пространств, которые должны быть размещены в пределах сайта (c), и матрицу смежности, чтобы определить условия размещения и соседние отношения этих пространств (d).
![enter image description here]()
Цитируя профессора Терзидиса:
"Способ решения этой проблемы состоит в том, чтобы стохастически размещать пространства в сетке до тех пор, пока все пространства не подойдут и ограничения не будут выполнены"
На рисунке выше показана такая проблема и пример решения (f).
АЛГОРИТМ (как кратко описано в книге)
1/"Каждый пробел связан со списком, который содержит все другие пробелы, отсортированные по степени желаемой окрестности".
2/"Затем каждая единица каждого пространства выбирается из списка, а затем поочередно размещается на сайте, пока они не поместятся на сайте и не будут соблюдены соседние условия. (Если это не удается, тогда процесс повторяется)"
Пример девяти случайно сгенерированных планов:
![enter image description here]()
Я должен добавить, что автор объясняет позже, что этот алгоритм не опирается на методы грубой силы.
ПРОБЛЕМЫ
Как видите, объяснение относительно расплывчато, а шаг 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 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
![enter image description here]()
Я был бы очень признателен, если бы кто-то мог помочь соединить точки и объяснить мне:
- как переупорядочить юниты в зависимости от степени желательности соседства?
РЕДАКТИРОВАТЬ
Как некоторые из вас заметили, алгоритм основан на вероятности того, что определенные пространства (составленные из единиц) являются смежными. Логика будет иметь то, что для каждого подразделения размещать случайным образом в пределах сайта:
- мы заранее проверяем его прямых соседей (вверх, вниз, влево, вправо)
- вычислить показатель пригодности, если хотя бы 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
Учитывая, что значительная часть юнитов не будет размещена на первом прогоне (из-за низкой вероятности смежности), нам нужно многократно повторять до тех пор, пока не будет найдено случайное распределение, в котором могут быть установлены все юниты.
![enter image description here]()
После нескольких тысяч итераций подгонка найдена и все соседние требования выполнены.
Однако обратите внимание, как этот алгоритм создает отдельные группы вместо неразделенных и однородных стеков, как в представленном примере. Я должен также добавить, что почти 5000 итераций - это намного больше, чем 274 итерации, упомянутых г-ном Терзидисом в его книге.
Вопросы:
- Что-то не так с тем, как я подхожу к этому алгоритму?
- Если нет, то какое неявное условие мне не хватает?
Ответы
Ответ 1
Решение, которое я предлагаю для решения этой проблемы, основано на повторении алгоритма несколько раз при записи правильных решений. Поскольку решение не является уникальным, я ожидаю, что алгоритм выдаст более 1 решения. Каждый из них будет иметь оценку, основанную на близости соседей.
Я назову " попытку ", чтобы найти подходящее распределение завода. Полный запуск скрипта будет состоять из N попыток.
Каждая попытка начинается с 2 случайного (равномерного) выбора:
- Начальная точка в сетке
- Начальный офис
После определения точки и офиса наступает " процесс расширения ", в котором все офисные блоки включаются в сеть.
Каждый новый блок устанавливается в соответствии с его процедурой:
- Первый. Вычислите сродство для каждой соседней ячейки с офисом.
- Второй. Случайно выберите один сайт. Выбор должен быть взвешен сродством.
После размещения каждого офисного блока необходим еще один случайный выбор: следующий офис.
После того, как вы выбрали, вы должны снова вычислить сходство для каждого сайта и случайным образом (взвешенно) выбрать начальную точку для нового офиса.
0 офисов близости не добавляют. Коэффициент вероятности должен быть 0 для этой точки в сетке. Выбор функции сродства является интересной частью этой проблемы. Вы можете попробовать с добавлением или даже умножением соседних клеток на фактор.
Процесс расширения принимает участие снова, пока каждый блок офиса не будет размещен.
Таким образом, в основном, выбор офиса следует за равномерным распределением, и после этого процесс взвешенного расширения происходит для выбранного офиса.
Когда заканчивается попытка? , Если:
- Там нет точки в сетке, чтобы разместить новый офис (все имеют
affinity = 0) - Офис не может расширяться, потому что все веса сродства равны 0
Тогда попытка недействительна и должна быть отменена, переходя к совершенно новой случайной попытке.
В противном случае, если все блоки соответствуют: это действительно.
Дело в том, что офисы должны держаться вместе. Это ключевой момент алгоритма, который случайным образом пытается соответствовать каждому новому офису в соответствии со сродством, но все же является случайным процессом. Если условия не выполняются (не действительны), случайный процесс начинается снова с выбора новой случайной точки сетки и офиса.
![enter image description here]()
Извините, здесь только алгоритм, но здесь нет кода.
Примечание: я уверен, что процесс вычисления соответствия может быть улучшен, или даже вы можете попробовать использовать несколько других методов. Это просто идея, чтобы помочь вам получить ваше решение.
Надеюсь, поможет.
Ответ 2
Я уверен, что профессор Костас Терзидис был бы отличным исследователем компьютерных теорий, но его объяснения алгоритма совсем не помогают.
Во-первых, матрица смежности не имеет смысла. В комментариях к вопросам вы сказали:
"Чем выше это значение, тем выше вероятность того, что эти два пространства являются приличными"
но 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, но она должна соответствовать матрице смежности.)
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
Так что держите его и продолжайте менять местами.
Некоторые заметки
- Обратите внимание, что алгоритм всегда будет завершаться, учитывая, что в какой-то момент итерации вы не сможете поменяться двумя местами и получить лучший результат.
- В матрице с
N местами есть N x (N-1) возможных перестановок, и это может быть сделано эффективным способом (поэтому, грубая сила не требуется).
Надеюсь, поможет!
