У меня есть несколько объектов с приоритетом, который является составным типом и только частично упорядочен . Мне нужно выбрать объекты в порядке приоритета (т.е. каждый раз приносить минимальный предмет). Но вместо того, чтобы произвольно завершать порядок, я бы предпочел, чтобы очередь была стабильной в том смысле, что если имеется более одного минимального элемента, она должна возвращать самый старый в первую очередь.
Есть ли какая-либо структура данных кучи, которая будет работать с частичным упорядочением? Или модификация обычной очереди приоритетов для работы с ней? Обычный выбор для нужного мне алгоритма - простая двоичная или 4-х разрядная куча, но это не работает с частичным упорядочением.
Поддержка значений приоритета:
- Поиск Infima (GLB) и супремумы (LuB). - максимальный такой, что . Вычисление инфимума из значений занимает время . Infimum (и supremum) каждого множества существует.
- Можно определить линейное расширение для частичного упорядочения. Использование его для очереди приоритетов - самый простой выход, поскольку алгоритм работает именно так. Но порядок влияет на производительность, и порядок вставки выглядит так, как будто лучше избегать наихудших случаев.
Кроме того, алгоритм, в котором я хочу использовать это, должен знать минимум всех приоритетов в очереди.
Приоритеты имеют некоторое реальное значение, но могут быть изменены, поэтому не представляется возможным полагаться на другие свойства, которые они могут иметь.
Примечание: двоичные кучи не работают с частичным упорядочением. Предположим, двоичная куча с , и , где и и . Они расположены в таком порядке, поэтому
a (0)
/ \
b (1) c (2)
теперь d вставлен. Следующая свободная позиция - 3, левый потомок , поэтому мы получаем
a (0)
/ \
b (1) c (2)
/
d (3)
Если (что подразумевает из транзитивности, но ничего не говорит о и ) и , то не местами с , потому что оно не меньше. Но на самом деле оно меньше, чем , но не сравнивается с ним, поэтому теперь основной инвариант кучи не выполняется; верх не минимален.
Я подозреваю, что лес куч, в стиле биномиальной кучи, может работать. По сути, важно всегда сравнивать новые значения с корнем и связывать только сопоставимые элементы. Это сделало бы деревья в лесу случайным размером и, таким образом, сделало сложность зависимой от количества взаимно несопоставимых множеств в куче. Я несколько подозреваю, что сложность не может быть исправлена (мы должны продолжать сравнивать, пока не найдем сопоставимый элемент), возможно, я что-то упустил, поэтому я оставляю это открытым.
Примечание. Порядок является частичным, и, хотя существуют способы определения линейных расширений для него, добавление временной метки и использование ее в качестве вторичного критерия не является одним из них. Предположим, что мы присвоили метку времени для каждого и определили порядок как если или ( и . Тогда предположим, что у нас есть различные , , , такие что и . Тогда и≼ ' ≼ ' б в ≼ б б ⋠ т ( ) ≤ т ( б ) б с т ( ) ≤ т ( б ) ≤ т ( с ) с ≤ ≼ ' б б ≼ ' с с ≼ ' , но , поэтому отношение не транзитивно и, следовательно, не является порядком. Этот вид расширения работает только для слабых упорядочений, но не для частичных.
Изменить: я понял, что не только является infimum любого определенного набора, но я на самом деле должен быть в состоянии эффективно получить infimum элементов в очереди. Итак, я сейчас размышляю, поможет ли добавление специальных узлов, содержащих инфу поддеревьев, в какую-то общую структуру кучи.
источник
Ответы:
Хотя точная проблема, поставленная в первоначальном вопросе, кажется трудной (и я был бы заинтересован в решении этой проблемы, особенно в части поиска информации). Я просто хотел отметить, что, если частично упорядоченный набор действительно состоит из векторов, использующих порядок продуктов, и если этого достаточно, чтобы просто иметь гарантию, что очередь приоритетов возвращает значения в порядке, «совместимом» с частичным порядком ( то есть, меньшие элементы всегда возвращаются перед большими элементами), то есть довольно простой способ сделать это.
По сути, идея состоит в том, чтобы найти топологическое упорядочение частично упорядоченного множества. То есть общий порядок « » такой, что a ≤ b≤T . Для векторов, использующих заказ продукта, это довольно просто: просто используйте лексикографический порядок « ≤ S », где первый «компонент» представляет собой сумму всех компонентов, используемых для заказа продукта (остальные компоненты по существу произвольны, так что вы также можете придерживаться слабого порядка). Затем мы можем видеть, что
а < бa≤b⟹a≤Tb ≤S
и
a = b
источник
Что не так с выполнением вашего частичного заказа?
Если вы предпочитаете «сначала самый старый», то ваш заказ фактически выполнен; «несопоставимые» предметы сопоставимы по возрасту.
Добавьте временную метку (или любое другое монотонно растущее целое число) к каждому элементу и используйте ее, если «реальное» сравнение невозможно.
источник
РЕДАКТИРОВАТЬ: это, кажется, интересная проблема, и у меня было небольшое исследование об этом. Я предлагаю вам прочитать следующее:
Я предлагаю вам прочитать эту статью: Daskalakis, Constantinos, et al. «Сортировка и отбор в позах». Журнал SIAM по вычислительной технике 40.3 (2011): 597-622.
Примечание: я удалил предыдущий наивный ответ. Пожалуйста, нажмите на правку, чтобы увидеть его.
источник
Мое использование терминологии может быть неправильным. Пожалуйста, отредактируйте мой ответ напрямую, чтобы исправить любые проблемы, которые вы найдете.
Во-первых, взаимно несопоставимые множества должны быть обнаружены на входах.
Например, может быть 5 объектов
a, b, c, d, e
, но их частичное упорядочение образует два несвязных графа:a ≤ b ≤ c
d ≤ e
{a, b, c}
несопоставим с любым из{d, e}
.Эти взаимно несопоставимые наборы должны быть обнаружены в первую очередь, прежде чем объекты могут быть сохранены в соответствующей структуре данных. Это можно сделать с помощью алгоритма поиска Union.
Для эффективности вставка нового объекта должна иметь эффективный способ поиска «списка существующих объектов, которые сопоставимы с этим новым объектом».
Теперь в каждом подмножестве (соответственно
{a, b, c}
и{d, e}
) минимумы должны быть четко определены. (Для каждого подмножества может быть один или несколько минимумов из-за частичного упорядочения.)Я вижу это как ориентированный ациклический граф . Попытка поместить это в кучу кажется катастрофической.
Чтобы извлечь минимумы из этой составной структуры данных, следующим шагом будет получение списка всех минимумов из всех подмножеств, выбор одного из них с самой ранней отметкой времени, удаление и возврат этого объекта.
источник
Проект, над которым я работаю, связан с аналогичной проблемой (кстати, я также использую частичный порядок векторов). У нас уже был алгоритм квадратичного времени для сортировки случайно упорядоченного списка, и я разработал алгоритм вставки, наблюдая за его поведением, когда только один объект вышел из строя. Мы не знаем, является ли это самой быстрой реализацией.
Вот какой-то псевдокод.
источник
Обычное поведение кучи - добавить новое значение в конец, а затем просеять его, пока оно сравнивается больше, чем его родитель.
Если вы пишете сравнение, которое возвращает то же самое для родителя и ребенка, несопоставимые случаи, так как для родителя больше, чем ребенок элемента, процесс sift up должен завершиться в нужной точке.
Это считается достаточно стабильным заказом для ваших целей?
Для пояснения возьмем пример из вашего комментария: a> b , а c не сопоставим с a или b :
итак, результат зависит от порядка вставки - кажется, это соответствует тому, что вы просите, но я не уверен, действительно ли это то, что вы хотите. Если это не так, не могли бы вы показать результат, который вы надеялись увидеть?
Итак, из вашего комментария (и правки к вашему вопросу) вы хотите, чтобы «сопоставимые» элементы перепрыгнули «несопоставимые» и нашли правильное место под порядком, если он есть. Я спросил об этом, потому что я не был уверен, как интерпретировать
(d и b попарно несопоставимы в вашем редактировании, но вы не хотите, чтобы они были в том порядке, в котором они были вставлены).
Мой следующий вопрос был бы о связи между «сопоставимыми» и «несопоставимыми» элементами, но я вижу, что вы обнаружили, что теперь они являются векторами в порядке продуктов (не было ясно, были ли некоторые элементы попарно- несравненный со всем , как NaN, или что).
Итак, если я возьму ваш новый пример и назначу векторные значения, верно ли, что это пример, где b несопоставимо с чем-либо еще:
и это должно сортировать к этому:
?
источник