DAG: минимизация расстояния между записями в сгруппированных узлах

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

entry     ]
entry--|  ] node 1
entry  |  ]
-----  |
entry<-|  ] node 2
entry  |  ]
-----  |
entry  |  ] node 3
entry--|  ]

Порядок записей в узле фиксирован. Записи хранятся в массиве с абсолютными индексами записей, на которые они ссылаются. Для каждой записи может быть не более 1 ссылки, и каждый узел имеет как минимум 1 ссылку. (другими словами, это высокосвязный граф). Граф содержит примерно 100 000 записей, сгруппированных в 40 000 узлов.

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

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


optimization directed-acyclic-graphs
person user1044459    schedule 07.12.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Проблема, которую вы описываете, заключается в том, как минимизировать максимальное расстояние. Я думаю, что это NP-сложно, поэтому простое решение не будет очень хорошим. Однако вы можете смоделировать ее как проблему ILP и использовать для этого какой-нибудь решатель.

Затем вы бы минимизировали M как цель.

ограничения будут M>= abs(s_i-e_i) для всех ссылок l_i. s_i и e_i представляют собой абсолютные индексы начала и окончания вашей ссылки.

Эти записи могут быть переписаны с точки зрения узла, которому они принадлежат, как s_i=n_i+c_i с n_i индексом узла, которому принадлежит s_i, и c_i фиксированным смещением внутри этого узла (среди других записей). e_i переписывается аналогичным образом. Затем вы настроены на оптимизацию n_i с помощью решателя.

person Origin    schedule 07.12.2012