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

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

КОНТЕКСТ

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

Цитируя профессора Терзидиса:

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

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

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

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

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

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

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

ПРОБЛЕМЫ

Как видите, объяснение относительно расплывчато, а шаг 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

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

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

РЕДАКТИРОВАТЬ

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

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

Вопросы:

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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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