algorithm - 最长递增子序列算法中的节点结构(Jacobson & Vo)

Question

我在论文 "Heaviest Increasing/Common Subsequence Problems" 中理解计算完整最长递增子序列 (lis) 的节点结构有问题雅各布森和 Vo。

这是论文中的伪代码:

什么意思

node is an auxiliary array that, for each element in L, contains a record of an element that precedes this element in an increasing subsequence. The function newnode() constructs such records and links them into a directed graph. At the end of the algorithm, we can search from the maximal element of L to recover an LIS of sigma.

?您将如何实现这种结构？

我是否必须构建一个有向图，将序列的所有元素作为顶点(加上一个零顶点)和边“\sigma_i -> s”，然后搜索从 L 的最大元素开始的最长路径(并以零结尾)？有没有更有效的方法来获取完整的列表？

---

我的第二个问题:这个算法和wikipedia中描述的算法一样快吗？ ？如果不是:我是否也可以修改维基百科的算法来计算论文中描述的最重的公共(public)子序列？

Answer 1

我会用数组实现数组，将图形实现为具有结构共享的单链表。也就是说，在通用 C++ 中，

#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <vector>

template <typename T>
struct Node {
  explicit Node(const T& e) : element(e) {}

  T element;
  std::size_t index = 0;
  Node* previous = nullptr;
};

template <typename T, typename Compare>
std::vector<T> LongestIncreasingSubsequence(const std::vector<T>& elements,
                                            Compare compare) {
  if (elements.empty()) {
    return {};
  }
  std::vector<std::unique_ptr<Node<T>>> node_ownership;
  node_ownership.reserve(elements.size());
  std::vector<Node<T>*> tableau;
  for (const T& element : elements) {
    auto node = std::make_unique<Node<T>>(element);
    auto it = std::lower_bound(tableau.begin(), tableau.end(), node.get(),
                               [&](const Node<T>* a, const Node<T>* b) {
                                 return compare(a->element, b->element);
                               });
    if (it != tableau.begin()) {
      auto previous = it[-1];
      node->index = previous->index + 1;
      node->previous = previous;
    }
    if (it != tableau.end()) {
      *it = node.get();
    } else {
      tableau.push_back(node.get());
    }
    node_ownership.push_back(std::move(node));
  }
  Node<T>* longest = *std::max_element(
      tableau.begin(), tableau.end(),
      [](Node<T>* a, Node<T>* b) { return a->index < b->index; });
  std::vector<T> result(longest->index + 1);
  for (; longest != nullptr; longest = longest->previous) {
    result.at(longest->index) = longest->element;
  }
  return result;
}

int main() {
  for (int x : LongestIncreasingSubsequence(
           std::vector<int>{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3},
           std::less<int>())) {
    std::cout << x << '\n';
  }
}

如果您有幸使用具有垃圾回收功能的语言，您可以忽略 node_ownership 和 std::move 的业务。

这是一个 Python 版本。

import bisect


def longest_increasing_subsequence(elements):
    elements = list(elements)
    if not elements:
        return []
    # Build the tableau
    tableau_elements = []
    tableau_indexes = []
    predecessors = []
    for i, element in enumerate(elements):
        j = bisect.bisect_left(tableau_elements, element)
        predecessors.append(tableau_indexes[j - 1] if j > 0 else None)
        if j < len(tableau_elements):
            tableau_elements[j] = element
            tableau_indexes[j] = i
        else:
            tableau_elements.append(element)
            tableau_indexes.append(i)
    # Find the subsequence lengths
    lengths = []
    for i, predecessor in enumerate(predecessors):
        lengths.append(1 if predecessor is None else lengths[predecessor] + 1)
    # Extract the best subsequence
    best = max(range(len(lengths)), key=lambda i: lengths[i])
    subsequence = []
    while best is not None:
        subsequence.append(elements[best])
        best = predecessors[best]
    subsequence.reverse()
    return subsequence


print(longest_increasing_subsequence([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3]))