Алгоритм пересечения наименьшего ребра

Question

(Прежде чем кто-нибудь спросит, это не домашняя работа.)

Скажем, у вас есть 2 массива y0 и y1, где

y0 = [1,2,3,4,5,6] и y1 = [2,1,6,3,4,5]

Обратите внимание y0[0] = y1[1] = 1, это, по сути, означает, что y0[0] подключен к y1[1]. Точно так же y0[2] = y1[3] = 3 так что они тоже «связаны».

(Изображение предоставлено belisarius)

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

В приведенном выше примере обратите внимание,

1. Edge 1 и Edge 2 будут пересекаться.
2. Edge 6 будет пересекаться с Edge 3, Edge 4, Edge 5.

Следовательно, решение может быть 1,3,4,5 или 2,3,4,5 (размер = 4), поскольку ни одна из этих линий не будет пересекаться друг с другом. Может быть несколько решений, но мне нужно только одно.

Мой вопрос, есть какая-нибудь известная проблема CS, которая похожа на эту? Какой алгоритм я должен использовать?

Я пытался объяснить мою проблему на примере, однако, до сих пор неясно, я уточню любые вопросы. Заранее спасибо.

Answer 1

Предполагая, что ни один элемент не повторяется в одном массиве, это просто самая длинная возрастающая подпоследовательность.

Без ограничения общности предположим, что первый массив A1 просто [1, 2, 3, ..., n]. Это преобразование может быть выполнено в O (n) с помощью хэш-набора или в O (nlogn) с помощью BST.

Обратите внимание, что наш набор имеет пересечение тогда и только тогда, когда он содержит i и j с i < j, но j появляется перед i во втором массиве A2 (мы знаем с i < j, что i появляется перед j в A1).

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

Самая длинная возрастающая подпоследовательность имеет простое решение O (n ^ 2) и чуть более сложное решение O (nlogn).

Answer 2

Это в основном подсчет числа инверсий. [Источник - Раздел 5.3, Разработка алгоритмов, Kleinberg and Tardos. http://books.google.co.in/books/about/Algorithm_Design.html?id=25p3mHu3ij8C]

Answer 3

То, что вы описываете, известно как проблема соответствия для двудольных графов . Я подозреваю, что есть что-то (пока неустановленное) в проблеме, которая затрудняет ее решение. До сих пор вы действительно не накладывали никаких ограничений на то, какие края можно использовать. Предположим, что есть определенные ребра (не все), эти «возможные» ребра образуют график, а те, которые вы решили использовать, образуют максимальное соответствие. Нахождение максимального соответствия в графе является алгоритмом полиномиального времени, и его особенно легко кодировать для двудольного случая.

Название звучит так, как будто обстоятельства могут навязать какое-то обстоятельство, так что «непересекающиеся» ребра могут оказаться невозможными («пересечения наименьших ребер»). Возможно, вам нужно покрытие ребер (или 1-покрытие), то есть каждая вершина принадлежит хотя бы одному ребру. Тогда, если два «вершинных» массива имеют разную длину, не будет «идеального соответствия», то есть соответствия, которое также является прикрытием. Классический результат Теорема Холла о браке характеризует наличие идеальных совпадений в двудольном графе. Если граф регулярный (все вершины имеют одинаковую степень), то Теорема Кенига говорит нам, что существует идеальное соответствие (и даже больше).

Добавлено:

Возможно, стоит заявить, что на картинке говорится об ограничениях на выбор краев. Два набора вершин имеют координаты {(i, 0) | i = 1, .., N} и {(j, 1) | J = 1, .., N}. Существует N доступных ребер, отрезков, которые соединяют (i, 0) и (j, 1) всякий раз, когда y0 [i] = y1 [j]. Хотя в строке темы написано «пересечение наименьших ребер», решением является максимальное подмножество этих ребер, которое не допускает пересечений, - самый большой плоский линейный граф , содержащийся в данном графе перестановок .

Это связано с проблемой минимизации пересечения 2 уровней, рассмотренной здесь:

Альтернативный метод минимизации пересечения на иерархических графах - П. Муцель

«Мы предлагаем ... удалить минимальное количество ребер, чтобы получаемый граф был планарным с k-уровнем ... В этой статье мы рассматриваем случай k = 2 ... [W] e решает проблему извлечения двухуровневый планарный подграф максимального веса в данном двухуровневом графе. Эта задача NP-трудная. "

Настоящая задача накладывает одинаковое количество точек в двух наборах вершин, базовый граф является регулярным степени 1, и при нумерации или позиционировании точек выбор не допускается. Таким образом, невозможно сделать вывод, что это так сложно, как описанное в приведенной выше статье. Однако оно направляет нас к так называемым методам «ветвления и связывания» для точного решения таких проблем.

Давайте рассмотрим «ребра» исходной задачи как «узлы» нового графа, где два узла смежны, если исходные ребра пересекаются. [Это пример графа пересечений.] Теперь проблема в том, чтобы найти максимальное независимое множество нового графа. Проблемы такого рода, как правило, являются NP-сложными, но, опять же, мы подозреваем, что масштабы существующих проблем могут быть не такими общими.

Одной из причин подозревать наличие алгоритма полиномиального времени является наличие алгоритмов аппроксимации полиномиального времени для максимально независимых подмножеств графов пересечений для конечных наборов плоских выпуклых множеств:

Независимый набор графов пересечений выпуклых объектов в 2D - П. Агарвал и М Мустафа

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

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

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

Нэш, Николас; Грегг, Дэвид (2010), «Выходной чувствительный алгоритм для вычисления максимально независимого набора кругового графа», Письма обработки информации 116 (16): 630–634

Я также нашел эту ссылку в Google Книгах:

Валиенте, Габриэль (2003), «Новый простой алгоритм для задачи о множестве независимых множеств на круговых графах», Алгоритмы и вычисления: 14-й симпозиум, ISAAC 2003, Киото