python - ¿Cómo reordenar las unidades según su grado de vecindario deseable?(en proceso)

subplot python (2)

Necesitaría ayuda para implementar un algoritmo que permita la generación de planes de construcción, que recientemente he encontrado al leer la última publicación del profesor Kostas Terzidis: Diseño de permutación: Edificios, textos y contextos (2014).

CONTEXTO

Considere un sitio (b) que se divide en un sistema de cuadrícula (a).
Consideremos también una lista de espacios que se colocarán dentro de los límites del sitio (c) y una matriz de adyacencia para determinar las condiciones de colocación y las relaciones adyacentes de estos espacios (d)

Citando al Prof. Terzidis:

"Una forma de resolver este problema es colocar estocásticamente espacios dentro de la cuadrícula hasta que todos los espacios estén en forma y las restricciones estén satisfechas"

La figura de arriba muestra tal problema y una solución de muestra (f).

ALGORITMO (como se describe brevemente en el libro)

1 / "Cada espacio está asociado con una lista que contiene todos los demás espacios ordenados según su grado de vecindad deseable".

2 / "Luego, cada unidad de cada espacio se selecciona de la lista y luego se coloca una por una al azar en el sitio hasta que encajen en el sitio y se cumplan las condiciones adyacentes (si falla, se repite el proceso)

Ejemplo de nueve planes generados al azar:

Debo añadir que el autor explica más adelante que este algoritmo no se basa en técnicas de fuerza bruta .

PROBLEMAS

Como puede ver, la explicación es relativamente vaga y el paso 2 es poco claro (en términos de codificación). Todo lo que tengo hasta ahora son "piezas de un rompecabezas":

un "sitio" (lista de enteros seleccionados)
una matriz de adyacencia (listas anidadas)
"espacios" (diccionario de listas)

para cada unidad:

Una función que devuelve sus vecinos directos.
una lista de sus vecinos deseables con sus índices ordenados
un puntaje de condición física basado en sus vecinos reales
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

Realmente apreciaría si alguien pudiera ayudar a conectar los puntos y explicarme:

¿Cómo reordenar las unidades según su grado de vecindad deseable?

EDITAR

Como algunos de ustedes han notado, el algoritmo se basa en la probabilidad de que ciertos espacios (compuestos por unidades) sean adyacentes. La lógica tendría entonces que para que cada unidad se coloque aleatoriamente dentro de los límites del sitio:

Verificamos sus vecinos directos (arriba, abajo, izquierda derecha) de antemano
calcular un puntaje de condición física si al menos 2 vecinos. (= suma de los pesos de estos 2+ vecinos)
y finalmente colocar esa unidad si la probabilidad de adyacencia es alta

A grandes rasgos, se traduciría en esto:

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

Dado que una parte significativa de las unidades no se colocará en la primera ejecución (debido a la baja probabilidad de adyacencia), debemos repetir una y otra vez hasta que se encuentre una distribución aleatoria donde se puedan ajustar todas las unidades.

Después de unas pocas miles de iteraciones, se encuentra un ajuste y se cumplen todos los requisitos adyacentes.

Sin embargo, tenga en cuenta cómo este algoritmo produce grupos separados en lugar de pilas no divididas y uniformes como en el ejemplo proporcionado. También debo agregar que casi 5000 iteraciones es mucho más que las 274 iteraciones mencionadas por el Sr. Terzidis en su libro.

Preguntas:

¿Hay algo malo en la forma en que me acerco a este algoritmo?
Si no, ¿qué condición implícita me estoy perdiendo?

Estoy seguro de que el profesor Kostas Terzidis sería un excelente investigador de la teoría de la computación, pero sus explicaciones de algoritmos no ayudan en absoluto.

Primero, la matriz de adyacencia no tiene sentido. En las preguntas comentarios que dijiste:

"cuanto más alto sea ese valor, mayor será la probabilidad de que los dos espacios estén adyacentes"

pero m[i][i] = 0 , lo que significa que las personas en la misma "oficina" prefieren otras oficinas como vecino. Eso es exactamente lo contrario de lo que esperas, ¿no? Sugiero usar esta matriz en su lugar:

With 1 <= i, j <= 5: +----------------+ | 10 6 1 5 2 | | 10 1 4 0 | m[i][j] = | 10 8 0 | | 10 3 | | 10 | +----------------+

Con esta matriz,

El valor más alto es 10. Así que m[i][i] = 10 significa exactamente lo que quieres: las personas en la misma oficina deben estar juntas.
El valor más bajo es 0. (Personas que no deberían tener ningún contacto)

El algoritmo

