algorithm - 查找算法 : Reconstruct a sequence with the minimum length combination of disjointed subsequences chosen from a list of subsequences

Question

我不知道在这里问这个问题是否合适，如果不合适，请见谅。

我得到了一个序列 ALPHA，例如:

A B D Z A B X

我得到了 ALPHA 的子序列列表，例如:

A B D
B D
A B
D Z
A
B
D
Z
X

我搜索了一种算法，该算法找到不连续子序列的最小长度 重建 ALPHA，例如在我们的案例中:

{A B D} {Z} {A B} {X}

有什么想法吗？我猜有些东西已经存在了。

Answer 1

您可以将此问题转化为寻找图中的最小路径。

节点将对应于字符串的前缀，包括一个用于空字符串的前缀。如果存在一个允许的子序列，当附加到字符串前缀 A 时，结果是字符串前缀 B，则将存在从节点 A 到节点 B 的边。

问题现在转化为寻找图中从空字符串对应的节点开始，到整个输入字符串对应的节点结束的最小路径。

您现在可以应用例如 BFS(因为边具有统一成本)或 Dijkstra 算法来找到此路径。

---

下面的python代码是基于上述原理的实现:

def reconstruct(seq, subseqs):
    n = len(seq)

    d = dict()
    for subseq in subseqs:
        d[subseq] = True

    # in this solution, the node with value v will correspond
    # to the substring seq[0: v]. Thus node 0 corresponds to the empty string
    # and node n corresponds to the entire string

    # this will keep track of the predecessor for each node
    predecessors = [-1] * (n + 1)
    reached = [False] * (n + 1)
    reached[0] = True

    # initialize the queue and add the first node
    # (the node corresponding to the empty string)
    q = []
    qstart = 0
    q.append(0)

    while True:
        # test if we already found a solution
        if reached[n]:
            break

        # test if the queue is empty
        if qstart > len(q):
            break

        # poll the first value from the queue
        v = q[qstart]
        qstart += 1

        # try appending a subsequence to the current node
        for n2 in range (1, n - v + 1):
            # the destination node was already added into the queue
            if reached[v + n2]:
                continue

            if seq[v: (v + n2)] in d:
                q.append(v + n2)
                predecessors[v + n2] = v
                reached[v + n2] = True

    if not reached[n]:
        return []

    # reconstruct the path, starting from the last node
    pos = n
    solution = []
    while pos > 0:
        solution.append(seq[predecessors[pos]: pos])
        pos = predecessors[pos]
    solution.reverse()

    return solution


print reconstruct("ABDZABX", ["ABD", "BD", "AB", "DZ", "A", "B", "D", "Z", "X"])

我没有太多使用 Python 的经验，这就是为什么我更喜欢坚持基础知识的主要原因(例如实现一个带有列表 + 开头索引的队列)。 p>