Блог

Это сетка, которая представляет географическую область в 10 000 квадратов, где каждый квадрат равен 55225 квадратным метрам.

В наборе данных объем трафика на квадрат варьируется от 100 до 1000.

например:

квадрат 1 — 100,

квадрат 2 — 500

.

.

Площадь 10 000-800

Теперь я хочу разделить эту область таким образом, чтобы каждый раздел мог иметь разную область, но будет передавать одинаковый объем трафика, стандартное отклонение трафика между разделами должно быть минимальным.Есть предложения по алгоритму пространственного разбиения?

Есть несколько решений, которые вы должны принять, чтобы проинформировать вашу процедуру. На first question ум приходит вопрос, определено ли количество разделов? Вопрос second question в том, существуют ли какие-либо геометрические ограничения для группы, т. Е. Должны ли они быть смежными или какая-либо конкретная форма идеальна? Вопрос third question о том, насколько хорошо, достаточно хорош? Часто существует огромная разница во времени выполнения алгоритма, который обеспечивает идеальный ответ (возможно, жадный алгоритм), и алгоритма, который обеспечивает оптимальный ответ (возможно, исчерпывающий подход или подход «грубой силы»). Вы получите минимальное стандартное отклонение, сгруппировав любые 2 сектора с одинаковым объемом, так как каждая из ваших групп будет иметь стандартное отклонение 0. В любом случае, это звучит очень похоже на расширенный bin packing problem , и вам, вероятно, следует начать свой обзор литературы там.

Вам нужно упаковать свои ячейки по порядку…

Здесь я выбрал центральные точки для своих кругов, смещенных к самому высокому потоку трафика, и заполнил их оттуда.

 class trafficNode:
    def __init__(self,v,i):
        self.cluster = None
        self.value = v
        self.index = i
        self.occupied = False
    def occupy(self):
        self.occupied=True

def tryAdd(xList,mList,irow,icol):
    try:
        if not(mList[irow][icol] in xList and !mList[irow][icol].occupied):
            xlist.append(mList[irow][icol])
    except IndexError:
        chill = None
    return(xlist)

class cluster:
    def __init__(self):
        self.nodes = []
    def getTotal(self):
        total = 0
        for k in self.nodes:
            total  = k.value
        return(total)
    def addNode(self,n):
        self.nodes.append(n)
    def getNeighbors(self,m,r = 0):
        neighbors = []
        for k in self.nodes:
            i = k.index()
            for k2 in range(0,4):
                if k2==0:
                    neighbors = tryAdd(neighbors,m,i[0] 0,i[1] 1)
                elif k2==1:
                    neighbors = tryAdd(neighbors,m,i[0] 1,i[1] 0)
                elif k2==2:
                    neighbors = tryAdd(neighbors,m,i[0] 0,i[1]-1)
                elif k2==3:
                    neighbors = tryAdd(neighbors,m,i[0]-1,i[1] 0)
                if r != 0:
                    if k2==0:
                        neighbors = tryAdd(neighbors,m,i[0] 1,i[1] 1)
                    elif k2==1:
                        neighbors = tryAdd(neighbors,m,i[0] 1,i[1]-1)
                    elif k2==2:
                        neighbors = tryAdd(neighbors,m,i[0]-1,i[1] 1)
                    elif k2==3:
                        neighbors = tryAdd(neighbors,m,i[0]-1,i[1]-1)
        return(neighbors)
    def seed(self,m,irow,icol):
        self.nodes.append(m[irow][icol])
        m[irow][icol].occupy()
    def propogate(self,m,target):
        total = 0
        for k in self.nodes:
            total  = k.value
        s = 1
        while total<target:
            s = 1 if !s else 0
            lastTotal=Total
            n = self.getNeighbors(m,s)
            if len(n==0):
                break;
            else:
                if(abs(target-(total sum([k.value for k in n])))<abs(target-total)):
                    for k in n:
                        self.nodes.append(k)
                        m[k.index[0]][k.index[1]].occupy()
                else:
                    break;
    def contains(self,i):
        ret = False
        for k in self.nodes 
            if k.index == i
                ret = False
                break;
        return(ret)

def parseData(d,s): # Where d is the source datafile and s is the number of units per row.
    ret = []
    f = open(d,"r")
    text = f.read()
    lines = f.split("n")
    n = 0
    r = 0
    temp = []
    for k in lines:
        v = k.split(" - ")[1]
        n =1
        temp.append(trafficNode(v,(r,n)))
        if n == s:
            n = 0
            r  = 1
            ret.append(temp)
            temp = []
    return(ret)

def mapTotal(m):
    return sum([sum([k2.value for k2 in k]) for k in m])

def pTotal(m,n):
    return(mapTotal/n)

import sys

infile = sys.argv[1]
ncols = sys.argv[2]
ntowers = sys.argv[3]
m = parseData(infile,ncols)
s = pTotal(m,ntowers)

spots = [k.index for k in m if !k.occupied]
clusters = []
while len(spots > 0):
    spotVals = [m[k[0]][k[1]].value for k in spots]
    nextSpotIndex = spots[spotVals.index(max(spotVals))]
    clusters.append(cluster)
    clusters[n].seed(self,m,nextSpotIndex[0],nextSpotIndex[1])
    clusters[n].propogate(m,s)
    spots = [k.index for k in m if !k.occupied]
  

Тем не менее, я еще не тестировал его… Ваши данные поступают в виде этого изображения или другого файла?