Е27.9 На складе с автоматической системой управления работают роботы, которые собирают грузы

Администратор

1 год назад

На складе с автоматической системой управления работают роботы, которые собирают грузы, расположенные на разных участках склада. Склад представляет собой прямоугольную сетку высотой $H$ и шириной $W$ . Каждый робот может перемещаться только вдоль осей сетки (вверх, вниз, влево, вправо), поэтому для оценки расстояний между объектами используется манхэттенское расстояние.

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

Под расстоянием между двумя точками и понимается манхэттенское расстояние, которое вычисляется по формуле:

В файле A хранятся данные о расположении грузов на двух участках склада, где каждый участок имеет размеры и . В каждой строке записана информация о расположении одного груза: сначала координата $x$ , затем координата $y$ . Количество грузов в файле не превышает 1000.

В файле B хранятся данные о грузах на трёх участках склада, где каждый участок также имеет размеры и . Количество грузов в файле не превышает 10 000. Структура хранения информации о грузах в файле B аналогична файлу A.

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

— среднее арифметическое абсцисс центроидов участков,
— среднее арифметическое ординат центроидов участков.

В ответе запишите четыре числа: в первой строке сначала целую часть абсолютного значения произведения затем целую часть абсолютного значения произведения для файла A; во второй строке — аналогичные данные для файла B.

Возможные данные одного из файлов иллюстрированы графиком.
Внимание! График приведён в иллюстративных целях для произвольных значений, не имеющих отношения к заданию.
Для выполнения задания используйте данные из прилагаемого файла.

ege-inf-zad27-9A.txt ege-inf-zad27-9A.xlsx

ege-inf-zad27-9B.txt ege-inf-zad27-9B.xlsx

Ответ:

для файла А

Px × 1000

Py × 1000

для файла Б

Px × 1000

Py × 1000

kompege.ru № 18314 (Д. Бахтиев) – задание №27

Показать решение...

Решение:

Visualizing DBSCAN Clustering

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

Решение: Кабанов Алексей

для файла А

from turtle import*
from random import*
def dist(p1, p2):
    x1, y1 = p1;
    x2, y2 = p2;
    return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-9A.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.replace(',','.').split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 2]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()

def centroid(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return min(m)[1]

cen = [centroid(cl) for cl in clusters]
px = sum(x for x,y in cen)/len(cen)
py = sum(y for x,y in cen)/len(cen)
print(abs(int(px*1000)), abs(int(py*1000)))

from turtle import*

from random import*

def dist(p1, p2):

x1, y1 = p1;

x2, y2 = p2;

return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-9A.txt')

data = []

for s in f:

x,y = [float(d) for d in s.replace(',','.').split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 2]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def centroid(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return min(m)[1]

cen = [centroid(cl) for cl in clusters]

px = sum(x for x,y in cen)/len(cen)

py = sum(y for x,y in cen)/len(cen)

print(abs(int(px*1000)), abs(int(py*1000)))

[476, 524]
23509 554

для файла Б

from turtle import*
from random import*
def dist(p1, p2):
    x1, y1 = p1;
    x2, y2 = p2;
    return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-9B.txt')
data = []
for s in f:
    x,y = [float(d) for d in s.replace(',','.').split()]
    data.append([x,y])
clusters = []
while data:
    cl = [data.pop()]
    for p in cl:
        sosed = [p1 for p1 in data if dist(p,p1) < 2]
        for p1 in sosed:
            cl.append(p1)
            data.remove(p1)
    clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]
print([len(cl) for cl in clusters])

#
# tracer(0)
# up()
# for cl in clusters:
#     color = random(),random(),random()
#     for x,y in cl:
#         goto(x*30, y*30)
#         dot(2, color)
# mainloop()

def centroid(cl):
    m = []
    for p in cl:
        s = 0
        for p1 in cl:
            s += dist(p,p1)
        m.append([s,p])
    return min(m)[1]

cen = [centroid(cl) for cl in clusters]
px = sum(x for x,y in cen)/len(cen)
py = sum(y for x,y in cen)/len(cen)
print(abs(int(px*1000)), abs(int(py*1000)))

from turtle import*

from random import*

def dist(p1, p2):

x1, y1 = p1;

x2, y2 = p2;

return abs(x2-x1)+abs(y2-y1)

f = open('ege-inf-zad27-9B.txt')

data = []

for s in f:

x,y = [float(d) for d in s.replace(',','.').split()]

data.append([x,y])

clusters = []

while data:

cl = [data.pop()]

for p in cl:

sosed = [p1 for p1 in data if dist(p,p1) < 2]

for p1 in sosed:

cl.append(p1)

data.remove(p1)

clusters.append(cl)

clusters = [cl for cl in clusters if len(cl) > 20]

print([len(cl) for cl in clusters])

# tracer(0)

# up()

# for cl in clusters:

# color = random(),random(),random()

# for x,y in cl:

# goto(x*30, y*30)

# dot(2, color)

# mainloop()

def centroid(cl):

m = []

for p in cl:

s = 0

for p1 in cl:

s += dist(p,p1)

m.append([s,p])

return min(m)[1]

cen = [centroid(cl) for cl in clusters]

px = sum(x for x,y in cen)/len(cen)

py = sum(y for x,y in cen)/len(cen)

print(abs(int(px*1000)), abs(int(py*1000)))

[3429, 3284, 3287]
3078 4758

Ответ:

23509 554
3078 4758