LINUX.ORG.RU

Нужен алгоритм упаковки(группировки)

 


0

2

Есть набор пар чисел. Нужно этот набор зарделить на N примерно равных групп где критерием является количество одинаковых чисел в группах. т.е. самый лучший набор будет состоять из таких пар чисел в которых нет в соседних группах.

например пары: [1, 2] [3, 4] [5, 6] [4,7] можно разделить на 2 группы таким образом: [3, 4] [5, 6] и [1, 2] [4, 7] тут получается что в этих группах есть совпадающее число 4 есть и там и там(его можно назвать связь), это не оптимальный вариант разделения.

Оптимальный будет: [3, 4][4, 7] и [5, 6] [1, 2] тут связей(совпадающих чисел нет)

как известно, правильная формулировка задачи — половина её решения. Сформулируй строго математически, что ты хочешь, и я уверен, ты получишь почти готовый алгоритм решения

Sahas ★★★★★ ()
Последнее исправление: Sahas (всего исправлений: 1)
Ответ на: комментарий от Sahas

как известно, правильная формулировка задачи

Задачи и так сформулирована паксимально математически. Если интересно как она изначально сформулирована то на самом деле там не пары чисел, а набор предикатов у которых по два аргумента и их нужно разделить на группы в которых как можно меньше будет одинаковых аргументов. Например:

predicate1 arg1 arg2

predicate2 arg2 arg3

predicate3 arg4 arg5

predicate4 arg6 arg7

andreykyz ★★ ()
Последнее исправление: andreykyz (всего исправлений: 1)
Ответ на: комментарий от anonymous

Приведи пример.

Тогда напиши способ сортировки который ты предлагаешь. Т.е. как конкретно эти пары изначально отсортировать?

andreykyz ★★ ()
Последнее исправление: andreykyz (всего исправлений: 1)
Ответ на: комментарий от anonymous

Я предсиавил числа как элементы графа

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

andreykyz ★★ ()
Ответ на: комментарий от anonymous

Полностью, поперёк, потом вдоль.

думаю это не сработает, т.к. пары представляют из себя изначально группы из 2 3 или 4 пар которые стоят рядом и имеют связи, сортировка нарушает эти локальные группы. Грубо говоря если просто в лоб разрезать поровну без сортировка это всегда будет лучше чем если вначале отсортировать.

andreykyz ★★ ()
Последнее исправление: andreykyz (всего исправлений: 2)

Посчитать количество каждых чисел. И на основе этого знания делить по N группам. Каждую подгруппу из неуникальных отрезков в одну группу: отрезки с 3 - в первую группу, отрезки с 4 - другую. Потом для добить уникальными для равенства групп.

anonymous ()

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

Можешь попробовать например разделённые множества тут использовать - объединешь по концам отрезка, а затем полученные разделённые множества разбиваешь по оптимальному размеру или просто реши как задачу о минимальном разрезе или как задачу разбиения на компоненты сильной связности графа.

AKonia ()
Последнее исправление: AKonia (всего исправлений: 3)
Ответ на: комментарий от AKonia

Разве это не собрат алгоритма составления оптимального расписания

Не в курсе про него почитаю.

У меня пока идея использовать оптимизационный алгоритм т.н. Алгоритм имитации отжига.

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

andreykyz ★★ ()
Последнее исправление: andreykyz (всего исправлений: 1)
Ответ на: комментарий от andreykyz

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

А ещё можете попробовать для каждой пары посчитать количество связей и просто вычленять пары у которых их больше всех(и соседей у которых больше 2-3 связей), пока не разобъёте в удобной пропорции(правда может получиться, что если это полносвязный граф, то его разбить проблемно)

AKonia ()
Последнее исправление: AKonia (всего исправлений: 1)

Есть набор пар чисел.

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

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

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

Crocodoom ★★★★ ()
Ответ на: комментарий от slovazap

То решение оптимальное из-за отсутствия связей, а в [[1, 2]] [[3, 4]] [[5, 6]] [[4,7]] есть одна связь между [3, 4] и [4, 7]. Т.е. другие оптимальные это:

  • [[1, 2] [3, 4] [5, 6] [4,7]]
  • [[1, 2]] [[3, 4] [5, 6] [4,7]]
  • [[5, 6]] [[3, 4] [1, 2] [4,7]]
xaizek ★★★★★ ()

На пистоне пойдёт?

from random import randint

def get_pairs(n=50, minmax=(1,10)):
    p = []
    for _ in range(n):
        a = randint(*minmax)
        while True:
            b = randint(*minmax)
            if b != a:
                break
        p += [(a,b)]
    return p
    
