Как переупорядочить юниты в зависимости от степени желательности соседства? (в процессе)

Question

Мне понадобится помощь в реализации алгоритма, позволяющего генерировать планы зданий, на который я недавно наткнулся при чтении последней публикации профессора Костаса Терзидиса: Проект перестановки: здания, тексты и контексты (2014).

КОНТЕКСТ

• Рассмотрим сайт (b), который разделен на сетку (a).
• Давайте также рассмотрим список пространств, которые должны быть размещены в пределах сайта (c), и матрицу смежности для определения условий размещения и соседних отношений этих пространств (d)

Цитирование проф. Терзидис:

«Способ решения этой проблемы состоит в том, чтобы стохастически размещать пространства в сетке до тех пор, пока все пространства не будут подогнаны и ограничения не будут выполнены»

На рисунке выше показана такая проблема и пример решения (f).

АЛГОРИТМ (как кратко описано в книге)

1 / "Каждое пространство связано со списком, который содержит все другие пространства, отсортированные по степени их желаемой окрестности."

2 / "Затем каждая единица каждого пространства выбирается из списка, а затем поочередно размещается на сайте, пока они не поместятся на сайте и не будут выполнены соседние условия. (Если произойдет сбой, то процесс повторяется) "

Пример девяти случайно сгенерированных планов:

Я должен добавить, что автор объясняет позже, что этот алгоритм не использует методы грубой силы .

ПРОБЛЕМЫ

Как видите, объяснение относительно расплывчато, и шаг 2 довольно неясен (с точки зрения кодирования). Все, что у меня есть, это кусочки головоломки:

• a "site" (список выбранных целых чисел)
• матрица смежности (вложенные списки)
• "пробелы" (словарь списков)

для каждой единицы:

• функция, которая возвращает своих прямых соседей
• список желаемых соседей с их индексами в отсортированном порядке

• оценка пригодности на основе фактических соседей

  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
  

Я был бы очень признателен, если бы кто-нибудь мог помочь соединить точки и объяснить мне:

• как переупорядочить юниты в зависимости от степени их желаемой близости?

EDIT

Как некоторые из вас заметили, алгоритм основан на вероятности того, что определенные пространства (составленные из единиц) являются смежными. Логика будет иметь то, что для каждого подразделения размещать случайным образом в пределах сайта:

• мы заранее проверяем его прямых соседей (вверх, вниз, влево, вправо)
• вычислить показатель пригодности, если хотя бы 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

Учитывая, что значительная часть юнитов не будет размещена при первом запуске (из-за низкой вероятности смежности), нам нужно повторять снова и снова до тех пор, пока не будет найдено случайное распределение, где могут быть установлены все юниты.

После нескольких тысяч итераций подгонка найдена и все соседние требования выполнены.

Обратите внимание, однако, как этот алгоритм создает разделенные группы вместо неразделенных и равномерных стеков , как в представленном примере. Я также должен добавить, что почти 5000 итераций - это намного больше, чем 274 итерации, упомянутых г-ном Терзидисом в его книге.

Вопросы:

• Что-то не так с тем, как я подхожу к этому алгоритму?
• Если нет, то какое неявное условие мне не хватает?

Answer 1

Я уверен, что профессор Костас Терзидис был бы отличным исследователем теории компьютеров, но его объяснения алгоритма совсем не помогают.

Во-первых, матрица смежности не имеет смысла. В ответах на вопросы вы сказали:

"чем выше это значение, тем выше вероятность того, что два пробела соприкасаются"

, но 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) возможных перестановок, и это может быть сделано эффективным способом (таким образом, грубая сила не требуется).

Надеюсь, это поможет!

Answer 2

Решение, которое я предлагаю для решения этой проблемы, основано на повторении алгоритма несколько раз при записи правильных решений. Поскольку решение не является уникальным, я ожидаю, что алгоритм выдаст более 1 решения. Каждый из них будет иметь оценку, основанную на близости соседей.

Я назову ' попытку ' для полного запуска, пытаясь найти действительное распределение завода. Полный запуск скрипта будет состоять из N попыток.

Каждая попытка начинается с 2 случайного (равномерного) выбора:

• Начальная точка в сетке
• Стартовый офис

После определения точки и офиса наступает процесс расширения , в котором все офисные блоки объединяются в сетку.

Каждый новый блок устанавливается в соответствии с его процедурой:

• первый. Вычислите сродство для каждой соседней ячейки с офисом.
• второй. Случайно выберите один сайт. Выбор должен быть взвешен сродством.

После размещения каждого офисного блока требуется другой случайный выбор: следующий офис должен быть размещен.

После выбора вы должны снова вычислить аффинитность для каждого сайта и случайным образом (взвесить) выбрать начальную точку для нового офиса.

0 офисы сродства не добавляются. Коэффициент вероятности должен быть 0 для эта точка в сетке. Выбор функции сродства интересен часть этой проблемы. Вы можете попробовать с дополнением или даже коэффициент умножения соседних клеток.

Процесс расширения повторяется до тех пор, пока не будет размещен каждый блок офиса.

Таким образом, в основном, выбор офиса следует за равномерным распределением, и после этого происходит взвешенный процесс расширения для выбранного офиса.

Когда заканчивается попытка? , Если:

• Нет смысла в сетке размещать новый офис (все имеют affinity = 0)
• Офис не может расширяться, потому что все веса сродства равны 0

Тогда попытка недействительна и должна быть отменена, переходя к совершенно новой случайной попытке.

В противном случае, если все блоки соответствуют: это допустимо.

Дело в том, что офисы должны держаться вместе. Это ключевой момент алгоритма, который случайным образом пытается соответствовать каждому новому офису в соответствии со схожестью, но все же является случайным процессом. Если условия не выполняются (не действительны), случайный процесс начинается снова с выбора новой случайной точки сетки и офиса.

Извините, есть только алгоритм, но здесь нет кода.

Примечание: Я уверен, что процесс вычисления соответствия может быть улучшен, или даже вы можете попробовать использовать несколько других методов. Это просто идея, чтобы помочь вам получить ваше решение.

Надеюсь, это поможет.