Вот очень быстрый алгоритм решения этой проблемы. Самая длинная возрастающая подпоследовательность в графе - это подпоследовательность пути в графе, и каждый путь должен принадлежать исключительно одному компоненту связности. Итак, если мы сможем решить эту проблему на связанных компонентах, мы сможем решить ее для всего графа, найдя лучшее решение для всех связанных компонентов.
Затем подумайте о случае, когда вы решаете эту проблему для связного графа G. В этом случае самая длинная возрастающая подпоследовательность, которую вы можете найти, будет сформирована путем сортировки узлов по их весу, а затем перехода от узла с наименьшим весом к во вторую, затем в третью, затем в четвертую и т. д. Если есть какие-то связи или дубликаты, их можно просто пропустить. Другими словами, вы можете решить эту проблему,
- Сортировка всех узлов по весу,
- Отбрасывая все узлы каждого веса, кроме одного, и
- Формирование LIS путем последовательного посещения каждого узла.
Это приводит к очень быстрому алгоритму решения общей проблемы. За время O (m + n) найдите все компоненты связности. Для каждого подключенного компонента используйте предыдущий алгоритм за время O (Sort (n)), где Sort (n) - время, необходимое для сортировки n элементов (которое может быть (n log n), если вы используете heapsort, (n + U ) для сортировки по сегментам, (n lg U) для сортировки по основанию и т. д.). Затем верните самую длинную найденную последовательность.
В целом, время выполнения - O (m + n + & Sort (n)), что превосходит мой предыдущий подход и должно быть намного проще кодировать.
Я изначально опубликовал этот ответ, который я оставлю, потому что считаю его интересным:
Представьте, что вы выбираете простой путь из графа G и смотрите на самую длинную возрастающую подпоследовательность этого пути. Хотя путь проходит по всему графу и может иметь множество промежуточных узлов, самая длинная возрастающая подпоследовательность этого пути на самом деле заботится только о
- первый узел на пути, который также является частью LIS, и
- с этой точки - следующее по величине значение в пути.
В результате мы можем думать о формировании LIS вот так. Начните с любого узла графа. Теперь перейдите к любому узлу в графе, который (1) имеет более высокое значение, чем текущий узел, и (2) доступен из текущего узла, затем повторите этот процесс столько раз, сколько нужно. Цель состоит в том, чтобы сделать это так, чтобы получить как можно более длинную последовательность возрастающих значений.
Мы можем смоделировать этот процесс как поиск наиболее длинного пути в группе доступности базы данных. Каждый узел в DAG представляет узел в исходном графе G, и есть ребро от узла u до узла v, если
- в G есть путь от u до v, и
- w(u) < w(v).
Это группа DAG из-за этого второго условия, хотя исходный график не является DAG.
Таким образом, мы можем решить эту общую проблему в два этапа. Сначала создайте DAG, описанный выше. Для этого:
Найдите компоненты связности исходного графа G и пометьте каждый узел его номером компонента связности. Время: O (m + n).
Для каждого узла u в G постройте соответствующий узел u 'в новом DAG D. Время: O (n).
Для каждого узла u в G и для каждого узла v в G, который находится в том же SCC, что и u, если w (u) ‹w (v), добавьте ребро от u 'до v'. Время: (n 2) в худшем случае, (n) в лучшем случае.
Найдите самый длинный путь в D. Этот путь соответствует самой длинной возрастающей подпоследовательности любого простого пути в G. Время: O (m + n).
Общее время выполнения: (n 2) в худшем случае, (m + n) в лучшем случае.
person
templatetypedef
schedule
22.09.2017