def make_dict(p):
    d = {}
    for i,(a,b) in enumerate(p):
        d[a] = d.get(a, []) + [i]
        d[b] = d.get(b, []) + [i]
    return d

def get_group(d, p):
    g = []
    n = []
    for k in d:
        for i in d[k]:
            a,b = p[i]
            if a in n or b in n:
                continue
            d[a].remove(i)
            d[b].remove(i)
            g.append((a,b))
            n += [a,b]
            break
    return g

p = get_pairs()
d = make_dict(p)
while True:
    g = get_group(d,p)
    if not g:
        break
    print(g)

Вывод:

[(3, 9), (4, 2), (7, 8), (10, 5)]
[(7, 3), (9, 2), (8, 6), (4, 10), (1, 5)]
[(6, 3), (8, 9), (1, 2), (4, 7), (5, 10)]
[(9, 3), (2, 1), (7, 10), (5, 8)]
[(9, 3), (2, 6), (5, 7), (10, 8), (4, 1)]
[(7, 3), (2, 9), (10, 8), (1, 5)]
[(4, 9), (7, 2), (8, 6), (10, 5)]
[(9, 6), (5, 2), (7, 1), (8, 10)]
[(2, 9), (6, 7), (4, 10)]
[(9, 7), (2, 4), (5, 10)]
[(7, 9), (1, 2)]
[(2, 9), (6, 7)]
[(2, 9), (5, 7)]
[(2, 1), (5, 7)]
[(6, 7)]

:3

anonymous ()
Ответ на: комментарий от andreykyz

Задачи и так сформулирована паксимально математически.

N примерно равных групп

Ну ты понял.

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

Пример: группы g1, g2… проверяем [a,b]. Если a in gi, b in gi, a in gj, b in gj and |gi|<|gj| — добавляешь в gi. Для оставшихся 2х случаев придумай сам.

tyakos ★★★ ()
Ответ на: комментарий от AKonia

что если это полносвязный граф, то его разбить проблемно)

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

andreykyz ★★ ()
Ответ на: комментарий от Crocodoom

То есть две точки лежат либо на одной вертикали

Можно числа заменить иероглифами разницы нет. Я просто для упрощения ниписал числа вот тут я написал как на самом деле все выглядит Нужен алгоритм упаковки(группировки) (комментарий)

andreykyz ★★ ()
Ответ на: комментарий от xaizek

Т.е. другие оптимальные это:

Они менее оптимальны т.к. группы отличаются в 2 раза друг от друга, нужно примерно одинаковые. нужно чтобы были примерно одинаковые. А у вас в 3 раза разница получается.

andreykyz ★★ ()
Ответ на: комментарий от anonymous

Введи badness = кол-во внешних связей. И примени «разделяй и строй».

Ну это похоже на Имитацию отжига. Делишь на части переставляешь пары между множествами а потом смотришь «badness» или «goodness» (смотря что есть) т.е. лучше/хуже

andreykyz ★★ ()
Ответ на: комментарий от tyakos

Пример: группы g1, g2… проверяем [a,b]. Если a in gi, b in gi, a in gj, b in gj and |gi|<|gj| — добавляешь в gi. Для оставшихся 2х случаев придумай сам.

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

andreykyz ★★ ()

У меня есть небольшое непонимание как натянуть мою задачу на теорию графов. Получается что изначально мой грав состоит из связей 2-х типов «разрывных»(между парами) и «неразрывных»(внутри пар). Задача получается в нахождении соседей с максимальным количеством «разрывных» связей. Можно для условности покрасить ребра разными цветами например зеленым(разрывные) и красным(неразрывные)

Прокоментируйте, правильно я свожу задачу к теории графов?

andreykyz ★★ ()
Ответ на: комментарий от andreykyz

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

AKonia ()
Последнее исправление: AKonia (всего исправлений: 1)
Ответ на: комментарий от andreykyz

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

AKonia ()
Ответ на: комментарий от andreykyz

Они менее оптимальны

Да, я хотел пример по связям показать и проигнорировал размеры.

У меня есть небольшое непонимание как натянуть мою задачу на теорию графов.

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

xaizek ★★★★★ ()
Последнее исправление: xaizek (всего исправлений: 1)
Ответ на: комментарий от andreykyz

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

Так известно же, что это за пары на обоих концах ребёр.

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

xaizek ★★★★★ ()
Последнее исправление: xaizek (всего исправлений: 1)