Paso 1: Comience a poner todos los lugares al azar

(Lo siento por la indexación de matriz basada en 1, pero debe ser coherente con la matriz de adyacencia).

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 | +---------------------+

Paso 2: Puntuación de la solución

Para todos los lugares p[x][y] , calcule la puntuación utilizando la matriz de adyacencia. Por ejemplo, el primer lugar 1 tiene 2 y 4 como vecinos, por lo que el puntaje es 11:

score(p[1][3]) = m[1][2] + m[1][4] = 11

La suma de todas las puntuaciones individuales sería la puntuación de la solución .

Paso 3: Refina la solución actual intercambiando lugares

Para cada par de lugares p[x1][y1], p[x2][y2] , intercambie y evalúe la solución nuevamente, si la puntuación es mejor, conserve la nueva solución. En cualquier caso, repita el paso 3 hasta que ninguna permutación pueda mejorar la solución.

Por ejemplo, si intercambias p[1][4] con 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 | +---------------------+

Encontrarás una solución con una mejor puntuación:

antes de cambiar

score(p[1][3]) = m[1][2] + m[1][4] = 11 score(p[2][1]) = m[1][2] + m[1][2] = 12

después del intercambio

score(p[1][3]) = m[1][1] + m[1][4] = 15 score(p[2][1]) = m[2][2] + m[2][2] = 20

Así que guárdalo y continúa intercambiando lugares.

Algunas notas

Tenga en cuenta que el algoritmo siempre finalizará dado que en algún punto de la iteración no podrá intercambiar 2 lugares y obtener una mejor puntuación.
En una matriz con N lugares hay N x (N-1) intercambios posibles, y eso se puede hacer de una manera eficiente (por lo tanto, no se necesita fuerza bruta).

¡Espero eso ayude!

La solución que propongo para resolver este desafío se basa en repetir el algoritmo varias veces mientras se graban soluciones válidas. Como la solución no es única, espero que el algoritmo arroje más de 1 solución. Cada uno de ellos tendrá una puntuación basada en la afinidad de los vecinos.

Llamaré a un '' intento '' para una ejecución completa tratando de encontrar una distribución de planta válida. La ejecución completa del script consistirá en N intentos.

Cada intento comienza con 2 elecciones aleatorias (uniformes):

Punto de partida en la cuadrícula.
Oficina de partida

Una vez definidos un punto y una oficina, se trata de un '' proceso de expansión '' que intenta encajar todos los bloques de oficinas en la red.

Cada nuevo bloque se establece de acuerdo a su procedimiento:

Primero Calcular la afinidad para cada celda adyacente a la oficina.
2do. Selecciona aleatoriamente un sitio. Las opciones deben ser ponderadas por la afinidad.

Después de colocar cada bloque de oficinas, se necesita otra opción aleatoria uniforme: la próxima oficina que se colocará.

Una vez seleccionado, debe calcular nuevamente la afinidad para cada sitio, y seleccionar aleatoriamente (ponderado) el punto de partida para la nueva oficina.

0 oficinas de afinidad no agregan. El factor de probabilidad debe ser 0 para ese punto en la cuadrícula. La selección de la función de afinidad es una parte interesante de este problema. Puedes intentar con la suma o incluso con la multiplicación del factor de celdas adyacentes.

El proceso de expansión toma parte nuevamente hasta que se coloca cada bloque de la oficina.

Básicamente, la selección de oficinas sigue una distribución uniforme y, después de eso, el proceso de expansión ponderada ocurre para la oficina seleccionada.

¿Cuándo termina un intento? , Si:

No hay ningún punto en la cuadrícula para colocar una nueva oficina (todas tienen affinity = 0 )
Office no puede expandirse porque todos los pesos de afinidad son iguales a 0

Entonces, el intento no es válido y se debe descartar para pasar a un nuevo intento aleatorio.

De lo contrario, si todos los bloques están en forma: es válido.

El punto es que las oficinas deben permanecer juntas. Ese es el punto clave del algoritmo, que intenta ajustarse al azar a cada oficina nueva de acuerdo con la afinidad, pero sigue siendo un proceso aleatorio. Si las condiciones no se cumplen (no son válidas), el proceso aleatorio comienza nuevamente al elegir un punto de cuadrícula y una oficina recién aleatorios.

Lo siento, solo hay un algoritmo pero nada de código aquí.

Nota: Estoy seguro de que el proceso de cálculo de afinidad podría mejorarse o incluso podría intentarlo con algunos métodos diferentes. Esta es solo una idea para ayudarlo a obtener su solución.

Espero eso ayude.