Как найти кратчайший путь, проходящий через группу множеств?

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

Например, пусть есть следующие 4 неупорядоченных множества:
A=abcdefg
B=cd
C=abch
D=defi

Размер кратчайшего пути – 11.

Одно из возможных решений:
P=CADB=habcgdeficd
|P|=11

Обратите внимание, что наборы могут иметь общие элементы с соседними наборами на пути!
Также могут быть повторяющиеся элементы, принадлежащие разным наборам (как в приведенном выше примере: 'c' и 'd' дублируются в P, добавив B к CAD).

Подскажите, пожалуйста, алгоритм поиска кратчайшего пути, как описано.
Спасибо!


algorithm graph-theory set-theory
person ekatz    schedule 14.02.2019    source источник
comment
Как это ни интересно, я думаю, что этот вопрос, возможно, лучше подходит для MathExchange (или даже MathOverflow). Кроме того, я сомневаюсь, что существует эффективное решение этой проблемы.   -  person MinosIllyrien    schedule 14.02.2019
comment
Я склонен думать, что это решение будет неполиномиальным. Допустим, вы можете ответить на вопрос, сколько элементов у этих наборов общих в O(1), используя некоторые предварительные вычисления. Теперь поместите это каждое множество в граф, и у вас будет click, в котором каждое ребро является этим запросом. Вам нужно найти путь, который проходит через все вершины и имеет максимальное количество пересечений. Я не уверен, но я думаю, что это NP hard.   -  person Yonlif    schedule 14.02.2019

Ответы (2)


arrow_upward
0
arrow_downward

Этот вопрос можно свести к варианту кратчайшей распространенной задачи суперстроки

person ekatz    schedule 17.02.2019
comment
В вашем примере abcdefghi является суперстрокой A, B, C, D. Попробуйте >>> A,B,C,D=map(set, ["abcdefg", "cd", "abch", "defi"]) >>> all(set("abcdefghi") >= S for S in [A, B, C, D]) True. Но abcdefghi не кажется реальным путем (A содержит B). - person jferard; 18.02.2019
comment
Строка abcdefghi не является суперстрокой A,B,C,D, так как нет строки, являющейся вариацией множества C, содержащегося в этой строке. - person ekatz; 20.02.2019
comment
Моя ошибка: суперсет. В вашем первом посте не было упоминания о порядке, поэтому суперстрока - это решение другой проблемы. - person jferard; 20.02.2019
comment
В первом предложении я написал: ... кратчайший путь (Заказная комбинация наборов) ... - person ekatz; 21.02.2019

arrow_upward
0
arrow_downward

У вас есть график:

  • узел - множества;
  • ребро A-B существует, если A и B пересекаются, но не являются подмножеством друг друга;
  • если ребро A-B существует, расстояние A-B равно размеру A объединения B.

Вы ищете кратчайший путь, охватывающий все узлы. Это вариант задачи коммивояжера без необходимости возвращаться к началу.

Немного чтения: Как называется проблема для путешествия? проблема продавца (TSP), не возвращаясь к исходной точке?

EDIT: я пытаюсь обобщить то, что обсуждалось в комментариях и моих ответах.

  1. Что было неясно в вопросе: что вы будете делать, если набор является надмножеством другого? Я предположил, что вы хотите разделить эти два множества, поэтому я написал: «ребро AB существует, если A и B пересекаются, но не являются подмножествами друг друга». Для TSP просто используйте бесконечное расстояние между множествами A и B, если ребро не существует. Это относится к подмножествам/надмножествам.

  2. Путь упорядочен (по определению пути), но множества неупорядочены. Вот почему это не (тривиальная) вариация кратчайшей общей проблемы суперструн. Строка заказана, набор №.

  3. Идея TSP также не работает с расстоянием, определенным выше, потому что:

    • the definition of the distance is not good: the distance should strictly decrease when the intersection grows. A solution would be max(len(S)) - len(A ^ B).
    • более важно: вам не разрешается использовать одни и те же буквы «с обеих сторон» набора. Например. "abc" не может находиться на расстоянии 1 от "bcd" и на расстоянии 2 от "eb", так как если выбрать путь "a-bc-d", то ребро "abc" - "eb" не больше не существует. Возможно, жадный выбор поможет, но я не уверен.
person jferard    schedule 14.02.2019
comment
Проблема начинается, когда вам нужно включить набор, который полностью содержит другой. Простого TSP будет недостаточно. Тем не менее, ответ на самую короткую общую строку довольно близок к TSP. - person ekatz; 20.02.2019
comment
@ekatz Как видите, я написал: ребро AB существует, если A и B имеют пересечение, но не являются подмножествами друг друга. Это условие приводит к разделению подмножеств/надмножеств. - person jferard; 20.02.2019
comment
Как я уже писал: ... Мне нужно найти кратчайший путь (комбинация упорядоченных наборов), который проходит через все эти наборы. Таким образом, в вашем решении у меня может быть окончательный упорядоченный путь, в котором не будет находиться определенный набор. - person ekatz; 21.02.2019